Představme si jednoduchou situaci. Řekněme, že jsme vlastníky internetového e-shopu s radiátory a chceme začít prodávat nejnovější typ. Ten má sice o něco lepší vlastnosti než staré modely, ale je o třetinu dražší, a zákazníci tak stále preferují starší varianty. Proto se rozhodneme, že ho začneme propagovat na úvodní stránce prostřednictvím banneru. Na prodeji tohoto modelu nám opravdu hodně záleží, a tak jsme si zaplatili profesionála, který připravil tři grafické návrhy. Otázka teď zní: jaký grafický návrh vybereme?

Nejjednodušší možností, kterou v takovém případě volí většina majitelů e-shopů, je vlastní úsudek. Ten je ovšem velmi subjektivní a vůbec nemusí odpovídat preferencím zákazníků. Lepší možností je využití takzvaného A/B testování. To spočívá v tom, že po nějakou dobu všechny bannery střídáme a pro každý z nich měříme poměr prokliků vůči počtu jeho zobrazení (CTR). Po nasbírání průkazného množství dat vybere banner s nejvyšší hodnotou CTR.

Tato metoda však není ideální. Návštěvnost e-shopu s radiátory asi nebude nijak závratná, proto může trvat velmi dlouho než nasbíráme dostatek dat pro kvalifikované rozhodnutí. Pokud bude navíc některý z bannerů výrazně méně atraktivní pro uživatele, jeho zobrazováním namísto jiného můžeme přijít o velké peníze. Naším cílem je tedy odhalit nejatraktivnější banner co nejdříve.

Moje oblíbená metoda, která patří mezi nejefektivnější, nese název bayesovský bandita. Pojmenování pochází z optimalizační úlohy známé jako problém mnohorukého bandity. Jedná se o problém, ve kterém máme řadu výherních automatů (v angličtině nazývaných one-armed bandit), každý s jinou pravděpodobností výhry, a naším cílem je nalézt posloupnost, v jaké na jednotlivých automatech hrát tak, abychom maximalizovali výnos. Jinými slovy, chceme co nejrychleji nalézt automat, u kterého je pravděpodobnost výhry nejvyšší a dále hrát pouze na tomto automatu. Analogie s bannery v e-shopu je přímočará − naším cílem je co nejdříve nalézt banner s nejvyšším CTR.

Jak sám název metody napovídá, je k tomu využita bayesovská statistika. Konkrétně jsou CTR jednotlivých bannerů odhadována samplováním z beta rozdělení. V obecnosti se jedná o rozdělení s parametry α a β definované jako

Pro ilustraci jsou křivky hustoty pravděpodobnosti beta rozdělení pro některé hodnoty α a β jsou zachyceny na obrázku 1.

Pro porozumění je dobré si uvědomit, že beta rozdělení je v podstatě pravděpodobnostní rozdělení popisující pravděpodobnosti pravděpodobností. V našem případě je to rozdělení přes pravděpodobnosti prokliků (CTR). Tvar křivky určující beta rozdělení je dán parametry α a β. Pokud jsou oba rovny 1 (černá křivka), všechny hodnoty CTR jsou stejně pravděpodobné. V případě volby odlišných hodnot parametrů dochází k tomu, že některé hodnoty CTR jsou více pravděpodobné než jiné. Obecně platí, že je střední hodnota beta rozdělení určena vztahem

Pokud tedy budou například α i β stejné a zároveň větší než 1, bude vždy nejpravděpodobnější hodnotou CTR číslo kolem 0.5. Pokud budou hodnoty α a β v poměru 25:75, bude střední hodnota CTR 1/4 (modrá křivka). Další zajímavou vlastností beta rozdělení je fakt, že čím jsou hodnoty parametrů vyšší, tím menší je jeho rozptyl. Z praktického hlediska to znamená, že čím vyšší hodnoty parametrů α a β ve správném poměru zvolíme, tím přesnější odhad CTR budeme mít (zelená a červená křivka).

Nyní se můžeme pustit do popisu algoritmu bayesovského bandity. Hlavní myšlenka spočívá v tom, že CTR každého banneru modelujeme pomocí beta rozdělení. Při hledání vhodného banneru k zobrazení náhodně vylosujeme hodnotu CTR ze všech tří beta rozdělení a zobrazíme ten banner, jehož vylosovaná hodnota CTR bude nejvyšší. Pokud uživatel na banner klikne, zvýšíme parametr α odpovídajícího beta rozdělení o 1. Pokud uživatel neklikne, zvýšíme o 1 hodnotu parametru β. Tento postup opakujeme při každém načtení úvodní stránky zobrazující banner.

Vzhledem k tomu, že na začátku testování obvykle o CTR jednotlivých bannerů nevíme nic, algoritmus je u všech bannerů inicializován hodnotami α = β = 1. Žádný z nich tedy není preferovaný a všechny mají stejnou šanci na zobrazení. Dalšími kroky se odhad zpřesňuje a algoritmus postupně konverguje do stavu, kdy bude téměř vždy vyhrávat banner s nejvyšší skutečnou hodnotou CTR.

Jeden z okamžiků rozhodování mezi bannery k zobrazení je zachycen na obrázku 2.

Jedná se o stav, kdy už byl každý z bannerů několikrát zobrazen a máme tedy hrubý odhad CTR. Střední hodnota banneru 1 na obrázku je 0.25, u banneru 2 je 0.4 a u banneru 3 je 0.67. Nejvyšší pravděpodobnost zobrazení má tedy banner 3. Nemusí však nutně zvítězit, protože aktuální CTR losujeme z příslušných beta rozdělení a například oblast okolo 0.5 má nenulovou pravděpodobnost u všech tří bannerů. Svislé čárkované čáry představují příklady vylosovaných hodnot. Vidíme, že oproti očekávání byl banner 2 předstižen bannerem 1, avšak nejvyšší hodnoty dosáhl přece jen banner 3. Proto ho zobrazíme.

Jednoduchou implementaci algoritmu bayesovského bandity představuje následující kód v jazyce Python.

from scipy.stats import beta
from random import random

class Banner():
    def __init__(self, CTR, alpha=1, beta=1):
        self.CTR = CTR
        self.alpha = alpha
        self.beta = beta

    def update(self, click):
        if click == True:
            self.alpha += 1
        else:
            self.beta += 1

    def sample(self):
        return beta(self.alpha, self.beta).rvs()

    def getCTR(self):
        return self.CTR

class BayesBandit:
    def __init__(self, CTRs):
        self.banners = []
        for CTR in CTRs:
            self.banners.append(Banner(CTR))

    def selectBanner(self):
        sampledCTRs = [banner.sample() for banner in self.banners]
        return sampledCTRs.index(max(sampledCTRs))

    def simulateUser(self, banner):
        CTR = self.banners[banner].getCTR()
        if random() < CTR:
            self.banners[banner].update(False)
        else:
            self.banners[banner].update(True)

if __name__ == "__main__":
    bandit = BayesBandit([0.25, 0.4, 0.67])
    for i in range(100):
        banner = bandit.selectBanner()
        bandit.simulateUser(banner)
        print "Banner %d" % (banner + 1)

Třída Banner, definovaná na řádcích 4-20, implementuje jednotlivé bannery. Je inicializovaná skutečnou hodnotou CTR a volitelně počátečními parametry α a β. Metoda update provádí aktualizaci parametrů na základě toho, jestli uživatel klikl na banner poté, co se mu zobrazil. Metoda sample vybírá náhodnou hodnotu CTR z odpovídajícího beta rozdělení. Metoda selectBanner třídy BayesBandit nejprve vylosuje CTR pro všechny bannery a poté vrátí index banneru s nejvyšší hodnotou CTR. Simulace chování skutečného uživatele je prováděna v metodě simulateUser.  Ta využívá skutečné hodnoty CTR banneru a rozhoduje o tom, zda by skutečný uživatel na banner klikl nebo ne. Samotný testovací program je zapsaný na řádcích 39-44. Nejprve jsou vytvořeny 3 bannery se skutečnými hodnotami CTR 0.25, 0.4 a 0.67. Poté je opakovaně vybírán banner k zobrazení a simulováno chování uživatele. Číslo zobrazeného banneru je v každém kroku vypsáno na standardní výstup. Po spuštění programu je vidět, že algoritmus zpočátku vybírá různé bannery, ale s rostoucím počtem iterací začíná preferovat banner 3. Už po dosažení 100 iterací je zobrazován téměř výhradně banner s nejvyšším skutečným CTR.

Popsaný algoritmus předpokládá, že o skutečných hodnotách CTR před zahájením testování nic nevíme. To však nemusí platit vždy. Provozovatel e-shopu například může předem usoudit, že banner 3 bude u uživatelů oblíbenější než banner 1. Potom je možné nastavit vhodné iniciální hodnoty α a β namísto defaultních 1. Pokud bude odhad správný, konvergenci to ještě urychlí. Pokud by však byl iniciální expertní odhad výrazně odlišný od skutečných hodnot, algoritmus sice po čase dokonverguje do správných hodnot, ale bude k tomu zapotřebí mnohem více iterací.