Lineární oddělitelnost - Linear separability

Existence čáry oddělující dva typy bodů znamená, že data jsou lineárně oddělitelná

v Euklidovská geometrie, lineární oddělitelnost je vlastnost dvou sad bodů. To je nejjednodušší vizualizovat ve dvou dimenzích ( Euklidovské letadlo ) tím, že jednu sadu bodů považujete za modrou a druhou za červenou. Tyto dvě sady jsou lineárně oddělitelné pokud existuje alespoň jeden čára v rovině se všemi modrými body na jedné straně čáry a všemi červenými body na druhé straně. Tato myšlenka se okamžitě zobecní na euklidovské prostory vyšších dimenzí, pokud je čára nahrazena a nadrovina.

Problém stanovení, zda je dvojice sad lineárně oddělitelná, a nalezení oddělovací nadroviny, pokud jsou, vyvstává v několika oblastech. v statistika a strojové učení, klasifikace určitých typů dat je problém, pro který existují dobré algoritmy založené na tomto konceptu.

Matematická definice

Nechat ${ displaystyle X_ {0}}$ a ${ displaystyle X_ {1}}$ být dvě sady bodů v n-rozměrný euklidovský prostor. Pak ${ displaystyle X_ {0}}$ a ${ displaystyle X_ {1}}$ jsou lineárně oddělitelné pokud existují n + 1 reálná čísla ${ displaystyle w_ {1}, w_ {2}, .., w_ {n}, k}$ , takže každý bod ${ displaystyle x v X_ {0}}$ splňuje ${ displaystyle sum _ {i = 1} ^ {n} w_ {i} x_ {i}> k}$ a každý bod ${ displaystyle x v X_ {1}}$ splňuje ${ displaystyle sum _ {i = 1} ^ {n} w_ {i} x_ {i}$ , kde ${ displaystyle x_ {i}}$ je ${ displaystyle i}$ -tá složka ${ displaystyle x}$ .

Ekvivalentně jsou dvě sady lineárně oddělitelné přesně, když jsou příslušné konvexní trupy jsou disjunktní (hovorově nepřekrývejte).^{[Citace je zapotřebí ]}

Příklady

Tři non-kolineární body ve dvou třídách ('+' a '-') jsou vždy lineárně oddělitelné ve dvou rozměrech. To ilustrují tři příklady na následujícím obrázku (případ „+“ není zobrazen, ale je podobný případu „-“):

Avšak ne všechny sady čtyř bodů, žádné tři kolineární, jsou lineárně oddělitelné ve dvou rozměrech. Následující příklad by potřeboval dva přímky, a proto není lineárně oddělitelný:

Všimněte si, že tři body, které jsou kolineární a tvaru "+ ⋅⋅⋅ - ⋅⋅⋅ +" také nejsou lineárně oddělitelné.

Lineární oddělitelnost booleovských funkcí v systému Windows n proměnné

A Booleovská funkce v n proměnné lze považovat za přiřazení 0 nebo 1 ke každému vrcholu booleovské hodnoty hyperkrychle v n rozměry. To dává přirozené rozdělení vrcholů do dvou sad. Booleovská funkce se říká, že je lineárně oddělitelné za předpokladu, že tyto dvě sady bodů jsou lineárně oddělitelné. Počet odlišných booleovských funkcí je ${ displaystyle 2 ^ {2 ^ {n}}}$ kde n je počet proměnných předaných do funkce.^[1]

Počet lineárně oddělitelných booleovských funkcí v každé dimenzi^[2] (sekvence A000609 v OEIS )
Počet proměnných	Booleovské funkce	Lineárně oddělitelné booleovské funkce
2	16	14
3	256	104
4	65536	1882
5	4294967296	94572
6	18446744073709552000	15028134
7	3.402823669 ×10^38	8378070864
8	1.157920892 ×10^77	17561539552946
9	1.340780792 ×10^154	144130531453121108

Podporujte vektorové stroje

H₁ neodděluje sady. H₂ ano, ale jen s malou rezervou. H₃ odděluje je s maximální rezervou.

Klasifikace údajů je v systému Windows běžný úkol strojové učení Předpokládejme, že jsou uvedeny některé datové body, z nichž každý patří do jedné ze dvou sad, a chceme vytvořit model, který rozhodne, která sada Nový datový bod bude v. V případě podporovat vektorové stroje, datový bod je považován za a p-dimenzionální vektor (seznam p čísla) a chceme vědět, zda můžeme takové body oddělit pomocí (p - 1) -dimenzionální nadrovina. Tomu se říká a lineární klasifikátor. Existuje mnoho hyperplánů, které by mohly klasifikovat (oddělit) data. Jednou z nejvhodnějších možností jako nejlepší nadrovina je ta, která představuje největší oddělení nebo okraj mezi těmito dvěma sadami. Takže zvolíme nadrovinu tak, aby byla vzdálenost od ní k nejbližšímu datovému bodu na každé straně maximalizována. Pokud taková nadrovina existuje, je známá jako hyperrovina s maximálním okrajem a lineární klasifikátor, který definuje, je známý jako maximum klasifikátor marže.

Více formálně, vzhledem k některým tréninkovým údajům ${ displaystyle { mathcal {D}}}$ , sada n body formuláře

{ displaystyle { mathcal {D}} = left {( mathbf {x} _ {i}, y_ {i}) mid mathbf {x} _ {i} in mathbb {R} ^ {p}, , y_ {i} in {- 1,1 } doprava } _ {i = 1} ^ {n}}

Kde y_i je buď 1 nebo -1, což označuje množinu, do které bod ${ displaystyle mathbf {x} _ {i}}$ patří. Každý ${ displaystyle mathbf {x} _ {i}}$ je p-dimenzionální nemovitý vektor. Chceme najít hyperrovinu s maximálním okrajem, která rozděluje body, které mají ${ displaystyle y_ {i} = 1}$ od těch, kteří mají ${ displaystyle y_ {i} = - 1}$ . Jakoukoli nadrovinu lze zapsat jako množinu bodů ${ displaystyle mathbf {x}}$ uspokojující

{ displaystyle mathbf {w} cdot mathbf {x} -b = 0,}

kde ${ displaystyle cdot}$ označuje Tečkovaný produkt a ${ displaystyle { mathbf {w}}}$ (nemusí být nutně normalizováno) normální vektor do nadroviny. Parametr ${ displaystyle { tfrac {b} { | mathbf {w} |}}}$ určuje odsazení nadroviny od počátku podél normálového vektoru ${ displaystyle { mathbf {w}}}$ .

Pokud jsou tréninková data lineárně oddělitelná, můžeme vybrat dva hyperplány takovým způsobem, že oddělují data a mezi nimi nejsou žádné body, a poté se pokusit maximalizovat jejich vzdálenost.

Viz také

Reference

^ 1962-, Russell, Stuart J. (2016). Umělá inteligence je moderní přístup. Norvig, Peter 1956- (třetí vydání). Boston. p. 766. ISBN 978-1292153964. OCLC 945899984.CS1 maint: číselné názvy: seznam autorů (odkaz)
^ Gruzling, Nicolle (2006). "Lineární oddělitelnost vrcholů n-dimenzionální hyperkrychle. M.Sc Thesis". University of Northern British Columbia. Citovat deník vyžaduje | deník = (Pomoc)

[1] 1962-, Russell, Stuart J. (2016). Umělá inteligence je moderní přístup. Norvig, Peter 1956- (třetí vydání). Boston. p. 766. ISBN 978-1292153964. OCLC 945899984.CS1 maint: číselné názvy: seznam autorů (odkaz)

[2] Gruzling, Nicolle (2006). "Lineární oddělitelnost vrcholů n-dimenzionální hyperkrychle. M.Sc Thesis". University of Northern British Columbia. Citovat deník vyžaduje | deník = (Pomoc)

[1]

[2]