OPTPV_20141125 01

Zhrnutie prednášky

Prednáška sa venuje úlohám separácie a klasifikácie bodov ako konvexným optimalizačným problémom riešiteľným lineárnym alebo kvadratickým programovaním. Na príkladoch dvoch množín bodov (napr. dobré a zlé produkty podľa kvality) sa vysvetľuje hľadanie deliacej lineárnej funkcie (nadroviny), ktorá ich oddeľuje. Diskutujú sa rôzne prípady: striktná lineárna separácia s viacerými možnými riešeniami, hľadanie najrobustnejšieho oddeľovača s najväčšou medzerou, aproximatívna separácia pri neoddeliteľných bodoch minimalizujúca počet nesprávne klasifikovaných bodov, a napokon nelineárna separácia. Zavádza sa úloha ako problém hľadania parametrov a a b lineárnej funkcie a^T x + b, pričom sa ukazuje, že pri absencii kritéria pre výber medzi viacerými riešeniami ide o tzv. problém uskutočniteľnosti (feasibility problem) s nulovou účelovou funkciou. Spomína sa aj metóda support vector machine ako kombinácia robustnej a aproximatívnej separácie s praktickým využitím napríklad pri rozpoznávaní tvárí.

• - Separácia a klasifikácia bodov sa formulujú ako konvexné optimalizačné úlohy (LP/QP).
• - Cieľom je nájsť lineárnu funkciu a^T x + b, ktorá oddelí dve množiny bodov.
• - Pri viacerých možných deliacich priamkach sa hľadá najrobustnejšia s najväčšou medzerou (margin).
• - Ak body nie sú lineárne separovateľné, používa sa aproximatívna separácia minimalizujúca počet chybne klasifikovaných bodov.
• - Support vector machine kombinuje robustnú a aproximatívnu separáciu a používa sa napr. pri rozpoznávaní tvárí.
• - Pri nelineárne oddeliteľných dátach je možné použiť nelineárny separátor.
• - Úloha bez konkrétnej účelovej funkcie sa rieši ako tzv. feasibility problem s nulovou cieľovou funkciou.

Zhrnutie pripravené s pomocou AI z prepisu videa.