Hints voor algoritme gezocht

[Verwijderd]

Ik ben aan het nadenken over een goed algoritme voor het volgende optimalisatieprobleem:

Ik heb enkele duizenden punten in een grofweg duizend-dimensionale ruimte. Alle mogelijke verbindingen tussen paren van deze punten hebben een numeriek uitgedrukte eigenschap die we maar even "score" zullen noemen. Het doel is het paar van 2 punten te vinden dat de hoogste score heeft.

Helaas is score op geen enkele manier af te leiden uit eigenschappen van de punten zelf. Score is wel experimenteel meetbaar, maar praktisch gezien niet voor meer dan maximaal enkele duizenden paren - terwijl er miljoenen mogelijke combinaties zijn. Wel geldt dat score voor op elkaar gelijkende paren (dus paren waarvan de punten dichtbij elkaar liggen in de duizend-dimensionale ruimte) ongeveer gelijk is.

Een concreet voorbeeld hiervan: stel dat we in een 2-dimensionale ruimte de punten (1,0) en (7,5) hebben, en dat de score van dit puntenpaar experimenteel is vastgesteld op 10. Je kan dan een redelijke voorspelling doen dat de score van het puntenpaar (1,1) en (7,6) ook zo rond de 10 zal liggen, maar over het puntenpaar (-5,3) en (7,-2) weet je niets.

Het gaat me om dat soort voorspellingen. Ik probeer een algoritme te schrijven dat, gegeven een aantal experimenteel gemeten puntenparen, voor alle niet-gemeten puntenparen een voorspelling doet op basis van de afstand tussen deze punten en de wel gemeten puntenparen. Nu is zoiets al een keer gedaan op basis van lineaire regressie, maar ik heb het idee dat er met moderne AI methoden meer uit te halen zou moeten zijn.

Echter, er is nog een andere dimensie van het probleem, en dat is waar lineaire regressie niet uit komt. Een optimalisatie op basis van regressie kan weliswaar een voorspelling geven voor ongemeten puntenparen gegeven de gemeten puntenparen, maar als er geen enkel gemeten puntenpaar in de buurt ligt van een ongemeten paar, dan zal de voorspelling ook niet best zijn (grote standard error). Ik ben daarom tevens op zoek naar een algoritme dat de onzekerheid in de toekomstige voorspelling van de scores voor alle paren probeert te minimaliseren door (gegeven een reeds gemeten set van gemeten paren) een zo goed mogelijk gekozen (maar qua omvang beperkte) set paren voor te dragen voor experimentele bepaling van de score. Maar ik ben er nog niet uit hoe je zoiets zou kunnen aanpakken. Heeft iemand op basis van bovenstaande beschrijving een suggestie van de oplossingsrichting waarin ik dit zou kunnen zoeken?

[naitsoezn]

klinkt alsof je op zoek bent naar "design of experiments". Is wel software voor te vinden....

Edit: en ipv lineaire regressie kun je ook één van de talloze niet-lineaire regressie methodes pakken om een model van je data te maken.

[ Voor 42% gewijzigd door naitsoezn op 24-07-2013 11:48 ]

[_js_]

Het tweede vraagstuk lijkt op Wikipedia: Maximum coverage problem, de beste benadering daarvoor (exact lijkt me niet te doen met zo'n grote dataset) is ook de meest simpele, telkens het paar kiezen dat de beste verbetering geeft. Of de precisie (1-1/e) nog steeds hetzelfde is als in het algemene probleem wanneer je ipv meeste niet gecoverde punten kiest voor laagste onzekerheid weet ik niet.

[Verwijderd]

Zo maar een schot in het duister hoor, maar kun je niets met SVM in dit geval als je de multiclass variant hiervan pakt of een K nearest algoritme gespecialiseerd in meerdere dimensies ?

[Grijze Vos]

Ben je niet op zoek naar local search?

[ Voor 49% gewijzigd door Grijze Vos op 25-07-2013 11:29 ]

[Coca-Cola]

Hoe belangerijk zijn die 1000 dimensies? Je kan eventueel met iets als PCA het aantal dimensions vrij sterk reduceren en dan kan je misschien wat eenvoudiger met een meer brute force algoritme aan de slag. Tijdens mijn afstuderen had ik ook >1000 dimensionale data en kon dit met behoudt van 95% van de variantie terugbrengen tot enkele 10 tallen dimensies.

[Zoijar]

Verwijderd schreef op donderdag 25 juli 2013 @ 11:16:
Zo maar een schot in het duister hoor, maar kun je niets met SVM in dit geval als je de multiclass variant hiervan pakt of een K nearest algoritme gespecialiseerd in meerdere dimensies ?

Curse of dimensionality is een probleem bij duizend-dimensionale data (i.e. vrijwel alle punten zullen aan de rand liggen en relatief ver van elkaar)... dimensionality reduction is niet zo'n gek idee.

[ Voor 8% gewijzigd door Zoijar op 25-07-2013 12:47 ]

[Verwijderd]

Heeft u ook een schematische weergave? De theoretische kant van een formule is leuk en belangrijk maar een visuele weergave kan bijvoorbeeld soms meer zeggen dan 1000 woorden ( of dementi's).

[Caelorum]

Een visuele weergave van datapunten met duizend features?

[Phoib]

Hij zal waarschijnlijk 2 dimensionaal bedoelen.

Er is geen relatie tussen 2 punten? Als in, tussen punten (1,0) en (1,1), wat is het verschil tussen die twee punten, buiten de score? Als er namelijk wel een relatie is, zou je daar mogelijk een heuristiek voor kunnen verzinnen. (alhoewel ik eerlijk toe moet geven dat dat een beetje onpraktisch is met 1000 dimensies...)

[shdx]

Klopt het volgende: als punt x gemeten is en punt y ligt daar dichtbij, dan weten we y redelijk goed te voorspellen. Als nu ook meting z wordt gedaan en z ligt ook in de buurt van y (maar wat verder weg van x), dan is y nog beter te voorspellen?
In een voorbeeld: punt x ligt op (1, 0) en heeft een gemeten score 6. Punt y ligt op (2, 0) en heeft een voorspelde score van 6. Punt z wordt nu gemeten: het punt ligt op (3, 0) en heeft een gemeten score van 7. De voorspelde score van y wordt nu bijgesteld naar 6.5.

Wat ik me in het 2D voorbeeld kan voorstellen is dat je een heat map maakt op basis van alle gemeten punten. Dat kan bijvoorbeeld door op basis van afstand de omliggende punten wat warmer te maken. Vervolgens kun je met deze map de punten selecteren die in de koele velden liggen, want dat zijn de punten waar je nog informatie over mist. Dat klinkt overigens makkelijker dan dat het daadwerkelijk is: het bepalen welk veld het meeste informatie oplevert is weer een nieuw vraagstuk. Een koel veld met meerdere punten is waarschijnlijk beter om eerst te onderzoeken dan een veld waar maar een punt in ligt. Ik heb echter wel het gevoel (lees: geen garanties) dat hier wel wat leuke heuristieken voor te vinden zijn.

[Verwijderd]

Zoijar schreef op donderdag 25 juli 2013 @ 12:45:
[...]

Curse of dimensionality is een probleem bij duizend-dimensionale data (i.e. vrijwel alle punten zullen aan de rand liggen en relatief ver van elkaar)... dimensionality reduction is niet zo'n gek idee.

True ... al zou je de cost/score van ieder punt binnen 1 plane wel moeten kunnen berekenen en daarna de afstand van de planes op zich kunnen berekenen ... maar het blijft een abstract concept dat heel moeilijk in 1 algoritme te omvatten is.

[MSalters]

Ik negeer even voor het gemak de verdeling van punten in een dimensie, en neem aan dat ze op 0 of 1 liggen. In 1000 dimensie heb je dan conceptueel een hyperkubus met 2[super]1000[/] hoekpunten en 2[super]2000[/] diagonalen. Jouw duizenden punten en duizenden gemeten diagonalen zijn een onvoorstelbaar kleine fractie hiervan.

Zelfs als we de duizend dimensies negeren is er nog een tweede probleem. Je hebt per punt maar een paar afstanden bekend, dus circa 99% van de afstanden zijn onbekend. Al had je maar 20 dimensies, en was het systeem in elk geval lokaal linear (maar wel anisiotroop), dan nog had je nog geen betrouwbare schatting van de bijdrage van elke dimensie.

Is je ruimte uberhaupt wel zo gestructureerd dat de driehoeksongelijkheid houdt? (Maw, is cost(AB)+cost(AC) > cost(AC) ? )

[Verwijderd]

Coca-Cola schreef op donderdag 25 juli 2013 @ 12:39:
Hoe belangerijk zijn die 1000 dimensies? Je kan eventueel met iets als PCA het aantal dimensions vrij sterk reduceren en dan kan je misschien wat eenvoudiger met een meer brute force algoritme aan de slag. Tijdens mijn afstuderen had ik ook >1000 dimensionale data en kon dit met behoudt van 95% van de variantie terugbrengen tot enkele 10 tallen dimensies.

Bedankt allemaal voor de reacties. Om met het vraagstuk van het aantal dimensies te beginnen: PCA kan het aantal dimensies wel flink reduceren. De explained variance van de eerste 2 principal components ligt typisch zo rond de 20%, van de eerste 10 zo rond de 60%, voor 95% zijn toch 100+ principal components nodig. Het is inderdaad geen slecht idee om een optimalisatiealgoritme te draaien op een projectie op principal components in plaats van op de originele data.

Er is geen relatie tussen 2 punten? Als in, tussen punten (1,0) en (1,1), wat is het verschil tussen die twee punten, buiten de score? Als er namelijk wel een relatie is, zou je daar mogelijk een heuristiek voor kunnen verzinnen. (alhoewel ik eerlijk toe moet geven dat dat een beetje onpraktisch is met 1000 dimensies...)

Het was een simplificatie om te zeggen dat er geen relatie is tussen de punten (en dus hun combinaties). Die is er wel degelijk, maar die relatie is zeer complex en slechts in bepaalde gevallen terug te brengen tot verschillen binnen een of enkele dimensies. Met het algoritme dat ik nu probeer te bouwen wil ik niet die kant op gaan, maar juist dat hele probleem proberen te omzeilen.

Klopt het volgende: als punt x gemeten is en punt y ligt daar dichtbij, dan weten we y redelijk goed te voorspellen. Als nu ook meting z wordt gedaan en z ligt ook in de buurt van y (maar wat verder weg van x), dan is y nog beter te voorspellen?
In een voorbeeld: punt x ligt op (1, 0) en heeft een gemeten score 6. Punt y ligt op (2, 0) en heeft een voorspelde score van 6. Punt z wordt nu gemeten: het punt ligt op (3, 0) en heeft een gemeten score van 7. De voorspelde score van y wordt nu bijgesteld naar 6.5.

Dit klopt inderdaad, hoewel het gaat om combinaties van punten en niet om de punten an sich, maar het concept blijft hetzelfde. Je oplossing is interessant, maar ik vrees dat (Zoals MSalters aanstipt) de ruimte wel heel erg leeg is.

Zelfs als we de duizend dimensies negeren is er nog een tweede probleem. Je hebt per punt maar een paar afstanden bekend, dus circa 99% van de afstanden zijn onbekend. Al had je maar 20 dimensies, en was het systeem in elk geval lokaal linear (maar wel anisiotroop), dan nog had je nog geen betrouwbare schatting van de bijdrage van elke dimensie.

Is je ruimte uberhaupt wel zo gestructureerd dat de driehoeksongelijkheid houdt? (Maw, is cost(AB)+cost(AC) > cost(AC) ? )

Om met de laatste vraag te beginnen: ja.

Het klopt dat slechts van zo'n 0,1% tot 1% van alle mogelijke combinaties de score experimenteel bepaald is, dat is de kern van het hele optimalisatieprobleem. Zelfs zeer onbetrouwbare schattingen zijn echter nog beter dan at random combinaties uitproberen.

Verder, op zich is het geen doel om de bijdrage van elke dimensie te schatten, toch? In die hoeken van de ruimte waar simpelweg geen punten liggen, hoef ik ook geen schatting te krijgen. Het feit dat PCA wel enigzins werkt om het aantal dimensies te reduceren, geeft aan dat zulke hoeken er wel degelijk zijn.