Algoritme (uit)gevonden, wat nu?

[analog_]

Ik denk dat het punt is dat hij de ELO oplossing of whatever er uit zijn initiele ranking algo kwam niet overeenstemde met wat hij wou zien (omdat de assumpties veranderd zijn wie sterker is dan wie), netto kan je stellen dat de ranking metric is aangepast zodanig dat het klopt met zijn idee wie hoger moet staan dan wie in bepaalde gevallen.

Dat er niet is nagedacht over alle andere gevallen is vrij duidelijk en toont ook aan wat er mist in het algoritme. Dit los je op door bijvoorbeeld met een 5 tal teams alle mogelijke uitslagen uitstippelen en deze rankings geven, vervolgens oordeel je de rankings, voorzie ook een tie-breaker algoritme (alphabetisch rang, numerisch rang, nullify uitslag, ...)

Ik denk dat je best eens naar bayes netwerken kijkt, hiermee zou je wetenschappelijker je metric kunnen uitdrukken. Dit wordt normaliter gebruikt voor kansberekening, echter heb jij geen onzekerheidsfactor dus iets is 1 of 0, en geen percentage kans. Je kan vervolgens dit overigens weer misbruiken om voorspellingen te doen met alle beschikbare data die je hebt. Je voegt toekomstige uitslagen toe aan je data met voorspellingen met een algoritme (bv. iets stoms: wie ever meer wins heeft, wint ... met 70% kans).

Wat je beschrijft is mogelijk 'nieuw' als algoritme, het is niks fundamenteels nieuws in de wetenschappelijke zin dat het een patent waardig is. Vanuit commercieel standpunt moet je zelf zien, ik denk het niet.

[ Voor 41% gewijzigd door analog_ op 13-11-2012 02:33 ]

[enomiss]

Ik kan het enthousiasme van de TS begrijpen. Echter, ik ben bang dat hij de realiteit niet onder ogen ziet.

Het is geen verschrikkelijk moeilijk materie. Je kan het wel verschrikkelijk moeilijk maken afhankelijk van welk probleem je wil oplossen. Jouw probleem is relatief simpel. Je wil een feitelijke sortering zonder al te diep te kijken wat je hieraan voor waarde kan hechten.

Ik heb ook eens zo een relatief simpel algoritme bedacht voor een soort van competitie voor een game die ik fanatiek speelde. Toen in Excel gestopt en ik zag duidelijk dat de beste spelers naar voren kwamen. Een half dagje puzzelen was het. Voldeed waar het voor nodig was.

Jouw algoritme maakt een pure feitelijke sortering van onderlinge relaties, en uiteindelijk plaats je de een boven de ander. Oke, leuk als je dit als resultaat wil, maar ieder sport heeft al zijn ranking systeem. Die voldoen.

De zogenaamde verschrikkelijk moeilijke algoritmes gaan een stuk verder. Algoritmes die echt waarde hebben zijn voorspellende algoritmes. Daarbij is het niet vanzelfsprekend wanneer A altijd van C wint, en B altijd van A verliest, dat B niet van C kan winnen. Denk aan spelers welke elkaars tactiek of manier van spelen niet liggen. Met relaties alleen ben je er dus niet. Over langere periodes kun je gemiddeldes nemen over de vorm, type spelers, stabiliteit etc. En om maar niet te spreken over de factor tijdsbestek, groei of afbrokkeling van bepaalde 'spelers'. Binnen een week kan een speler de top speler gepasseerd zijn in werkelijke skills. Ook al komt dit nog niet naar voren in de statistieken. Pas als je een voorspellend algoritme bedenkt, dan wordt het echt interessant. En dan weet ik zeker dat de miljoenen klaar liggen bij het honkbal of bij Google om maar iets te noemen. Zo een simpel algoritme van de TS is al 1000x bedacht en zit vast en zeker al op genoeg plekken in code.

Overigens bij jouw probleem zie ik een vreselijke poll voor me:
Welke film vind je beter?
A of B?
A of C?
A of D?
B of C?
B of D?
etc.
Gelukkig werkt IMDB niet zo, en zijn er geen relaties maar gewoon stemmen. Simpel. Dus voor welk specifiek probleem is jouw ding nou een oplossing? Voor een te ingewikkelde poll?

[ Voor 7% gewijzigd door enomiss op 13-11-2012 05:16 ]

[Kayr]

Mooi verhaal op je site Ik moest zoals wel meer posters (denk ik) bij het eerste plaatje ook direct aan de grafentheorie denken. Zal nu eerst eens verder lezen, maar voor mijn gevoel zit hier wel een verband.

Leuk project en interessant dat je het met ons wilt delen

Oja, dit is wat er ook nog in me opkwam: http://nl.wikipedia.org/wiki/Transitieve_afsluiting oftewijl, gewogen gerichte graaf.

[ Voor 20% gewijzigd door Kayr op 13-11-2012 17:26 ]

[shdx]

Om te kunnen beslissen of je algoritme echt nieuw is, is het denk ik handig om het algoritme in wat meer globale termen samen te vatten. Laat ik het eens iets proberen. Even wat terminologie: de afbeelding op je site noemen we een graph. De graph bestaat uit nodes (de rondjes) en edges (de lijntjes/pijltjes). Elke edge heeft een gewicht (bijv. 1 of -1). Een indirect pad tussen node u en v, bestaat uit drie nodes, u, x en v waarvoor geldt dat (u, x) en (x, v) edges zijn.

Wat ik nu opmaak uit de tekst op je website is dat je een score tussen twee nodes (bijv. film A en film B.) probeert te berekenen. Deze score, S(u, v), voor het berekenen van de score S tussen node u en v, waarbij u!=v, gaat als volgt:

1. Neem het gewicht tussen node u en v
2. Voor elk indirect pad tussen u en v: sommeer over de gewichten tussen nodes (u, x) en (x, v)
3. Tel alle gesommeerde gewichten van de indirecte paden tussen u en v bij elkaar op
4. Middel het getal uit stap 3 over het aantal indirecte paden
5. Sommeer de getallen uit stap 1 en 4

Uiteindelijk wordt er ook nog wat normalisatie uitgevoerd op de scores. De vraag is nu of je algoritme daadwerkelijk nieuw of origineel genoeg is om wat mee te doen, zoals patenteren. Je algoritme moet het denk ik vooral hebben van het meenemen van indirecte paden in de berekening van een score. Hierbij moet opgemerkt worden dat het gebruik van indirecte paden met 1 extra node (dat wil zeggen: u -> x -> v) een beperking is van je algoritme; het is vrij simpel om dit algoritme uit te breiden om rekening te houden met indirecte paden met meerdere nodes (bijv. u -> x -> y -> v). In je zoektocht naar andere werken zul je rekening moeten houden dat andere algoritmes waarschijnlijk meer generiek zijn opgesteld. Ook bij het middelen van de gewichten over het aantal indirecte paden zul je rekening moeten houden met een generieke aanpak; middelen kan gezien worden als het vermenigvuldigen met een variabele, waarbij deze variabele bij jou toevallig ingesteld is op 1/K.

Ik denk dat je er veel voordeel van zal hebben om je algoritme wat meer formeel uit te schrijven. Dat zal de zoektocht naar andere algoritmes die ongeveer hetzelfde doen vergemakkelijken. Als ik zo naar je algoritme kijk denk ik niet dat je iets nieuws te pakken hebt. Ik kan helaas niet naar een algoritme wijzen dat hetzelfde doet, maar het algoritme komt vrij simpel over; ik verwacht dat je algoritme al eens is gebruikt. Overigens zie ik geen overeenkomst tussen jouw algoritme en de genoemde algoritmes in dit topic.
De toepassing van je algoritme is een ander verhaal. Misschien is nog niemand op het idee gekomen om zo'n algoritme te gebruiken voor een ranking in (sport)wedstrijden. In dat geval heb je op dat gebied iets nieuws te pakken. Wat je dan met je vinding moet doen, durf ik niet te zeggen. Patenteren is, zoals je zelf al aangeeft, erg duur. Je verwacht die kosten er dan toch uit te kunnen halen. Een mooie uitwerking van je algoritme met daarbij de nodige resultaten en vergelijkingen met andere algoritmes, zou een goede eerste stap zijn. Toon maar aan dat jouw algoritme goed werkt, of zelfs beter dan andere algoritmes in het maken van een ranking.

Wat betreft complexiteit scoort je algoritme niet heel goed. Je berekent voor elke node (u, v) in de graph een score, waarbij je ook naar alle indirecte links kijkt. Voor een fully connected graph bereken je n*n scores. De complexiteit is dus O(n²). Dit betekent dus dat je voor grotere graphs heel veel meer rekentijd nodig gaat hebben.

[Herko_ter_Horst]

Wie weet is het wel beter dan het PageRank algo van Google...

[H!GHGuY]

Om op de TS zijn oorspronkelijke vraag terug te komen:

Er zijn projecten waarbij je je idee kan publiceren, zodat ze later niet door iemand anders gepatenteerd kunnen worden.
Zie bijvoorbeeld:
http://www.researchdisclosure.com/
http://www.ip.com/

[Tarilo]

Sjoerd_87 schreef op maandag 19 november 2012 @ 17:51:
Wall of text

QFT!

Vooral de laatste alinea is een heel belangijk punt als het om algoritmes gaat. Er zijn(kort door de bocht) twee punten die van groot belang zijn bij een algoritme:

• Het produceert een correcte oplossing
• Het is snel

Als je iets wilt kunnen zeggen over je algoritme zul je in ieder geval deze twee punten duidelijk moeten hebben. Het is dus, zoals hierboven ookal aangegeven, van belang dat je een goede generieke omschrijving hebt van je algoritme. Daarnaast zal je moeten onderzoek hoe snel je algoritme is, dit gebeurt aan de hand de Big-O notatie.

Als bovenstaande punten duidelijk zijn kun je wat zinnigs gaan zeggen over de waarde van het algoritme. Immers is een algoritme dat niet altijd de correcte oplossing produceert zo goed als waardeloos, maar ook als je algoritme altijd de correcte oplossing vindt is het niet direct goud waard. Als je algoritme er namelijk 2-3 keer zolang over doet om het antwoord te vinden dan een vergelijkbaar algoritme, heb je er eigenlijk ook niet zoveel aan.

[.oisyn]

Niet alleen performance, ook geheugengebruik is van belang. Een algoritme dat in O(n) een antwoord kan vinden maar ondertussen wel O(n!) geheugen nodig heeft schaalt ook voor geen meter.