Vagy nincs rá megoldás, mint például clustering esetében, ahol címke nélküli unsupervised a tanítás. Nincs minta adat, melyhez képest tanul. Nem terminátorról van szó meg skynet-ről. Gyököt sem fejben végzünk 5 tizedesjegyig, igaz? Csupán arra kérem a megoldást, hogy csoportosítsa az elemeket saját belátása szerint. Erre van szükségen, ilyen egyszerű. Viszont a paraméterek erősen befolyásolják a folyamatot. Tehát mégsem a matematikai eljárás végzi el a munka ordas részét.
Vagy pedig azért nem praktikus a hiper paraméterek keresése, mint például kereszt validáció esetén, mert rengeteg idő is lehet. Illetve sok esetben a kombinációs tér nem elég diverz a kevés adat miatt, vagy éppen túl nagy a megfelelő mértékű konvergáláshoz. Lásd genetikai algoritmusok, ahol a paraméterek kezdeti megválasztása végig hatással van az elkövetkező generációkra, és ezért könnyen lokális optimumon ragad az eredmény globális helyett. Vagyis nem kapunk hatékony eljárást pontos válaszokkal. Megint csak rulett az egész sok esetben.
Ezért szükségem van egy non-parametrikus megoldásra. Nem érdekel hogyan csinálja meg a feladatot. Vissza kérdezés nélkül kérem az eredményt, adott szempontból optimális beállításokkal automatikusan.
Mire kell nekem a clustering?
Elemek csoportosítására magas dimenziójú térben. A konkrét gyakorlati feladatot nem részletezhetem, de mutatok egy példát. Generálok alább 7 bejegyzést 3 paraméterrel uniform eloszlásból (Ruby kód):
7.times.map{ 3.times.map{ rand }}0.013438491689817145, 0.6059295099250915, 0.43407371597719424
0.4646181909510593, 0.17354565869186833, 0.11856299324595465
0.19035679865504918, 0.5537488631731675, 0.7118393242401592
0.9945609585463614, 0.5769530731910849, 0.6161285616429645
0.9469447880274934, 0.22756057412576614, 0.42115780137882186
0.756948695490351, 0.3831291895422715, 0.3075328890288558
0.5884440302242662, 0.12795693407535236, 0.328168763239297
Vajon milyen csoportokba oszthatók?
Megoldásom válasza:
0 →
0.9469447880274934, 0.22756057412576614, 0.42115780137882186
0.9945609585463614, 0.5769530731910849, 0.6161285616429645
0.013438491689817145, 0.6059295099250915, 0.43407371597719424
0.756948695490351, 0.3831291895422715, 0.3075328890288558
0.19035679865504918, 0.5537488631731675, 0.7118393242401592
1 →
0.5884440302242662, 0.12795693407535236, 0.328168763239297
0.4646181909510593, 0.17354565869186833, 0.11856299324595465
A fenti objektum egy Hash, melynek kulcsa a csoport nevét adja (0, 1, 2, 3 stb), az értéke pedig maguk a kiválasztott elemek. A 0-s csoport speciális. Oda azokat teszem, melyeket nem oszt be egyetlen csoportba sem, vagy pedig túl kicsi csoporthoz tartoznak. Az 1-es csoport a legnagyobb (értsd legtöbb elemet tartalmazó). Ha van 2-es, akkor az a második legnagyobb, és így tovább.
Hogyan kell nekem az eljárás?
Egyrészt ne csak azt mondja meg, hogy mely elemek elég hasonlók. Hanem azt is, hogy a talált csoportok közül melyeket veszi dominánsnak. Tehát a túl kicsi és jelentéktelenebb csoportokat nem kérem.
Tehát itt két dolgot terveztem meg teljesen adaptívra. Az egyik, hogy a hasonlóságot hogyan döntse el. Itt önhasonulásokat csinálok, hogy az adatot saját karakterisztikájához hasonlítsa. És annak figyelembevételével disztingváljon, amikor egy eljárásnál kell válasz egy optimális paraméterre. Például a következőnél:
Tegyük fel, hogy az alábbi méretű halmazokat találja (ennyi elem van bennük):
2, 2, 2, 2, 3, 4, 4, 5, 6, 6, 8, 13, 16, 17, 38
Hol választassam szét a csoportok méretét? Mi legyen az a limit, mely felettieket dominánsnak veszem, az alattiakat pedig elég jelentéktelennek?
Vegyük észre, hogy itt egy „közép” limitről beszélünk. Nem megfelelőek a statisztikai outlier detection számítások. Például átlag plusz Z szórás. Vagy IQR stb. A kevés adat miatt pedig szofisztikáltabb eljárás nem játszik.
Mi tehát a megfelelő megoldás ennek eldöntésére?
Mindig arra törekszek, hogy az eljárást vissza hajlítsam az univerzum saját karakterisztikáihoz, és minél kevesebb tetszőleges döntést tartalmazzon. Kvázi vele akarom eldöntetni. Mert így, ahogy egymásra épülnek a matematikai függvényeim és eljárásaim, egyre kevésbé divergál el az univerzum tulajdonságától. Tehát közelebb akarom tartani egymáshoz. Például nem akarok egy polinomiális egyenlet tervezésénél dönteni a kitevő mértékéről. Vagy legkisebbet választom, vagy ha gyökről van szó és erősebb kell, akkor lehet hogy inkább természetes alapú log-gal csökkentem egy érték növekedését az elem szám vagy idő egy egyéb függvényében.
Tehát vissza térve a kérdésre: Hol húzzam meg a közép limitet az alábbi értékeknél?
2, 2, 2, 2, 3, 4, 4, 5, 6, 6, 8, 13, 16, 17, 38
A válaszom az, hogy mivel a legtöbb eloszlás negatív exponenciális (legalábbis az egyik vége, például normál vagy fél normál, vagy log normál, vagy gamma, poisson, bates, T, chi, stb), ezért ha eloszlás helyett az értékeket ábrázoljuk, akkor ez azt jelenti, hogy az egyre nagyobb értékekből egyre kevesebb van. Ez idáig könnyen érthető.
Viszont ezért áthelyezem az egészet log domain-be, mely a nagyobb értékeket jobban vissza rántja. Mely annyit tesz, hogy a log-ját veszem mindegyiknek. Természetesen természetes alapút.
Majd átlagát veszem, mely egy középérték számítás. A közép limit vonzónak tűnik, de log domain-en kívül nem jó, mert a túl nagy kiugró értékek felhúzzák az aritmetikai átlagot. Hiába van kevés a nagy értékekből. Túl erős a hatásuk. Ezt vizuálisan vizsgálva is érezhetjük intuitív módon, ha vizuálisan ábrázoljuk a talált halmazokat és azok nagyságát. Túl erősen eldobja az alsó értékeket.
Majd az átlagot vissza fordítom a log domain-ből az eredetibe inverz log-al, ami nem más mint az exponenciális. És máris meg van a limit. Ez viszont nem más, mint a mértani közép. Közép limit értéke a fentihez (kerekítve):
5.6
Tehát a 6-os és annál nagyobbakat veszem eléggé dominánsnak. A sima átlag 8.5-ös értéked ad, tehát azzal csak a 13 és nagyobb értékek maradnának benne. Erre van szükségem. Hogy ne csak a legnagyobbak legyenek benne, hanem a kisebbekből is, de ne túl kicsik. Még akkor is ha a legnagyobb érték nagyságrendje drasztikusan nagyobb a többihez. Az értékek növekedéséhez képest határozódjon meg a limit.
Tehát a válaszom a számsor ketté választására az, hogy vegyük a mértani közepét. Hogy milyen más értékes tulajdonságai vannak a mértani átlagnak, azt majd talán egy másik bejegyzésben kitárgyalom.
Mutatok pár példát számsorra, és az ahhoz tartozó aritmetikai (sima) és mértani átlagot. A számsort hiperbolikusan generálom, hogy minél drasztikusabb értékek kerüljenek bele, ugyanis tapasztalatom, hogy a megtalált halmazok mérete ilyen drasztikusan csökken a gyakorlatban. Például az első 60% elemet tartalmaz, a második 5%, aztán 3% stb. Az értékeket kerekítem kevesebb tizedesre az olvashatóságért.
Számsor generálása (Ruby kód, minimum 2-es érték kell, mert 1 elemű halmazt nem értékelünk):
11.times.map{ (1/rand+1).round }.sortPéldák (számsor → aritmetikai átlag → mértani átlag):
2 2 2 2 3 3 5 6 7 9 11 → 4.73 → 3.88
3 3 3 4 4 5 6 7 15 26 53 → 11.7 → 6.97
2 2 2 3 4 7 10 14 37 44 165 → 26.4 → 8.82
2 2 2 2 3 3 5 5 6 10 11 → 4.64 → 3.8
2 2 2 2 2 3 4 4 5 5 48 → 7.18 → 3.71
2 2 2 2 2 3 4 4 4 5 15 → 4.09 → 3.27
2 2 2 2 3 3 3 4 5 7 66 → 9 → 3.98
2 2 2 2 3 3 4 5 7 11 19 → 5.45 → 4
2 2 2 2 2 2 2 3 3 3 5 → 2.55 → 2.43
2 2 2 4 4 4 5 5 23 40 518 → 55.4 → 7.75
Látszik, hogy például az utolsónál a sima átlag csak a legnagyobb halmazt mutatná (518), míg a mértani beleveszi még az előző két legnagyobbat is (23 40 518).
Színekkel megmutatva még érthetőbb talán. A zöldeket a sima átlag választja ki, a kékeket pedig hozzá veszi még a mértani átlag:
Tehát a blogom végső mondanivalója az, hogy ha egy számsort ketté akarsz választani valahol középen, de nem a legszélén, hogy csak a nagyobb értékekkel dolgozz, legyen az bármi, akkor a mértani átlagot használhatod könnyedséggel, mely nem a normál, hanem a logaritmikusan vissza húzott értékeken végez közép érték számítást. Erősen adaptív limitet ad.
Másik adaptív megoldásom volt, mely ennél jóval komplexebb, hogy a halmazok kiválasztásánál végig tudtam vinni teljesen non-parametrikusan a megoldást az utolsó lépésig. Nincs olyan kérdés, melyre nem tudok az adathoz és így saját magához igazodó robusztus döntést adni.
Mindezen túl sikerült a clustering eljárásomat tovább optimalizálnom és négyzetesen elrobbanóból lineárisba vissza hoznom futásidőben. Ruby-ban futtatom mert nem kell gyorsabb. Pár másodperc alatt lefut ezres elemszám alatt, 10 – 20 dimenzióban.
- sinexton blogja
- A hozzászóláshoz be kell jelentkezni
- 1171 megtekintés
Hozzászólások
Ingyen vagy olcson megtudod csinaltatni gyorsabban massal, mint azt neked telne barmifele modon, akkor azt kell tenni.
Every single person is a fool, insane, a failure, or a bad person to at least ten people.
- A hozzászóláshoz be kell jelentkezni
Mire gondolsz? Matematikai kutatás-fejlesztést nem lehet kidelegálni alkalmazottnak, mert olyan alkalmazott nem létezik praktikai okokból. vagy nem éri meg.
- A hozzászóláshoz be kell jelentkezni
Kicsit hosszu lett az iras, igy nem tudok mindennel egyeterteni. A log-exp nagyreszt azert jelenik meg a szamolasokban, mert a az egyes esemenyek valoszinusege altalaban szorzodik. Igy az illesztesnel a likelihood szorzat helyett, reszben numerikus okokbol a valoszinusegek logaritmusat szoktak hasznalni, vagy a negetiv logaritmusat, ami az entropia. Utobbi azert is kenyelmes, mert a lekodolashoz szukseges bitek szamat is megadja.
A parameterek pedig nem csak ugy legbol kapottak szoktak lenni, altalaban a tanulasi minta tanulasi-teszt mintara bontasaval lehet vizsgalni egy parameter hasznossagat.
Nekem van egy egyelore nem peer-reviewed cikkem a Kollmogorov komplexeitasrol, nekem az a legjobb megoldasom a temara, de az nyilvan nem a futasidorol szoval.
- A hozzászóláshoz be kell jelentkezni
Kicsit hosszu lett az iras, igy nem tudok mindennel egyeterteni. A log-exp nagyreszt azert jelenik meg a szamolasokban, mert a az egyes esemenyek valoszinusege altalaban szorzodik. Igy az illesztesnel a likelihood szorzat helyett, reszben numerikus okokbol a valoszinusegek logaritmusat szoktak hasznalni, vagy a negetiv logaritmusat, ami az entropia. Utobbi azert is kenyelmes, mert a lekodolashoz szukseges bitek szamat is megadja.
Igen, viszont inkább arra akartam utalni, hogy nem valószínűségi számításokhoz kapcsolódó problémáknál is meglepően gyakori megoldásaim között a log felhasználása. Mint egy kvázi komplexitás csökkentést hajt végre és egy "alacsonyabb" szinten lehet dolgozni a maradék komplexitással.
Az entrópia felhasználási esetei is meglepők és tetszik például a hasznossága különböző valósz. eloszlások összehasonlításánál.
A parameterek pedig nem csak ugy legbol kapottak szoktak lenni, altalaban a tanulasi minta tanulasi-teszt mintara bontasaval lehet vizsgalni egy parameter hasznossagat.
Erre írtam a kereszt validációs példát. Sok esetben nem praktikus vagy nem teljesen kivitelezhető, például ha túl kevés adat van, vagy nincs cimkézett adat, amihez képest lehet tanulni és validálni. Például ez van legtöbb esetben clustering-nél. És ha ez nem lehetséges, akkor nincs optimalizálási lehetőség validációval. De mégis meg kell hozni a döntést. És matematikailag becsült vagy bármilyen heurisztikával előállított paraméter mindig jobb lesz, mint a légből kapott emberi tippelés. Erre jön be részben a kutatásaim és fejlesztéseim nagy része.
Nekem van egy egyelore nem peer-reviewed cikkem a Kollmogorov komplexeitasrol, nekem az a legjobb megoldasom a temara, de az nyilvan nem a futasidorol szoval.
Izgalmas kapcsolódó téma szerintem az "irreducibility", mely bizonyos értékek előállításánál azt mondja ugye, hogy nincs shortcut. Tele vagyunk ilyennel univerzumunkban, ahol a heurisztikus lehetőségek izgalmasak.
Munkámban általában azt értetem meg a emberekkel, hogy nincs végtelen (univerzumunkban nincs 0% és 100% és ez könnyen bizonyítható). Tehát ha egy tervezési hibát csökkentünk, akkor azt legtöbb eseteben nem lehet levinni 0%-ra, mert nem megismerhető a szükséges információ még akkor sem, ha ismerjük univerzumunk összes részecskéjének irányvektorát és pozícióját. De lehet rajta jócskán csökkenteni.
Köszi.
- A hozzászóláshoz be kell jelentkezni