Patroonherkenning

Moderators: dirkwb, Xilvo

Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
Reageer
Berichten: 7

Patroonherkenning

Hallo allemaal!

Ik heb het onderwerp maar patroonherkenning genoemd, maar misschien valt mijn vraag wel in een andere categorie.

Stel ik heb een serie van n opeenvolgende tijdsduurwaarnemingen:

dt-1, dt-2, dt-3, dt-4, ...., dt-n

De gemeten tijdsduur is stochastisch. Misschien is er ook sprake van autocovariantie tussen de waarnemingen.

Al ik 2 series van n waarnemingen met elkaar vergelijk, hoe kan ik dan de mate van (on)gelijkenis berekenen/uitdrukken?

wezeltje

Berichten: 2

Re: Patroonherkenning

Je hebt dus 2 stochastische processen, X1(t) en X2(t).

De auto-covariantie van X1(t) met tijdstip t+t' is bepaald als:

C(t,t') = E[X1(t),X1(t+t')] = E[X1(t)X(t+t')]-E[X(t)][X(t+t')]

De auto-covariantie van X1(t) met zichzelf op tijdstip t+0 is uiteraard de variantie van het stochastische proces.

De auto-correlatiefunctie is bepaald als:

R(t,t') = E[X1(t)X(t+t')]

Als je de 2 auto-correlatiefuncties plot kan je misschien overeenkomsten vinden. Dit kan heel makkelijk met Matlab.

Bovenstaande is alleen geldig als het proces een IID proces is, dus:

Independent, Identically Distributed.

Berichten: 7

Re: Patroonherkenning

Hoi Temples,

Dankjewel voor je reactie. Ik weet hoe je auto-covariantie kunt uitrekenen.

Mijn vraag gaat echter verder.

Stel je hebt een afbeelding van een gezicht. Je doet een tiental metingen: breedte mond, afstand oor tot oor, etc. Mijn vraag heeft betrekking op de methode waarmee je twee gezichten (twee meetseries) met elkaar kan vergelijken. Ook hier zijn de metingen stochastisch. Ook hier is waarschijnlijk sprake van autocovariantie.

En in mijn probleem is het aantal meetpunten overigens ook gering.

Berichten: 2

Re: Patroonherkenning

Dan vind ik dat er in dit geval niet echt sprake is van een stochastisch proces, maar van een grote dataset van afbeeldingen met verschillende features, zoals:

- breedte mond

- oor tot oor afstand

- breedte wenkbrauwen

Als je van al deze afbeeldingen deze features berekent kan je daar wellicht datamining technieken op loslaten, aangezien het dan allemaal unieke onafhankelijke realisaties zijn.

Mag ik vragen waar je de auto-covariantie op los wilde laten? Misschien dat ik het bij het verkeerde eind heb, en dat ik dan beter begrijp wat je met de covariantie wilt doen.

Berichten: 7

Re: Patroonherkenning

Heb ik gesproken van een proces? Met stochastisch bedoelde ik dat een waarneming van een element in de serie aan onzekerheid onderhevig is. Misschien gebruik ik het verkeerde begrip.

Waarom richt je je aandacht zo op die auto-covariantie?

Nog een voorbeeld?

Het is algemeen bekend dat koeien uitzonderlijk muzikale solisten zijn: elke koe loeit met een vrij uniek ritme BOE. Met ritme bedoel ik de opeenvolgende tijdsintervallen tussen 2 BOEs. Het patroon herhaald zich steeds na 10 BOEs opnieuw. Het is ook algemeen bekend dat meteen na het melken zo'n serie van BOEs nieuw begint.

In een aanloopfase is van elke koe steeds na het melken een aantal van de series van 9 tijdsintervallen gemeten, waarbij de identiteit van de koe bekend was. Een referentie reeks is bepaald door van elke koe het gemiddelde van waargenomen 1ste tijdsintervallen te nemen, tot en met een gemiddelde voor het 9de tijdsinterval.

We willen de koeien na het melken identificeren met meer zekerheid dan "op zicht" alleen. We meten de 9 tijdsintervallen tussen 10 BOEs. We vergelijken de gemeten serie met de referentie serie van de op zicht geidentificeerde koe. Het probleem is nu: wanneer zeggen we dat de gemeten serie overeen komt met referentie serie?

Misschien wisten jullie het al, maar voor de zekerheid: als het warm weer is dan zijn alle tijdsintervallen wat langer dan wanneer het koud het. Het patroon blijft echter vrij stabiel.

Berichten: 336

Re: Patroonherkenning

je variabelen zijn de tijd tussen 2 boes van de koe die je aan het meten bent, de kans dat de eerste boe die je hoort niet de eerste boe van de serie is laten we buiten beschouwing. We noemen de tijden tussen de boes : X1,X2,X3,,X9.

Je hebt van alle koeien van deze serie t_boe1,t_boe9 al bepaald, met een standaarddeviatie s_t_boe1,s_t_boe2, enz....(nisschien niet nodig want poisson)

Je hebt nu een meting:x1,x2,,x9

Je maakt een prior: het kan elke koe zijn.

Dus: P(Koe_i)=1/n_koeien

Je bepaalt de kans voor iedere koe dat gegeven deze koe zijn geproduceerde patroon X1,,X9 is. -> P(X1,,X9 | koe_i)



De kans op een koe gegeven je stochasten is nu P(koe_i ^ X1,,X9)=P(X|Koe_i)*P(koe_i).

Doe koe met de grootste kans is nu je most likely koe!

Dat is de Bayesian aanpak, dat zullen de frequentisten onder jullie misschien minder leuk vinden. IIg succes.
Duct tape is like the force: it has a dark side, a light side and it holds the universe together.

Berichten: 664

Re: Patroonherkenning

wezeltje schreef:Het probleem is nu: wanneer zeggen we dat de gemeten serie overeen komt met referentie serie?

Misschien wisten jullie het al, maar voor de zekerheid: als het warm weer is dan zijn alle tijdsintervallen wat langer dan wanneer het koud het. Het patroon blijft echter vrij stabiel.
De eerste boe van ieder patroon (of de gehele lengte van het boe patroon) nemen als referentie voor de volgende boe's, dus boe1 = 1, boe2 = a*boe1, ......

Als beste match, zou ik dan het boe-patroon (koe-x) uit de database nemen die de kleinste som van absolute tijdsduurverschillen met de waargenomen boe heeft.

Zoiets?

Berichten: 7

Re: Patroonherkenning

sirius schreef:Je hebt nu een meting:x1,x2,,x9  

Je maakt een prior: het kan elke koe zijn.

Dus: P(Koe_i)=1/n_koeien

Je bepaalt de kans voor iedere koe dat gegeven deze koe zijn geproduceerde patroon X1,,X9 is. -> P(X1,,X9 | koe_i)

 

De kans op een koe gegeven je stochasten is nu P(koe_i ^ X1,,X9)=P(X|Koe_i)*P(koe_i).

Doe koe met de grootste kans is nu je most likely koe!


Hartstikke bedankt; volgens mij gaat het de goede richting op!

Ik heb toch nog vragen:

* Wat is een Prior?

* Ik ben niet geinteresseerd in de koe met de grootste likelyhood, maar wanneer ik gelijkenis zou moeten verwerpen, gegeven de randvoorwaarde dat de kans op een foutieve verwerping kleiner is dan x procent.

* Ik dacht het niet meteen al te ingewikkeld te maken (althans wat mijzelf betreft), maar aanvankelijk zijn er maar enkele koeien in de populatie. Die zal in de tijd wel snel groeien.

Berichten: 7

Re: Patroonherkenning

Chriis schreef:De eerste boe van ieder patroon (of de gehele lengte van het boe patroon) nemen als referentie voor de volgende boe's, dus boe1 = 1, boe2 = a*boe1, ......

Als beste match, zou ik dan het boe-patroon (koe-x) uit de database nemen die de kleinste som van absolute tijdsduurverschillen met de waargenomen boe heeft.

Zoiets?
Volgens mij ga jij er al van uit dat er sprake is van covariantie tussen opeenvolgende waarnemingen, of niet. Dat lijk mij niet juist.

Berichten: 664

Re: Patroonherkenning

wezeltje schreef:
Chriis schreef:De eerste boe van ieder patroon (of de gehele lengte van het boe patroon) nemen als referentie voor de volgende boe's, dus boe1 = 1, boe2 = a*boe1, ......

Als beste match, zou ik dan het boe-patroon (koe-x) uit de database nemen die de kleinste som van absolute tijdsduurverschillen met de waargenomen boe heeft.

Zoiets?
Volgens mij ga jij er al van uit dat er sprake is van covariantie tussen opeenvolgende waarnemingen, of niet. Dat lijk mij niet juist.
Ik begrijp je niet helemaal, bedoel je die eerste regel (over referentie)? Dat was enkel bedoelt om de eventuele temperatuur afhankelijkheid eruit te halen.

Ik dacht dat je op zoek was naar een methode om de patronen met elkaar te vergelijken, een mate van gelijkenis te bepalen. -> Als beste match, zou ik dan het boe-patroon (koe-x) uit de database nemen die de kleinste som van absolute tijdsduurverschillen heeft, in vergelijking met de waargenomen boe. Dus min(som(abs(tki - tli))) met som over alle i, en tki, tijdsduur tussen boei en boei+1 van patroon k.

Berichten: 7

Re: Patroonherkenning

Chriis, je hebt helemaal gelijk. Ik heb die correctie niet meteen doorzien in de gauwigheid.

Ik vind het moeilijk te beoordelen of jouw oplossing in deze vraagstelling de beste is. Je corrigeert voor een afwijking in de eerste tijdsduur, terwijl die afwijking grotendeels toevallig kan zijn. Je kiest voor de kleinste-kwadraten en gaat daarmee voorbij aan mogelijke covarianties. Anderzijds kan ik me ook voorstellen dat er gezien de aard van het probleem geen andere oplossing is.

Berichten: 664

Re: Patroonherkenning

Je corrigeert voor een afwijking in de eerste tijdsduur, terwijl die afwijking grotendeels toevallig kan zijn.
Ja, dat is idd zo. Daarom leek het mij misschien ook beter om de lengte van het gehele patroon te normaliseren, ipv de eerste boe. Verder weet ik niet precies hoe en hoeveel het patroon kan variëren. Dit was het eerste wat mij te binnen schoot, ik ben zelf namelijk meer bezig geweest met video, frame-interpolatie, mpeg, motion compensation/estimation, etc..

Berichten: 7

Re: Patroonherkenning

Nou dan begrijp ik je goed.

Zou het i.p.v. de hele serie te corrigeren voor de afwijking van de eerste tijdsduur dan niet beter zijn om naar de afwijking in de som van tijdsduren te kijken, en daarvoor alle tijdsduren te corrigeren?

Ik hoop dat Sirius ook nog iets van zijn Bayesiaanse aanpak kan toelichten; ik snap er niets van.

Berichten: 664

Re: Patroonherkenning

Zou het i.p.v. de hele serie te corrigeren voor de afwijking van de eerste tijdsduur dan niet beter zijn om naar de afwijking in de som van tijdsduren te kijken, en daarvoor alle tijdsduren te corrigeren?
Het is soms lastig als je niet even een paar tekeningetjes kan maken. Maar ik denk dat wat jij hier zegt ook wel is wat ik bedoel.

Laten we als voorbeeld even een kort patroon nemen van lengte 3.

'Normaliseren':

bv: [2,4,1] totale 'lengte' = 2+4+1 = 7. Dus normaliseren -> [2/7,4/7,1/7].

Met warm weer wordt dit patroon iets 'langer' dus b.v.: [4,8,2] lengte 14, normaliseren levert nu ook weer [2/7,4/7,1/7].

Iets anders:

Misschien dat in langere pauzes meer variatie zit, b.v.: [2±1,4±2,1±1/2]. Dan zijn de fouten die in de langere pauzes gemaakt worden dus groter. Dan lijkt het me beter om de fouten te wegen, door b.v. de gemeten fout te delen door de verwachte lengte van de pauze -> meer variatie toestaan bij langere pauzes.

Misschien kan je de pauzes quantiseren, b.v. lang-middel-kort.

Dus [2,4,1] -> [m(iddel),l,k]

Ik weet niet hoeveel 'afstand' er tussen de patronen van de verschillende koeien zit, dat heeft natuurlijk wel invloed op de prestatie van deze methode.

Reageer