Stretli sme sa s tým už každý. Hľadáte človeka do teamu? Kupujete byt alebo hľadáte aspoň podnájom? Ste čerstvo rozídený/-á a rozmýšľate koľko ďalších vzťahov ešte budete musieť okúsiť, kým narazíte na toho pravého (resp. tú pravú)? Pri každej z tejto situácií sme v neistote, ako správne odhadnúť mieru svojej prieberčivosti. Prijať radšej vrabca v hrsti (a potom to ľutovať), či dúfať v holuba na streche s vedomím, že ho možno nikdy nebudem mať? Napriek tomu, že sme si tým prešli každý, len málo kto vie, že na túto otázku existuje optimálne, matematicky dokázané riešenie.
— Tento blog je súčasťou série Neznáme Algoritmy , ktorá sa snaží popularizovať aj tie dátové algoritmy, ktoré nie sú bežne používané, hoci sú vo svojej podstate veľmi užitočné. Ak vás téma zaujala, pridajte sa do analytickej komunity Mocnedata.sk a avízo na ďalšie užitočné analytické blogy dostaneme zakaždým medzi prvými priamo do emailu. —
Algoritmus, ktorý si dnes predstavíme sa odborne nazýva Stopping Problem, ale vo svete analytikov je častejšie označovaný ako Secretary problem. Dôvodom pre toto označenie bola pôvodná historka, ktorá prispela k popularizácii tejto matematickej hádanky. Na jej počiatku totiž išlo o to, ako pristúpiť optimálne k výberu sekretárky pre svoju firmu. Na rozdiel od HR rád o vhodnom profile a obsahu CVčka, Secretary problem sa zaoberá pragmatickejšou otázkou: Ak by som vyberal zo 100 kandidátok, ktorých kvality sú náhodne rozdelené (nevieme vopred, ktorá v poradí bude tá najlepšia), koľkých kandidátov by som mal vidieť, aby som mohol zodpovedne vybrať a neoľutovať svoj výber?
Ak ste o tom algoritme ešte nepočuli, asi vás zarazí, že má skutočne matematicky podložené optimálne riešenie. Čo je ešte prekvapivejšie, riešenie je stabilné naprieč rôznymi výberovými konaniami, takže sa dá držať stále toho istého postupu. Jediné, čo je potrebné splniť, aby správne fungoval je, že vyberáte len z možností, ktoré spĺňajú aspoň základné podmienky, ktoré ste si stanovili. (Teda, že na pracovný pohovor pozývate len takých kandidátov, ktorí aspoň hovoria rečou, v ktorej majú pracovať. Alebo, že idete na obhliadku iba takých bytov, ktoré majú aspoň vami požadovaný minimálny počet izieb).
Zaručená cesta k (?) úspechu
Pravidlo, ktoré pri takýchto výberoch vedie k optimálnemu výberu je formulované nasledovne: 37% času/úsilia hľadania systematicky odmietajte každú z videných možností (aj keby sa vám zdali ideálne) a následne siahnite po prvej, ktorá je najlepšia z tých, ktoré ste videli doposiaľ (alebo aspoň výrazne podobná). Čiže, ak by ste mali vybrať zo 100 kandidátov na prácu, pozvite si ich v náhodnom poradí, prvých 36 odmietnite a 37mim počnúc, vyberte toho, ktorý bol lepší ako všetci doposiaľ. Toto pravidlo funguje aj pre optimalizáciu toho, kedy sa postaviť do radu: dimenzujete to tak, aby ste 37% času prišli vopred a zvyšok strávili čakaním. Aj keď s radmi to môže byť komplikovanejšie, ak sa veci môžu minúť, kým na ne čakáte :(.
Pre tých, ktorí stále neveriacky krútia hlavami nad touto stratégiou, trochu vysvetlenia, ako to vlastne funguje. Stopping problém je hľadanie optimálneho pomeru medzi “rozkukávaním” a fázou “ideme na vec”. Ak ste videli len jedného kandidáta a na pohovor ich pozývate v náhodnom poradí, šanca toho druhého, že bude lepší, je v priemere približne 50%. Zároveň šanca, že sme zatiaľ nevideli najlepšieho je 98%. Keď pridáte tretieho účastníka, obe pravdepodobnosti sa k sebe o niečo priblížia. Ak to budete opakovať dostatočný počet krát, dostanú sa pravdepodobnosti do optimálnej rovnováhy. Tento bod nastáva pri 1/e časti celku, teda pri 1/2.71828 = 36.7879%, čo je tesne pod 37%. Keďže však väčšina situácií sa pohybuje v množine celých čísiel, stačí si zapamätať 37% ako približnú hodnotu tejto hranice.
Dozvedeli sme sa teda, že pri hranici 37% nastáva optimálny pomer medzi rozkukávaním a rozhodnosťou k činu. Čo však vlastne algoritmus skutočne garantuje? Ak ste to náhodou ešte neprekukli, tak treba otvorene povedať, že Stopping Problem algoritmus nesľubuje, že vyberiete najlepšieho možného kandidáta. Inými slovami, ak mám 100 kandidátov, tak samozrejme nie je zaručené, že ideálny kandidát (volajme ho číslo 100) príde tesne po 37% pokusov. Iste si viete predstaviť situáciu, že číslo 100 zhodou okolnosti príde na pohovor hneď ako prvý. Pravidlo 37% by ho teda odmietlo a v tom najlepšom prípade by nám zostávalo “len” číslo 99, ak náhodou tiež nebolo v prvých 36 pokusoch. Preto je si potrebné uvedomiť, že Stopping algoritmus negarantuje úspech, len maximalizuje pravdepodobnosť, že nebudete svoj výber ľutovať. Stopping problém totiž vychádza zo skutočnosti, že ak by aj prišlo číslo 100 na prvý pohovor, keďže ste nevideli ešte ostatných kandidátov, nevedeli by ste, že je to top 1 voľba. To, že si vyberáte naozaj dobrú voľbu, sa musí potvrdiť práve porovnaním s tými, ktorých ste už odmietli vo fáze “rozkukávania”. Nuž a práve pri 37% rozkukávaní je istota už dostatočne pevná, ale zároveň pravdepodobnosť výberu kvalitného kandidáta stále veľmi vysoká.
Čo všetko možno vyberať podľa 37% pravidla
Secretary problém má v skutočnom živote naozaj veľmi široké uplatnenie. Len si je potrebné uvedomiť, že 37% pravidlo sa nevzťahuje len na počty opakovaní nejakej činnosti, ale na akékoľvek úsilie ako také. Ak sa teda do 3 mesiacov hodláte presťahovať do nového mesta (napr. Berlína) , v ktorom ste nikdy pred tým nežili (a tým pádom neviete, ako vyzerá optimálny byt v danom meste), mali by ste venovať 37% času (teda niečo viac ako 1 mesiac) chodeniu po obhliadkach len preto, aby ste si urobili obraz o tom, čo je “dobrý byt” v Berlíne. Po tomto mesiaci by ste však mali byť pripravení zobrať prvý byt, ktorí bude lepší ako tie, čo ste videli. (alebo aspoň bude porovnateľný s tým najlepším, ktorý ste za prvý mesiac videli). Ak ste si však povedali, že napriek tomu, že máte 3 mesiace, ste ochotný/á ísť iba na 20 obhliadok, rozkukávanie bez seriózneho záujmu by malo trvať prvých 7 obhliadok, potom už by ste mali chňapnúť po prvom, ktorý vás očaril najviac doposiaľ.
Analogicky možno postupovať aj pri výbere životného partnera. Ak ste sa rozhodli, že si chcete založiť rodinu do 35ky, potom (predpokladajúc, že prvé seriózne lásky začínajú niekde okolo 16ho roku), tak do 24ho roku si môžete užívať viac menej nezáväzne (stále pozor na pohlavné choroby). Po tomto veku by ste však mali spozornieť a pokúsiť sa vybudovať pevný vzťah s prvým partnerom, s ktorým vám je vo vzťahu lepšie, ako vám bolo počas nezáväzného rozkukávania. Ak zoberiete do úvahy, že ľudia sa väčšinou berú po 3-4 rokoch spolu, je fascinujúce, že na Slovensku je priemerný vek nevesty 28 (= 24 + 4) rokov. Pre utlmenie všeobecného nadšenia však treba pripomenúť, že manželstvá na Slovensku stále dosahujú vyše 40% rozvodovosť. Ak by sa teda náhodou podvedome riadili pravidlom 37% (vedome ho asi nepoznajú), naznačovalo by to, že si na hľadanie partnera síce nechávajú potrebný čas, ale počas hľadania absolvujú príliš málo vzťahov, aby si kalibrovali, čo je dobrý partner.
Do tretice, Secretary problem v doprave. Ak idete autom na stretnutie alebo do divadla a na zaparkovanie vám zostáva ešte 10 min, tak optimálne je hľadať parkovacie miesto niečo menej ako 4 minúty a následne zaparkovať na prvom voľnom, ktoré vás postretne.
Rôzne mutácie
Po vyriešení základného Secretary problému sa objavili na svete rôzne mutácie základného zadania. Základným pravidlom Stopping problem algoritmu je, že ak ste nejakú ponuku videli a odmietli, nedostanete už šancu sa k tejto voľbe vrátiť. Hoci pri hľadaní bytu v Berlíne je to 100% pravda (ak si byt nevyberiete, pravdepodobne ešte v tom istom týždni sa tam nasťahuje niekto iný) a aj pri vzťahoch, kde ste odmietli požiadanie o ruku, to asi tiež platí, existujú aj situácie, kde vrátiť sa k už odmietnutej voľbe vôbec nemusí byť nemysliteľné. Napríklad spomínaný výber sekretárky: pokiaľ nežijete v krajine, kde sú buď nadmieru ješitné ženy alebo trh práce nie je v zúfalom nedostatku, asi je možné pre nejaké časové obdobie dozadu pokúsiť sa o opätovnú voľbu už odmietnutého kandidáta. V takomto prípade sa stratégia zásadne mení (oplatí sa pokračovať v hľadaní (a odmietaní) aj po 37% kandidátov až do 37% + x&, kde x reprezentuje práve čas (alebo počet možností dozadu v čase), ktoré môžete ešte obnoviť, aj keď ste ich primárne odmietli. Ak máte pocit, že sa budete vedieť vrátiť k ľubovoľnej ponuke bez ohľadu na to, kedy v minulosti ste ju prvý krát odmietli, potom stratégia velí vidieť všetkých kandidátov.
Inou mutáciou Stopping problému sa riadi situácia s predajom bytu. Ak totiž nadstrelíte hodnotu v ponuke výrazne viac, oplatí sa vám čakať dlhšie, či sa predsa nenájde niekto ochotný zaplatiť tak vysokú cenu. Naopak, ak počas čakania na kupca bytu máte s daným bytom ešte náklady (napr. energie), optimálne riešenie sa mení práve podľa pomeru nadstrelenej hodnoty k utekajúcim peniazom za držanie bytu do jeho predaja.
— Tento blog je súčasťou série Neznáme Algoritmy , ktorá sa snaží popularizovať aj tie dátové algoritmy, ktoré nie sú bežne používané, hoci sú vo svojej podstate veľmi užitočné. Ak vás téma zaujala, pridajte sa do analytickej komunity Mocnedata.sk a avízo na ďalšie užitočné analytické blogy dostaneme zakaždým medzi prvými priamo do emailu. —
Seriál je inšpirovaný publikáciou Algorithm to live by, ktorú čochvíľa predstavíme v jednom z blogov.
Publikované dňa 3. 5. 2018.
Späť na domovskú stránku
