Rss

  • linkedin

Archives for : algoritmi

Etäisyydet puolueista vaalikoneessa

Helsingin Sanomien vaalikoneen ympärille syntyi pientä hässäkkää kun kansanedustaja Jyrki Kasvi huomasi, ettei hän nouse äänestäjän suosituslistalla ylimmäksi, vaikka äänestäjä vastaisi kaikkiin kysymyksiin täsmällisesti samoin kuin itse Kasvi.

Hesari lähti julkisesti avaamaan tätä ilmiötä ja selvisi että Jyrki Kasvi on Hesarin käyttämän algoritmin mielestä puolueista lähempänä Feministipuoluetta kuin edustamaansa Vihreää liittoa. Ehdokassuositukset taas jäljittelevät Suomen vaalikäytäntöä ja se antaa ensimmäisiksi suosituksiksi parhaat yksittäiset osumat ”lähimmästä” puolueesta ja vasta alempana puolueriippumattomasti lähimmät yksittäiset ehdokkaat. Kohun myötä Hesari tässä kirjoituksessa avasi käyttämänsä algoritmin toimintaa ja tarjosi dataa Uudenmaan vaalipiirin Feministipuolueen sekä Vihreän liiton ehdokkaiden vastauksista.

Seuraavassa esitellään muutamia vaihtoehtoisia tapoja ehdokkaiden sekä puolueiden läheisyyden mittaamiseen, käydään läpi Hesarin algoritmissa tehdyt valinnat ja katsotaan, kuinka Jyrki Kasville olisi käynyt vaihtoehtoisilla algoritmeilla.

Kahden yksittäisen ehdokkaan välinen etäisyys

Ehdokkat vastaavat Hesarin vaalikoneessa 30 kysymykseen, joten ehdokkaiden vastausten välistä etäisyyttä toisistaan mitataan 30-ulotteisessa avaruudessa. Tämä ei suinkaan ole yksiselitteinen tehtävä. Moniulotteisten etäisyyden mittaamiseen on olemassa useita eri mittareita. Näistä tunnetuimmat ovat Euklidinen-etäisyys (katso kaava) ja Manhattan-etäisyys (tai ”taksimetriikka”,katso kaava ja havainnollistus). Kun etäisyyttä mitataan Euklidisella etäisyydellä, peruskoulussa opitut geometrian lait pätevät. Datan analysointi ei kuitenkaan ole eksaktia matematiikkaa. Manhattan-etäisyydellä on se etu, ettei se ole niin herkkä reagoimaan yksittäisiin poikkeaviin havaintoihin.

Alla olevassa kuvaajassa on (kuviteltuna) esimerkkinä kahdelta ehdokkaalta vastaukset kahteen kysymykseen. Ensimmäinen ehdokas on antanut molempiin kysymykseen vastauksen 1 (”Täysin eri mieltä”). Toinen ehdokas on vastannut 1. kysymykseen 4 (”Jokseenkin samaa mieltä”) ja 2. kysymykseen 5 (”Täysin samaa mieltä”). Näiden kahden pisteen euklidinen etäisyys (punainen jana) on 5. Tämän voi varmistaa Pythagoraan lauseen avulla: $3^2 + 4^2 = 25 = 5^2 $. Eli kaikista janoista muodostuvan kolmion kateettien neliöiden summa on sama kuin hypotenuusan neliö. Geometrisessa tulkinnassa on kuitekin muistettava, että siinä täytyy olettaa vastausvaihtoehtojen välimatkat yhtä pitkiksi. Eli esimerkiksi ero ”Täysin eri mieltä” ja ”Jokseenkin erimieltä” välillä on sama kuin ”En osaa sanoa” ja ”Jokseenkin samaa mieltä” välillä.

Kahden pisteellä merkityn ehdokkaan välinen etäisyys eri mittareilla 2-ulotteisessa koordinaatistossa.

Manhattan-etäisyys taas määritellään mustien janojen määrittelemän ”kiertoreitin” pituutena. Tämä on 3 + 4 = 7. Hesari on päätynyt käyttämään vaalikoneen algoritmissaan tätä Manhattan-etäisyyttä kahden yksittäisen ehdokkaan välisen etäisyyden mittaamiseen.

Lopuksi vielä huomio, että kumpikaan esitellyistä etäisyysmittareista ei ota huomioon kysymysten välistä korrelaatiota. Mikäli usea kysymys liittyy samaan teemaan, tämä teema tulee korostumaan myös etäisyysmittarissa.

Etäisyys ryhmästä

Kun kahden ehdokkaan välinen etäisyysmittari on päätetty, pitää seuraavaksi päättää kuinka etäisyys puolueeseen mitataan. Hesari on laskenut etäisyyden jokaiseen puolueen ehdokkaaseen erikseen ja ottanut näistä keskiarvon. Toinen vaihtoehto olisi määritellä ensin puolueryhmän keskipiste 30-ulotteisessa avaruudessa ja laskea sitten etäisyys tähän yhteen pisteiseen. Ryhmän keskipisteenkin voi määritellä usealla eri tavalla, mutta pitäydytään nyt yksinkertaisimmassa: lasketaan kaikkien vastauksien keskiarvo ryhmän sisällä.

Ero usean yksittäisen ehdokkaan etäisyyden laskemisen ja keskipisteen laskemisen välillä on ainakin se, että yksittäisten etäisyyksien tapa rankaisee vaihtelusta puolueen sisällä. Otetaan esimerkiksi kaksi kahden hengen puoluetta. Puolueen 1 edustajat ovat molemmat vastanneet kysymykseen saman vastauksen 2. Puolueen 2 edustajista toinen on vastannut samaan kysymykseen 1 ja toinen 3. Mikäli Jyrki Kasvi olisi vastannut kysymykseen myös 2, etäisyyttä puolueeseen 1 kertyy 0 + 0 = 0. Etäisyyttä puolueeseen 2 taas kertyy 1 + 1 = 2. Molempien puolueiden keskiarvo on kuitenkin sama 2, joten keskiarvoon ei etäisyyttä kerry kumpaankaan puolueeseen lainkaan. Alla oleva taulukko vielä kokoaa yhteen em. esimerkin tulokset.

Puolue Ehdokas1Ehdokas2KAEtäisyys
yksilöihin
Etäisyys
keskiarvoon
Puolue122200
Puolue213220

Yllä olevan eron syntyminen kuitenkin vaatii, että Jyrki Kasvi on vastannut kysymykseen juuri 2. Muilla vastauksilla eroa mittaustapojen välillä ei tässä esimerkissä synny.

Hesari on päätynyt algoritmissaan mittaamaan etäisyyttä yksilöiden etäisyyksien kautta.

Vastausten vaihtelu puolueen sisällä

Kun Hesarin algoritmi mittaa etäisyyttää koko puolueesta tavalla, joka oletettavasti suosii sisäisesti saman mielistä ryhmää, on kiinnostavaa kuinka yhdenmielisiä Feministipuolueen ja Vihreiden jäsenet ovat. Alla olevassa kuvaajassa on lasketty yksittäisen ehdokkaiden vastaajien etäisyydet Manhattan-etäisyydellä. Mitä punaisempi väri, sitä lähempänä kyseiset ehdokkaat ovat toisiaan. Jokainen ehdokkaan etäisyys itsestään on luonnollisesti 0, mikä näkyy punaisena halkaisijana vasemmasta alanurkasta oikeaan ylänurkkaan.

Ehdokkaat 1-10 kuuluvat feministipuolueeseen ja ehdokkaat 11-40 Vihreisiin. Vasemmassa alanurkassa oleva yhtenäinen punainen neliö (tai oikeammin Tanskan lippu yhden yksittäisen sooloilijan ansiosta) kertoo, että Feministipuolueen jäsenet ovat hyvin yhdenmielisiä keskenään. Vihreiden joukossa nähdään sekä punaista että sinistä, mikä viestii vastauksien eroista puolueen sisällä.

Ehdokkaiden etäisyys toistaan Manhattan-etäisyydellä mitattuna. Punainen väri viittaa samankaltaisuuteen ja sininen eroihin vastauksissa.

Tulokset eri mittareilla

Lopuksi kiinnostavaa on, että olisiko tulokset erilaisia, mikäli algoritmin kehityksessä olisi tehty erilaisia valintoja. Nykyinen algoritmi antaa tulokseksi, että Jyrki Kasvin läheisyys Feministipuolueen kanssa on 79.3% ja Vihreiden kanssa 77.4%. Tein laskelmat vaihtoehtoisilla aiemmin tässä blogitekstissä esitetyillä menetelmillä hyödyntäen muilta osin Hesarin käyttämää ajatusta samankaltaisuuden laskemiseen. Tulokset ovat alla olevassa taulukossa. Alkuperäisen menetelmän tulokset ovat vasemmassa ylänurkassa.

Yksilöetäisyys ->
Ryhmämittari
ManhattanEuklidinen
Yksittäiset ehdokkaatFem 79.3%, Vih 77.4%Fem 65.6%, Vih 65.5%
RyhmäkeskiarvoFem 79.8%, Vih 78.9%Fem 67.6%, Vih 71.8%

Ennakko-oletukseni oli, että siirryttäessä mittaamaan ryhmän etäisyyttä ryhmäkeskiarvolla Vihreät menisivät Feministien ohi, koska puolueen sisäisistä eroista ei enää rankaistaisi. Olin väärässä. Todellisuudessa Vihreät hieman kirivät, mutta häviävät edelleen Feministipuolueelle 0.9 % -yksiköllä.

Siirtyminen alkuperäisestä algoritmista Euklidiseen etäisyyteen tasoittaisi tilannetta enemmän. Feministipuolue voittaisi enää olemattomalla 0.1% – yksikön erolla. Mikäli muutettaisiin molempia mittaustapoja, lopulta Vihreät menisivät Feministipuolueen ohi paalupaikalle prosentein 71.8% – 67.6%.

Kehitysehdotuksia

Tässä Jyrki Kasvin tapauksessa oli hyvin pienestä kiinni, tuleeko Feministipuolue vai Vihreät voittajaksi puolueen läheisyyden vertailussa. Itse olisin algoritmin kehityksessä todennäköisesti lähtenyt liikkeelle etäisyydestä puolueen keskipisteeseen ja ainakin pohtinut puolueiden erilaisten kokojen ja kysymysten välisten korrelaatioiden huomioimista jollain tavalla. Oma tämän hetken ymmärrys aiheesta ei kuitenkaan riitä painavasti kritisoimaan algoritmin kehittäjän valintoja käytetyissä etäisyysmittareissa.

Huoleni koskee lähinnä vaalikoneen tapaa suosia ronskisti voittaja-puoluetta esiin nostetuissa ehdokkaissa nyt kun voittajapuolueen voi tiukoissa kisoissa ratkaista valinnat algoritmin kehityksessä tai muut satunnaistekijät.

Kun itse tein Hesarin vaalikoneen, klikkasin kolmen ylimmäksi nousseen ehdokkaat lisätiedot uusiin välilehtiin ja siirryin tutkimaan niitä. Ainakin itseltäni on mennyt täysin ohi, että alempana on saattanut olla muista puolueista ehdokkaita, jotka osuvat vielä paremmin omiin valintoihin. Ensimmäinen kehityskohde voisikin olla tämän asian selkeämpi viestiminen kiireiselle käyttäjälle.

Yleisemmällä tasolla tämä esimerkki havainnollistaa, kuinka todellisessa maailmassa, eksaktin matematiikan ulkopuolella, algoritmien kehitys on aina jossain määrin taidetta ja kehittäjän tekemät valinnat vaikuttavat jossain määrin tuloksiin. Tässäkin tapauksessa voittaja olisi ollut Vihreät, mikäli olisi käytetty ryhmäkeskiarvoja ja Euklidista etäisyyttä.

Mitä enemmän algoritmilla on vaikutusta ihmisiin, sitä tärkeämpää on niitä julkistaa ja altistaa kritiikille sekä kehotusehdotuksille. Tästä ryhdikäs hatun nosto Hesarille.

Facebooktwittergoogle_plusredditpinterestlinkedinmail

Vakioanalytiikkaa – näin tehdään miljardeja

Vieraskynä: Tämän postauksen on poikkeuksellisesti kirjoittanut kollega, vedonlyöntikonkari Johannes Ärje (Twitter: @JJArje)

Vakioveikkaus on Veikkaus Oy:n vanhin peli. Sen pelaaminen aloitettiin jo vuonna 1940, mutta tässä blogipostauksessa keskitytään vuoteen 2016. Mitä mahdollisuuksia kehittynyt tietotekniikka ja data-analytiikka tuo pelaamiseen?

Voittava vedonlyönti

Voittava vedonlyönti on helpompi määritellä kuin toteuttaa. Kaikki ne vedot, jotka odotusarvoisesti eli keskimäärin palauttavat enemmän kuin panos oli, ovat teoreettisesti voitollisia vetoja. Jos noppaa heitettäessä saisit kertoimen 6.5 silmäluvulle 6, olisi veto voitollinen, vaikka se ei juuri sillä kertaa toteutuisikaan. Suurin haaste voittavaan urheiluvedonlyöntiin on siinä että odotusarvon laskemiseen tarvittava vedon osumisen todennäköisyys joudutaan aina arvioimaan. Samasta syystä johtuen on vaikea arvioida, onko vedonlyönti kokonaisuudessaan voitollista, vaikka vetoja olisi takana satoja tai Vakion tapauksessa satojatuhansia. Vakion kaltaisissa totalisaattoripeleissä (voitto-osuudet määrittyvät sen mukaan mitä rivejä muut pelaajat pelaavat) toinen suuri haaste on ennakoida muiden vedonlyöjien pelaamista loppuhetkellä. Onneksi pelaamishetkellä on informaatiota sen hetken tilanteesta.

Todennäköisyydet

soccer_ballVakion kohteet vaihtelevat laidasta (ampumahiihto) laitaan (jalkapallo) ja tuskin kukaan pystyy / ehtii jokaiseen kohteeseen arvioimaan todennäköisyyksiä omassa päässä luotettavasti. Vailla parempaa tietoa voi turvautua vedonlyöntimarkkinan informaatioon eli muodostaa vaikkapa suuria panoksia ottavan firman kertoimista todennäköisyydet. Useimmissa lajeissa / sarjoissa viime hetken kertoimista voidaan poimia suhteellisen luotettavat arviot eri tulosten todennäköisyyksille. Toki vedonlyöjä, joka pystyy arvioimaan markkinaa paremmin todennäköisyyksiä, saa valtavaa etua Vakion kaltaisessa pelissä, jos pelin muut puolet ovat hallussa. Henkilökohtaisesti turvaudun eri lajeissa eri informaatiolähteisiin.

API

Veikkaus tarjoaa yhtenä harvoista vedonlyöntiyhtiöistä ohjelmointirajapintaa (API, application programming interface), jonka avulla voidaan tietokoneohjelman kautta hakea tietoa kertoimista, voitto-osuuksista ja peleistä sekä myös suorittaa itse vedonlyönti. Näin ollen koko pelaaminen alusta loppuun on mahdollista automatisoida jopa niin, että vedonlyöjä voi lähteä viikoksi Karibian risteilylle netin ulottumattomiin ja kone hoitaa kaiken likaisen työn.

Algoritmi:

– tutki onko tänään Vakiossa sopivia kohteita

– vähän ennen kohteen sulkeutumista:

  1. hae / arvioi yksittäisten kohteiden todennäköisyydet
  2. hae infoa pelatuista vakioriveistä
  3. lyö odotusarvoltaan positiivisiksi arvioidut rivit sisään, mutta jätä koko kierros välistä, jos jokin epäilyttää

– analysoi lopullisilla tiedoilla vetokokonaisuuden odotusarvoa

Rivien hakeminen

Veikkauksen API:sta voidaan tosiaan hakea tietoa jokaisen rivin voitto-osuudesta ja pelatusta rivimäärästä. Niinpä se on mahdollista tehdä kaikille riveille, joita 12 kohteen Vakiossa on 531441 kappaletta. Harmi, että tarjolla ei ole mitään yhtä tiedostoa, josta nämä määrät löytyisivät. Tai no, hyvähän se on niille, jotka pystyvät hakemaan silti rivit. Moniajot siis käyntiin, mutta Veikkauksen sääntöjä noudattaen rajoitetaan prosessit maksimissaan viiteen.

(https://github.com/VeikkausOy/sport-games-robot)

Voitto-osuudet

Tällä hetkellä 8 kohteen Vakiossa on vain yksi voittoluokka, joten kyseisen pelin matemaattinen puoli on lastenleikkiä (Verrataan rivin todennäköisyyttä odotettuun voitto-osuuteen). 18 kohteen Vakio Grand Prix:ssa puolestaan rivitiedot eivät ole haettavissa, joten sen pelin allekirjoittanut on kokonaan skipannut. Keskitytään tässä 12 kohteen Vakioon, joka on hieman yksinkertaisempi kuin perinteinen 13 kohteen Vakio.

12 kohteen Vakiossa on kolme voitto-osuusluokkaa (12, 11 ja 10 oikein), joten jokaisen rivin odotusarvo muodostuu 1 + 24 + 264 = 289:stä eri osasta, jotka summataan yhteen. Yksittäisellä rivillä voi siis saada osumaan 24 eri tavalla 11 oikeaa tulosta. Lisähaasteena kaikkien luokkien voitto-osuudet muuttuvat vielä sen mukaan, jos jossakin voitto-osuusluokassa joko voitto-osuus jäisi alle 2 euron tai siinä ei ole yhtään riviä. Kun tällainen laskenta tehdään pelin kaikille riveille, niin laskutoimenpiteitä tulee suoritettua lähes puoli miljardia. En muuten suosittele tämän koodaamiseen for-silmukkaa.

Ennustaminen

Konepelaajat kilpailevat erityisesti toisiaan vastaan. Usein muut pelaajat / peliporukat löytävät viime hetkellä ison osan samoja rivejä. Niinpä pelatessa on syytä myös ennustaa muualta tulevaa peliä. Eipä siinä siis muu auta kuin luoda sopiva ennustemalli aiempien kierrosten datojen perusteella. Alustavan arvioni perusteella viikonpäivistä perjantai on paras eli silloin on kilpailua vähiten. Liekö joku muu robotti eksynyt silloin baariin?

Toki myös omat lähellä toisiaan olevat rivit vaikuttavat odotusarvoihin, joten on syytä tehdä uusi ennustetuilla rivimäärillä toteutettu voitto-osuuslaskentaruljanssi ja karsia vielä huonoksi tippuneita rivejä pois.

Rivit sisään

Lopulta kun on saatu aikaan arvio hyvistä riveistä, pitää vedot saada lyötyä vielä sisään niin nopeasti kuin mahdollista. Joko peliaika on päättymässä tai Veikkaus on päivittämässä tietojaan (10 minuutin välein). Jälkimmäisessä tapauksessa on tärkeä määritellä reviiriään muille pelaajille, sillä jokainen veto tiettyyn riviin vähentää sen kannattavuutta muille. Rivejä on mahdollista myös yhdistellä järjestelmiksi ja usein 5000 rivin kokonaisuus tiivistyykin alle puoleen ja samoin käy syöttöön tarvittavalle ajalle.

Kuinka sitten kävikään

Kuinka hyvänä rivikokonaisuuden odotusarvo lopulta säilyikään muiden pelaajien tulituksessa? Olennaisin tekijä tähän on aika, jolloin kertoimia päivitetään viimeisen kerran. Itselleni täydellinen päivitysaika on kuusi minuuttia ennen kohteen sulkeutumista, jolloin ehdin vielä tämän kaiken tehdä, mikäli pelattava rivimäärä ei ole poikkeuksellisen korkea. Lopullisten tietojen päivityttyä on syytä vielä tarkastaa lopullinen odotusarvo, mutta itse otteluiden katsominen saa jäädä muiden henkilöiden vastuulle.

Kannattaako tehdä Vakiorobotti?

  • Ei, koska edut ovat pieniä.
  • Ei. Jos joku pelaisi samat rivit kuin itse pelaan, niin molempien odotusarvo painuisi pakkasen puolelle.
  • Ei, koska liikaa vaivaa.

Vastauksia usein esitettyihin kysymyksiin:

  • Koneeni on Suomen paras (loppupelin analytiikan perusteella)
  • Jäin tappiolle Karibian risteilyn aikana
  • Kaikki tämä on tehty R:llä (http://www.r-project.org)
  • En kertonut lähellekään kaikkea
  • Tarjoan kerrointa 6.5, että Kimblessä tulee valitsemani numero, jos saan itse suorittaa painalluksen

Mitä tykkäsit blogipostauksesta ”Vakioanalytiikkaa – näin tehdään miljardeja laskutoimituksia”?

– Johannes ÄrjeFacebooktwittergoogle_plusredditpinterestlinkedinmail