{"id":167,"date":"2014-12-09T08:50:37","date_gmt":"2014-12-09T07:50:37","guid":{"rendered":"http:\/\/www.mlguru.cz\/?p=167"},"modified":"2017-08-12T15:37:41","modified_gmt":"2017-08-12T13:37:41","slug":"bayesovsky-bandita-chytrejsi-a-levnejsi-ab-testovani","status":"publish","type":"post","link":"https:\/\/www.mlguru.com\/cs\/bayesovsky-bandita-chytrejsi-a-levnejsi-ab-testovani\/","title":{"rendered":"Bayesovsk\u00fd bandita: chyt\u0159ej\u0161\u00ed a levn\u011bj\u0161\u00ed A\/B testov\u00e1n\u00ed"},"content":{"rendered":"

\"Slot<\/a><\/p>\n

P\u0159edstavme si jednoduchou situaci. \u0158ekn\u011bme, \u017ee jsme vlastn\u00edky internetov\u00e9ho e-shopu s radi\u00e1tory a chceme za\u010d\u00edt prod\u00e1vat nejnov\u011bj\u0161\u00ed typ. Ten m\u00e1 sice o n\u011bco lep\u0161\u00ed vlastnosti ne\u017e star\u00e9 modely, ale je o t\u0159etinu dra\u017e\u0161\u00ed, a z\u00e1kazn\u00edci tak st\u00e1le preferuj\u00ed star\u0161\u00ed varianty. Proto se rozhodneme, \u017ee ho za\u010dneme propagovat na \u00favodn\u00ed str\u00e1nce prost\u0159ednictv\u00edm banneru. Na prodeji tohoto modelu n\u00e1m opravdu hodn\u011b z\u00e1le\u017e\u00ed, a tak jsme si zaplatili profesion\u00e1la, kter\u00fd p\u0159ipravil t\u0159i grafick\u00e9 n\u00e1vrhy. Ot\u00e1zka te\u010f zn\u00ed: jak\u00fd grafick\u00fd n\u00e1vrh vybereme?<\/p>\n

Nejjednodu\u0161\u0161\u00ed mo\u017enost\u00ed, kterou v takov\u00e9m p\u0159\u00edpad\u011b vol\u00ed v\u011bt\u0161ina majitel\u016f e-shop\u016f, je vlastn\u00ed \u00fasudek. Ten je ov\u0161em velmi subjektivn\u00ed a v\u016fbec nemus\u00ed odpov\u00eddat preferenc\u00edm z\u00e1kazn\u00edk\u016f. Lep\u0161\u00ed mo\u017enost\u00ed je vyu\u017eit\u00ed takzvan\u00e9ho A\/B testov\u00e1n\u00ed. To spo\u010d\u00edv\u00e1 v tom, \u017ee po n\u011bjakou dobu v\u0161echny bannery st\u0159\u00edd\u00e1me a pro ka\u017ed\u00fd z nich m\u011b\u0159\u00edme pom\u011br proklik\u016f v\u016f\u010di po\u010dtu jeho zobrazen\u00ed (CTR<\/a>). Po nasb\u00edr\u00e1n\u00ed pr\u016fkazn\u00e9ho mno\u017estv\u00ed dat vybere banner s nejvy\u0161\u0161\u00ed hodnotou CTR.<\/p>\n

Tato metoda v\u0161ak\u00a0nen\u00ed ide\u00e1ln\u00ed. N\u00e1v\u0161t\u011bvnost e-shopu s radi\u00e1tory asi nebude nijak z\u00e1vratn\u00e1, proto m\u016f\u017ee trvat velmi dlouho ne\u017e nasb\u00edr\u00e1me dostatek dat pro kvalifikovan\u00e9 rozhodnut\u00ed. Pokud bude nav\u00edc n\u011bkter\u00fd z banner\u016f v\u00fdrazn\u011b m\u00e9n\u011b atraktivn\u00ed pro u\u017eivatele, jeho zobrazov\u00e1n\u00edm nam\u00edsto jin\u00e9ho m\u016f\u017eeme p\u0159ij\u00edt o velk\u00e9 pen\u00edze. Na\u0161\u00edm c\u00edlem je tedy odhalit nejatraktivn\u011bj\u0161\u00ed banner co nejd\u0159\u00edve.<\/p>\n

Moje obl\u00edben\u00e1 metoda, kter\u00e1 pat\u0159\u00ed mezi nejefektivn\u011bj\u0161\u00ed, nese n\u00e1zev bayesovsk\u00fd bandita. Pojmenov\u00e1n\u00ed\u00a0poch\u00e1z\u00ed z optimaliza\u010dn\u00ed \u00falohy zn\u00e1m\u00e9 jako probl\u00e9m mnohoruk\u00e9ho bandity<\/a>. Jedn\u00e1 se o probl\u00e9m, ve kter\u00e9m m\u00e1me \u0159adu v\u00fdhern\u00edch automat\u016f (v angli\u010dtin\u011b naz\u00fdvan\u00fdch one-armed bandit<\/a>), ka\u017ed\u00fd s jinou pravd\u011bpodobnost\u00ed v\u00fdhry, a na\u0161\u00edm c\u00edlem je nal\u00e9zt posloupnost, v jak\u00e9 na jednotliv\u00fdch automatech hr\u00e1t tak, abychom maximalizovali v\u00fdnos. Jin\u00fdmi slovy, chceme co nejrychleji nal\u00e9zt automat, u kter\u00e9ho je pravd\u011bpodobnost v\u00fdhry nejvy\u0161\u0161\u00ed a d\u00e1le hr\u00e1t pouze na tomto automatu. Analogie s bannery v e-shopu je p\u0159\u00edmo\u010dar\u00e1 \u2212\u00a0na\u0161\u00edm c\u00edlem je co nejd\u0159\u00edve nal\u00e9zt banner s nejvy\u0161\u0161\u00edm CTR.<\/p>\n

Jak s\u00e1m n\u00e1zev metody napov\u00edd\u00e1, je k tomu vyu\u017eita\u00a0bayesovsk\u00e1 statistika. Konkr\u00e9tn\u011b jsou\u00a0CTR jednotliv\u00fdch banner\u016f odhadov\u00e1na samplov\u00e1n\u00edm z\u00a0beta rozd\u011blen\u00ed<\/a>. V obecnosti se jedn\u00e1 o rozd\u011blen\u00ed s parametry \u03b1\u00a0a \u03b2\u00a0definovan\u00e9 jako<\/p>\n

Beta(x|\\alpha, \\beta) = \\dfrac{\\Gamma(\\alpha + \\beta)}{\\Gamma(\\alpha)\\Gamma(\\beta)}x^{\\alpha-1}(1 - x)^{\\beta-1}. <\/p>\n

Pro ilustraci jsou k\u0159ivky hustoty pravd\u011bpodobnosti beta rozd\u011blen\u00ed pro n\u011bkter\u00e9 hodnoty \u03b1\u00a0a \u03b2 jsou zachyceny na obr\u00e1zku 1.<\/p>\n

\"\"<\/a><\/p>\n

Pro porozum\u011bn\u00ed je dobr\u00e9 si uv\u011bdomit, \u017ee beta rozd\u011blen\u00ed je v podstat\u011b pravd\u011bpodobnostn\u00ed rozd\u011blen\u00ed popisuj\u00edc\u00ed\u00a0pravd\u011bpodobnosti pravd\u011bpodobnost\u00ed. V na\u0161em p\u0159\u00edpad\u011b je to rozd\u011blen\u00ed p\u0159es pravd\u011bpodobnosti proklik\u016f (CTR). Tvar k\u0159ivky ur\u010duj\u00edc\u00ed beta rozd\u011blen\u00ed je d\u00e1n parametry\u00a0\u03b1\u00a0a \u03b2. Pokud jsou oba rovny 1 (\u010dern\u00e1 k\u0159ivka), v\u0161echny hodnoty CTR jsou stejn\u011b pravd\u011bpodobn\u00e9. V p\u0159\u00edpad\u011b volby odli\u0161n\u00fdch\u00a0hodnot parametr\u016f doch\u00e1z\u00ed k tomu, \u017ee n\u011bkter\u00e9 hodnoty CTR jsou v\u00edce pravd\u011bpodobn\u00e9 ne\u017e jin\u00e9. Obecn\u011b plat\u00ed, \u017ee je st\u0159edn\u00ed hodnota beta rozd\u011blen\u00ed ur\u010dena vztahem<\/p>\n

E[x] = \\dfrac{\\alpha}{\\alpha + \\beta}. <\/p>\n

Pokud tedy budou nap\u0159\u00edklad\u00a0\u03b1 i \u03b2 stejn\u00e9 a z\u00e1rove\u0148 v\u011bt\u0161\u00ed ne\u017e 1, bude v\u017edy nejpravd\u011bpodobn\u011bj\u0161\u00ed hodnotou CTR \u010d\u00edslo kolem 0.5. Pokud budou hodnoty\u00a0\u03b1 a \u03b2 v pom\u011bru 25:75, bude st\u0159edn\u00ed hodnota CTR 1\/4 (modr\u00e1 k\u0159ivka). Dal\u0161\u00ed zaj\u00edmavou vlastnost\u00ed beta rozd\u011blen\u00ed je fakt, \u017ee \u010d\u00edm jsou hodnoty parametr\u016f vy\u0161\u0161\u00ed, t\u00edm men\u0161\u00ed je jeho rozptyl. Z praktick\u00e9ho hlediska to znamen\u00e1, \u017ee \u010d\u00edm vy\u0161\u0161\u00ed hodnoty parametr\u016f\u00a0\u03b1 a \u03b2 ve spr\u00e1vn\u00e9m pom\u011bru zvol\u00edme, t\u00edm p\u0159esn\u011bj\u0161\u00ed odhad CTR budeme m\u00edt (zelen\u00e1 a \u010derven\u00e1 k\u0159ivka).<\/p>\n

Nyn\u00ed se m\u016f\u017eeme pustit do popisu algoritmu bayesovsk\u00e9ho bandity. Hlavn\u00ed my\u0161lenka\u00a0spo\u010d\u00edv\u00e1\u00a0v tom, \u017ee CTR ka\u017ed\u00e9ho banneru modelujeme pomoc\u00ed beta rozd\u011blen\u00ed. P\u0159i hled\u00e1n\u00ed vhodn\u00e9ho banneru k zobrazen\u00ed n\u00e1hodn\u011b vylosujeme hodnotu CTR ze v\u0161ech t\u0159\u00ed\u00a0beta rozd\u011blen\u00ed a zobraz\u00edme ten banner, jeho\u017e\u00a0vylosovan\u00e1 hodnota CTR bude nejvy\u0161\u0161\u00ed. Pokud u\u017eivatel na banner klikne, zv\u00fd\u0161\u00edme parametr \u03b1 odpov\u00eddaj\u00edc\u00edho beta rozd\u011blen\u00ed o 1. Pokud u\u017eivatel neklikne, zv\u00fd\u0161\u00edme o 1 hodnotu parametru \u03b2. Tento postup opakujeme p\u0159i ka\u017ed\u00e9m na\u010dten\u00ed \u00favodn\u00ed str\u00e1nky zobrazuj\u00edc\u00ed banner.<\/p>\n

Vzhledem k tomu, \u017ee na za\u010d\u00e1tku testov\u00e1n\u00ed obvykle o CTR jednotliv\u00fdch banner\u016f nev\u00edme nic, algoritmus je u v\u0161ech banner\u016f inicializov\u00e1n hodnotami\u00a0\u03b1 = \u03b2 = 1. \u017d\u00e1dn\u00fd z nich\u00a0tedy nen\u00ed preferovan\u00fd a v\u0161echny maj\u00ed stejnou \u0161anci na zobrazen\u00ed. Dal\u0161\u00edmi kroky se odhad zp\u0159es\u0148uje a algoritmus postupn\u011b konverguje do stavu, kdy\u00a0bude t\u00e9m\u011b\u0159 v\u017edy vyhr\u00e1vat banner s nejvy\u0161\u0161\u00ed skute\u010dnou hodnotou CTR.<\/p>\n

Jeden z okam\u017eik\u016f\u00a0rozhodov\u00e1n\u00ed mezi bannery k zobrazen\u00ed je zachycen\u00a0na obr\u00e1zku 2.<\/p>\n

\"Obr\u00e1zek<\/a>

Obr\u00e1zek 2: Bayesovsk\u00fd bandita.<\/p><\/div>\n

Jedn\u00e1 se o stav, kdy\u00a0u\u017e byl ka\u017ed\u00fd z banner\u016f n\u011bkolikr\u00e1t zobrazen a m\u00e1me tedy hrub\u00fd odhad CTR. St\u0159edn\u00ed hodnota banneru 1 na obr\u00e1zku je 0.25, u banneru 2 je 0.4 a u banneru 3 je 0.67. Nejvy\u0161\u0161\u00ed\u00a0pravd\u011bpodobnost zobrazen\u00ed m\u00e1 tedy banner 3. Nemus\u00ed v\u0161ak nutn\u011b zv\u00edt\u011bzit, proto\u017ee aktu\u00e1ln\u00ed\u00a0CTR losujeme z p\u0159\u00edslu\u0161n\u00fdch beta rozd\u011blen\u00ed a nap\u0159\u00edklad oblast okolo\u00a00.5 m\u00e1 nenulovou pravd\u011bpodobnost u v\u0161ech t\u0159\u00ed banner\u016f. Svisl\u00e9 \u010d\u00e1rkovan\u00e9 \u010d\u00e1ry p\u0159edstavuj\u00ed p\u0159\u00edklady vylosovan\u00fdch hodnot. Vid\u00edme, \u017ee oproti o\u010dek\u00e1v\u00e1n\u00ed byl banner 2 p\u0159edsti\u017een\u00a0bannerem 1, av\u0161ak nejvy\u0161\u0161\u00ed hodnoty dos\u00e1hl p\u0159ece jen banner 3. Proto ho zobraz\u00edme.<\/p>\n

Jednoduchou implementaci algoritmu bayesovsk\u00e9ho bandity p\u0159edstavuje n\u00e1sleduj\u00edc\u00ed k\u00f3d v jazyce Python<\/a>.<\/p>\n

\r\n\r\nfrom scipy.stats import beta\r\nfrom random import random\r\n\r\nclass Banner():\r\n    def __init__(self, CTR, alpha=1, beta=1):\r\n        self.CTR = CTR\r\n        self.alpha = alpha\r\n        self.beta = beta\r\n\r\n    def update(self, click):\r\n        if click == True:\r\n            self.alpha += 1\r\n        else:\r\n            self.beta += 1\r\n\r\n    def sample(self):\r\n        return beta(self.alpha, self.beta).rvs()\r\n\r\n    def getCTR(self):\r\n        return self.CTR\r\n\r\nclass BayesBandit:\r\n    def __init__(self, CTRs):\r\n        self.banners = []\r\n        for CTR in CTRs:\r\n            self.banners.append(Banner(CTR))\r\n\r\n    def selectBanner(self):\r\n        sampledCTRs = [banner.sample() for banner in self.banners]\r\n        return sampledCTRs.index(max(sampledCTRs))\r\n\r\n    def simulateUser(self, banner):\r\n        CTR = self.banners[banner].getCTR()\r\n        if random() &lt; CTR:\r\n            self.banners[banner].update(False)\r\n        else:\r\n            self.banners[banner].update(True)\r\n\r\nif __name__ == &quot;__main__&quot;:\r\n    bandit = BayesBandit([0.25, 0.4, 0.67])\r\n    for i in range(100):\r\n        banner = bandit.selectBanner()\r\n        bandit.simulateUser(banner)\r\n        print &quot;Banner %d&quot; % (banner + 1)\r\n\r\n<\/pre>\n
T\u0159\u00edda Banner<\/em>, definovan\u00e1 na \u0159\u00e1dc\u00edch 4-20, implementuje jednotliv\u00e9 bannery. Je inicializovan\u00e1 skute\u010dnou hodnotou CTR a voliteln\u011b po\u010d\u00e1te\u010dn\u00edmi\u00a0parametry\u00a0\u03b1 a \u03b2. Metoda update<\/em> prov\u00e1d\u00ed aktualizaci parametr\u016f na z\u00e1klad\u011b toho, jestli u\u017eivatel klikl na banner pot\u00e9, co se mu zobrazil. Metoda sample<\/em> vyb\u00edr\u00e1 n\u00e1hodnou hodnotu CTR z odpov\u00eddaj\u00edc\u00edho beta rozd\u011blen\u00ed. Metoda selectBanner<\/em> t\u0159\u00eddy BayesBandit<\/em> nejprve vylosuje CTR pro v\u0161echny\u00a0bannery a pot\u00e9 vr\u00e1t\u00ed index banneru s nejvy\u0161\u0161\u00ed hodnotou CTR. Simulace chov\u00e1n\u00ed skute\u010dn\u00e9ho u\u017eivatele je prov\u00e1d\u011bna v metod\u011b\u00a0simulateUser.\u00a0<\/em>\u00a0Ta vyu\u017e\u00edv\u00e1 skute\u010dn\u00e9 hodnoty CTR banneru a rozhoduje o tom, zda by skute\u010dn\u00fd u\u017eivatel na banner klikl nebo ne. Samotn\u00fd testovac\u00ed program je zapsan\u00fd na \u0159\u00e1dc\u00edch 39-44. Nejprve jsou vytvo\u0159eny 3 bannery se skute\u010dn\u00fdmi hodnotami CTR 0.25, 0.4 a 0.67. Pot\u00e9 je opakovan\u011b vyb\u00edr\u00e1n banner k zobrazen\u00ed a simulov\u00e1no chov\u00e1n\u00ed u\u017eivatele. \u010c\u00edslo zobrazen\u00e9ho banneru je v ka\u017ed\u00e9m kroku vyps\u00e1no na standardn\u00ed v\u00fdstup. Po spu\u0161t\u011bn\u00ed programu je vid\u011bt, \u017ee algoritmus zpo\u010d\u00e1tku vyb\u00edr\u00e1 r\u016fzn\u00e9 bannery, ale s rostouc\u00edm po\u010dtem iterac\u00ed za\u010d\u00edn\u00e1 preferovat banner 3. U\u017e po dosa\u017een\u00ed 100 iterac\u00ed\u00a0je zobrazov\u00e1n t\u00e9m\u011b\u0159 v\u00fdhradn\u011b banner s nejvy\u0161\u0161\u00edm skute\u010dn\u00fdm CTR.<\/p>\n
Popsan\u00fd algoritmus p\u0159edpokl\u00e1d\u00e1, \u017ee o skute\u010dn\u00fdch hodnot\u00e1ch CTR p\u0159ed zah\u00e1jen\u00edm testov\u00e1n\u00ed nic nev\u00edme. To v\u0161ak nemus\u00ed platit v\u017edy. Provozovatel e-shopu nap\u0159\u00edklad m\u016f\u017ee p\u0159edem usoudit, \u017ee banner 3 bude u u\u017eivatel\u016f obl\u00edben\u011bj\u0161\u00ed ne\u017e banner 1. Potom je mo\u017en\u00e9\u00a0nastavit vhodn\u00e9 inici\u00e1ln\u00ed hodnoty\u00a0\u03b1 a \u03b2 nam\u00edsto defaultn\u00edch 1. Pokud bude\u00a0odhad spr\u00e1vn\u00fd, konvergenci to je\u0161t\u011b urychl\u00ed. Pokud by v\u0161ak byl inici\u00e1ln\u00ed expertn\u00ed odhad v\u00fdrazn\u011b odli\u0161n\u00fd od skute\u010dn\u00fdch hodnot, algoritmus sice po \u010dase dokonverguje do spr\u00e1vn\u00fdch hodnot, ale bude k tomu zapot\u0159eb\u00ed\u00a0mnohem\u00a0v\u00edce iterac\u00ed.<\/p>\n","protected":false},"excerpt":{"rendered":"
P\u0159edstavme si jednoduchou situaci. \u0158ekn\u011bme, \u017ee jsme vlastn\u00edky internetov\u00e9ho e-shopu s radi\u00e1tory a chceme za\u010d\u00edt prod\u00e1vat nejnov\u011bj\u0161\u00ed typ. Ten m\u00e1 sice o n\u011bco lep\u0161\u00ed vlastnosti ne\u017e star\u00e9 modely, ale je o t\u0159etinu dra\u017e\u0161\u00ed, a z\u00e1kazn\u00edci tak st\u00e1le preferuj\u00ed star\u0161\u00ed varianty. Proto se rozhodneme, \u017ee ho za\u010dneme propagovat na \u00favodn\u00ed str\u00e1nce prost\u0159ednictv\u00edm banneru. Na prodeji tohoto […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":""},"categories":[2,9],"tags":[],"class_list":["post-167","post","type-post","status-publish","format-standard","hentry","category-statistika","category-testovani"],"_links":{"self":[{"href":"https:\/\/www.mlguru.com\/cs\/wp-json\/wp\/v2\/posts\/167","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.mlguru.com\/cs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.mlguru.com\/cs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.mlguru.com\/cs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mlguru.com\/cs\/wp-json\/wp\/v2\/comments?post=167"}],"version-history":[{"count":44,"href":"https:\/\/www.mlguru.com\/cs\/wp-json\/wp\/v2\/posts\/167\/revisions"}],"predecessor-version":[{"id":431,"href":"https:\/\/www.mlguru.com\/cs\/wp-json\/wp\/v2\/posts\/167\/revisions\/431"}],"wp:attachment":[{"href":"https:\/\/www.mlguru.com\/cs\/wp-json\/wp\/v2\/media?parent=167"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.mlguru.com\/cs\/wp-json\/wp\/v2\/categories?post=167"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.mlguru.com\/cs\/wp-json\/wp\/v2\/tags?post=167"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}