Wiskundige gezocht voor kansrekening binnen hobbyproject

[Kaw]

Update over de stand van zaken... Hij is nog erg traag en ongeoptimaliseerd, maar ik ben blij met de resultaten.
http://www.maximumcompression.com/data/text.php op deze site zou mijn programma bij dit bestandje op de 29e plaats komen te staan. Hij wist het te comprimeren naar 448,420 bytes.

Het is wel geinig. Nog elke dag vind ik methodes om de zaak verder te optimaliseren.

[jakobmarin]

Jan Sloot had ook een flinke compressie bedacht, zie http://www.debroncode.nl, maar overleed te vroeg om er iets mee te kunnen doen....

[GAB]

Jan Sloot had ook een flinke compressie bedacht, zie http://www.debroncode.nl, maar overleed te vroeg om er iets mee te kunnen doen....

Dit topic is al redelijk oud, maar Jan Sloot had ook resultaten die theoretisch onmogelijk waren, en heeft zijn familie met een aardig zakcentje nagelaten door zijn fraude...

[jakobmarin]

Dit topic is al redelijk oud, maar Jan Sloot had ook resultaten die theoretisch onmogelijk waren, en heeft zijn familie met een aardig zakcentje nagelaten door zijn fraude...

of het fraude was, kun je natuurlijk niet weten. Roel Pieper (ook geen domme man) was er van overtuigd dat het waar moest zijn, en nog steeds.
Zie ook dit document, waar een kenner aangeeft dat het best zou moeten kunnen: http://www.debroncode.nl/images/files/B ... oncode.doc

[Kaw]

Er is wel een theoretisch minimum. Er bestaat een zogenaamd Kolmogorov Complexity. Een minimum van informatie die nodig is om iets weer te geven. Stel je voor dat die regel er niet was. Dan zou je alle informatie terug kunnen brengen naar een 1 of een 0. Dat kan niet, want met 1 'bit' informatie kun je alleen maar vast stellen of het een 1 of een 0 was. Stel je voor dat je de pincodes op wil slaan. Er zijn 10.000 verschillende pincodes. Je hebt grofweg een minimum van 13,5 bits nodig om dat op te slaan en geen informatie te verliezen.
Met films is het zelfde. Je zou het menselijk terug kunnen brengen tot een uitgebreide beschrijving van een scenario. Die beschrijving zal langer zijn dan 16.000 of 32.000 karakters. Toch zal de computer kennis moeten hebben hoe de omgeving er uit ziet waar die film zich afspeelt. Ook zal de computer een uitgebreide kennis moeten hebben van de acteurs om die in die omgevingen te verwerken. Dan moet de computer de geluiden aan de hand van het scenario er nog inpassen. Nee, het lukt niet met 32.000 tekens, maar volgens Jan Sloot kan dat wel. Met een beetje nuchterheid kun je zelf afleiden dat het onmogelijk is.

[jakobmarin]

@Kaw: als jij dat zo nuchter kunt bedenken dat het onmogelijk is, waarom zou iemand als Roel Pieper daar dan zijn geld in stoppen?

[GAB]

@Kaw: als jij dat zo nuchter kunt bedenken dat het onmogelijk is, waarom zou iemand als Roel Pieper daar dan zijn geld in stoppen?

ik denk dat Roel Pieper zichzelf daarna ook aardig voor het hoofd heeft geslagen, maar om wat minder met gevoelens en wat meer met data te komen:
http://www.data-compression.com/theory.html
http://tweakers.net/nieuws/35515/rappor ... sloot.html

in die laatste gaat het ook over Andrey Kolmogorov, die door Kaw genoemd werd.

[Kaw]

Als je de beschikbare informatie rondom Jan Sloot goed doorleest, dan vallen er een hoop puzzelstukjes op zijn plek. Hij had een soort verzamelbestand. Dit bestand, ongeveer 300-400 mb groot, was een soort van bron-bestand waar een indexbestand naar verwees. Hij noemde dat indexbestand(je) van 16kb of 32kb (ik weet niet precies meer de grootte) de film. Je hoeft alleen dat indexbestandje te distribueren en men hoeft maar eenmaal dat bronbestand binnen te halen om via het indexbestandje de hele film te kunnen zien. Dat is helemaal waar. In computerland noemen we dat caching.

Stel dat je TV een computer was. Je krijgt een indexbestandje van de zender waarin staat dat reclame 1243 gezien moet worden. De computer kijkt in zijn verzamelbestand naar reclame 1243 en toont die. Voila. Als er nieuwe reclames uitkomen, dan moet het verzamelbestand aangevult worden. Ondertussen hoeft niet steeds weer de reclame gedownload te worden en zoals de TV-bezitters weten wordt reclame veel herhaalt, dus al na 8 keer de reclame tonen heb je meer compressie berijkt dan wat volgens die rus met zijn complexiteit theorie mogelijk is.

Jan Sloot hield zichzelf voor de gek en daarmee ook meneer Pieper. Jan vulde zijn verzamelbestand met de informatie wat hij wilde laten zien. Gewoon een bepaald opslagmedium in dat portable pc'tje van hem en doormiddel van een geheugenkaartje waar een indexbestandje op stond werd de bijbehorende informatie uit het grote bestand gelezen en getoont. Waarschijnlijk was dat verzamelbestand ingewikkeld ingericht, zodat hij zichzelf kon overtuigen dat het niet zomaar de film zelf was en is het hem gelukt om dubbele frames (bijv. momenten met volledig zwart beeld) niet dubbel, maar éénmaal op te slaan. Dat verzamelbestand bestond uit unieke frames en het indexbestand maakte van die frames weer de film zoals je die wilde zien. Best knap voor iemand die geen informatica-achtergrond heeft. Helaas niet een wonderalgoritme.

[Kaw]

Ik denk dat een update wel op zijn plaats is. Inmiddels ben ik ook lid van het forum van encode.ru. Daar zitten de beste programmeurs op dit gebied met elkaar te kletsen wat een nieuwe strategie kan zijn. Daar en ook in de praktijk ben ik er achter gekomen dat Bayes alleen op zichzelf niet voldoet. In redelijk wat gevallen heb je bijvoorbeeld een patroon herkent die 1 keer eerder voor komt in het bestand. Dit patroon geeft aan dat de volgende bit bijv. een 1 is. Er is 1 patroon, dus volgens dat patroon weet je 100% dat het een 1 is. Bayes flipt dan meteen naar P = 1 en komt daar niet meer vanaf. Als dat patroon nu 10.000 keer eerder voor kwam en in alle 10.000 gevallen een 1 opleverde, dan zit je dicht bij de P = 1, maar door 1 patroon kun je dat niet zeggen en zit je eerder bij P = 0.51 ofzo.

Ik heb inmiddels heel wat studie gemaakt over dit onderwerp en weet dat ik op zoek ben naar 'confidence' regels. Ik moet bepalen hoeveel vertrouwen ik heb in een bepaalde meting. Dat vertrouwen kan ik bepalen door de mediaan te berekenen en de daarbij behorende afwijken enz., maar dat gaat niet op bij een Binomiale verdeling. Wat zijn de 'confidence' regels voor een Binomiale verdeling? Encode.ru helpt me daarbij niet verder. De programmeurs daar bepalen de confidence op basis van bevinding en dat gaat goed in hun gevallen, omdat ze werken met een beperkt aantal types metingen. Ik heb een virtueel onbeperkt aantal metingen per inschatting die redelijk vaak maar 1 keer optreden en daardoor kan ik niet op basis van de geschiedenis een beetje gaan schatten wat de confidence is over een bepaalde enkelvoudige meting.

Het is wel complex. Stel dat je twee patronen hebt. Patroon 1 is een match van 5 bytes en patroon 2 is een match van 15 bytes.
Patroon 1 levert 10 keer een 0 op en 5 keer een 1 en patroon 2 levert 10 keer een 1 op en 5 keer een 0. Ze hebben niet dezelfde confidence, want patroon 2 is zeldzamer en geeft een grotere kans op een goed antwoord dan patroon 1. Ik moet niet alleen rekening houden met het aantal keren dat een bepaald patroon optreed, maar ook met zijn eigen verdeling (hoeveel 1en en 0en levert een bepaald patroon op? Bijv. 30% 1en en 70% 0en) en hoe 'zeldzaam' een patroon is. De eerste 2 eigenschappen kan ik zo berekenen, maar hoe meet ik de zeldzaamheid van een patroon? En hoe vormt dat gezamelijk een bepaalde confidence?

[Kaw]

Antwoord gevonden. De Wilson score interval kan ik gebruiken. Heb al een C# implementatie gemaakt.