upper-cpnfidence-bound-level
Die vielversprechende Wahl eines potentiellen Partners: Dieser Pfau „hat einen höheren upper bound confidence level“ als Artgenossen mit kleineren Schleppen, Quelle: Pixabay, Free for commercial use, DanielAlon.

Im ersten Teil dieser Artikelserie haben wir gesehen, wie der Epsilon Greedy Algorithmus, der einfachste und wohl bekannteste Bandit Algorithmus, mit einer geringen, vorgegebenen Wahrscheinlichkeit die Google Ads Kampagnen „erforscht“, welche zum Zeitpunkt t nicht zwingendermaßen die höchsten Erwartungswerte der Klickanzahl bei einer Budgetreallokation eines durch budget limitierten Google Ads Kontos aufweisen. Auch wenn Epsilon Greedy damit bereits eine gute Möglichkeit liefert, das Dilemma zwischen Exploitation (Ausnutzen der Budgetreallokation, welche zum Zeitpunktpunkt t den höchsten Erwartungswert an Klicks erbringt) und Exploration (Erforschen von alternativen Budgetverschiebungen zu Google Ads Kampagnen mit eventuell höheren Erwartungswerten der Klickanzahl) auszubalancieren, so fällt die zufällige Wahl einer alternativen Budgetreallokation ohne eigentliche Vorlieben, wie beispielsweise die Aussicht auf einen besonders hohen Erwartungswert der Kampagnen Klicks. Wäre es nicht viel besser, wenn die „nicht-greedy-Wahl“, also das Erforschen von Alternativen so ausfällt, dass entweder, die Wahrscheinlichkeit des höchsten Erwartungswert am größten ist oder dass die Wahl auf diejenige Budgetreallokation fällt, die wir zum Zeitpunkt t am wenigsten erforscht haben? Damit könnten wir uns die Wahl einer nichtoptimalen Budgetreallokation weitgehend ersparen. Der Upper Bound Confidence Level (=UBC) Algorithmus ermöglicht genau diese Verbesserung.

 

Das Szenario der Google Ads Optimierung

 

Bleiben wir bei unserem Szenario aus Teil 1: ein herkömmliches Google Ads Konto mit 4 Suchkampagnen K1, K2, K3 und K4 und einem Gesamtbudget von G=100 Euro pro Tag. Seien die 4 Kampagnen wieder durch Ihr Budget aktuell limitiert, sprich komplett von unserem Freelancer durchoptimiert und eine Anhebung des Gesamtbudgets ist nicht möglich. Wieder ist unser Ziel, mit einer entsprechenden, regelmäßigen Reallokation des Gesamtbudgets die höchstmögliche Anzahl an Klicks zu erhalten. Wie beim Epsilon Greedy Ansatz, modellieren wir den geschätzten Erwartungswert der Belohnungen, sprich die Klickanzahl durch die jeweilige Verschiebung eines Anteils von je 5 Euro dreier Kampagnen auf die vierte als Mittelwert Qn = R1+R2+…+R4 / n oder umformuliert inkremental als Qn+1 = Qn + 1/n*(Rn – Qn) (Sutton, R. S. & Barto A. G. (2018). Reinforcement Learning. Westchester Publishing Services, US). Den tatsächlichen Erwartungswert schreiben wir wieder als q(a) = E[Rt|At = a] auf. Anders als beim Epsilon Greedy Algorithmus, wird das Testen von Alternativen nicht durch eine vorgegebene, „blinde“ Wahrscheinlichkeit realisiert, sondern durch die Varianz des geschätzten Erwartungswertes, oder besser gesagt durch ein Konfidenzintervall It,a.

Prinzipiell wird mit dem UCB auf die Idee des Konfidenzintervalls (Gruss an Martin 😉 ) aus der Statistik zurückgegriffen. Um den erstaunlich komprimierten Ansatz im Vorwege genießen zu können, stelle ich zunächst dem geneigten Leser die abgeänderte, mathematische Formulierung des gesamten UCB Ansatzes vor: Vollständig ausgeschrieben sieht die action die gewählt wird so aus.

arg-max Anmutig einfach oder? Widmen wir uns nun der Erklärung. Hiefür liefern wir als erstes die Erklärung des Konfidenzintervalls aus der Statistik.

 

Vom Konfidenzintervall zum Upper Confidence Bound

 

Wenn p die Populationsgröße ist, die wir schätzen wollen (also zum Beispiel der Erwartungswert der Klicks durch die Verschiebung der Google Ads Kampagnen Budgets), so bezeichnet das Konfidenzintervall das Intervall I=[a,b], wobei a und b in der Regel reelle Zahlen sind, so dass p mit einer gewissen Wahrscheinlichkeit W innerhalb des Intervalls liegt. Ist diese Wahrscheinlichkeit zum Beispiel W=95%, so können wir, wenn wir das Konfidenzintervall bestimmt haben sagen, dass in 95 von 100 Fällen (unserer Schätzungen) die tatsächliche Größe p zwischen a und b liegt. Umgangssprachlich können wir dann sagen, dass wir eine 95% Chance haben, über die Anzahl der geschätzten Klicks, die wir durch die Budgetreallokation erhalten, richtig zu liegen. Wir nennen dieses Intervall das 95% Konfidenzintervall. Wenn das Intervall nun sehr breit ausfällt, sagen wir I=[10,75], so könnte mit einer 95% Wahrscheinlichkeit der Zugewinn an Klicks 75 sein. Sicherlich eine action, die sich lohnt, frühzeitig zu überprüfen. Und genau das ist das Ziel des UBC, beziehungsweise eines der beiden Ziele.

Der Term sorgt dafür, dass die action (=Google Ads Kampagnen Budgetverschiebung) bevorzugt wird, welche entweder die größtmögliche Belohnung, sprich Klickanzahl enthält oder von uns am wenigsten erforscht wurde. In beiden Fällen haben wir dadurch einen Vorteil. Liegt der nächste Wert des Belohnung (= Anzahl der erhaltenen Klicks nach Verschiebung des Budgets)  tatsächlich innerhalb des Intervalls, so können wird diese action mit einer entsprechend großen Klickanzahl ausnutzen (Exploitation) , liegt er nicht in dem Intervall, haben wir etwas Neues gelernt (Exploration) und können wir uns auf andere Reallokationen konzentrieren.

Die Funktionsweise des Terms

Situation 1: Der nächste reward (=Anzahl der erhaltenen Klicks nach Verschiebung des Google Ads Budgets) liegt tatsächlich in arg-max

Wenn sich unsere optimistische Erwartung bestätigt, erhöht sich der Nenner und der Zähler in und zwar jedes Mal, wenn wir die action ausnutzen. Der Logarithmus im Zähler sorgt allerdings dafür, dass sich die Wirkung des Terms im Laufe der Zeit verringert, da die Steigung mit der Zeit nachlässt. Dies wiederum bedeutet, dass der Gesamtausdruck mit der Zeit schneller gegen den “echten” Erwartungswert konvergiert. Dadurch verringert sich aber auch die Unsicherheit der richtigen Wahl.

Situation 2: Die action gewinnt nicht, wird also nicht gewählt. Dann erhöht sich für die zugrundeliegende Google Ads Budgetverschiebung nur der Zähler und das Intervall wird größer. Dadurch jedoch wird diese Aktion ein stärkerer Kandidat für die Exploration. Die Eigenschaft lässt gewolltermaßen ebenfalls mit der Zeit nach. Denn jedesmal, wenn die action nicht gewählt wird, lässt die Wirkung des Zählers nach, da die Steigung des Logarithmus kleiner wird.

Die Modellierung der Google Ads Budget Optimierung mit Python

Beim UCB benötigen wir keine Zufallsgenerierung. Die Umsetzung reduziert auf die Modellierung der geschätzten Erwartungswerte der Google AdWords Klicks durch die Verschiebung der Budgets und den Term . Hier kommt die Umsetzung in Python mit Erklärungen:

 

# Google Ads Budgetoptimierung budgetlimitierter Google Ads Kampagnen mit dem Upper Confidence Bound Algorithmus (UCB).
# Am Beispiel eines Google Ads accounts mit 4 budgetlimitierten Kampagnen. Beim Start der Benutzung des UCB wird
# angenommen, dass bereits eine einmalige, anteilige Verschiebung von je x Euros von 3 Kampagnenbudgets zur jeweils
# vierten zu folgenden Ergebnissen geführt hat:
# Verschiebung nach Kampagne 1: 1 zusätzlicher Klick
# Verschiebung nach Kampagne 2: 3 zusätzliche Klicks
# Verschiebung nach Kampagne 3: 2 zusätzliche Klicks
# Verschiebung nach Kampagne 4: 9 zusätzliche Klicks
# Die entsprechenden geschätzten Erwartungswerte sind in campaign_exp4=np.array([1,3,2,9]) übertragen worden.
# Autor: Jan Tappé, M.A. - www.jantappe.de - Februar 2020. Creative Commons (CC) Lizenz: free to use for non commercial purposes

import pandas as pd
import numpy as np

campaign_counters4=np.array([1,1,1,1])
# Initialisierung von 4 counter Variablen in Form eines Arrays

campaign_exp4=np.array([1,3,2,9])
# Initialisierung von 4 Erwartungswert Variablen in Form eines Arrays
t2=1

calc_array=[0,0,0,0]
# Hier kommen die Ergebnisse der Berechnungen von Q_t,a + c*sqrt(ln(t)/N(a) zur Bestimmung von arg max Q_t,a + c*sqrt(ln(t)/N(a)
# hinein

assisting_array=[0,0,0,0]
# Ein Hilfsarray. Der Eintrag wird 1, für arg max Q_t,a + c*sqrt(ln(t)/N(a)

# Ab hier geht's los. Ab hier wird so oft, wie gewünscht wiederholt.

# Berechnung des Ausdrucks Q_t,a + c*sqrt(ln(t)/N(a))
t2=+t2
for cell in range(4):
calc_array[cell]=campaign_exp4[cell]+10*(np.sqrt(np.log(t2)/(campaign_counters4[cell]+1)))

c=np.argmax(calc_array)

reward=input("Bitte gib den aktuellen reward ein: ")
reward=float(reward)
b=reward

# Berrechnung von Q_t,a + c*sqrt(ln(t)/N(a)) nach Erhalt des rewards für die Google Ads Budgetverschiebung, für
# die Q_t,a + c*sqrt(ln(t)/N(a) maximal wird (Funktionsweise 1)
campaign_exp4[c]=(campaign_exp4[c]+((1/campaign_counters4[c])*(b-campaign_exp4[c])))+
10*(np.sqrt(np.log(t2)/campaign_counters4[c]))
campaign_counters4[c]=campaign_counters4[c] +1

# Berrechnung von Q_t,a + c*sqrt(ln(t)) für die nicht-maximalen Budgetverschiebungen (Funktionsweise 2)
assisting_array[c]=1
for cell in assisting_array:
if assisting_array[cell] != 1:
campaign_exp4[c]=campaign_exp4[c]=(campaign_exp4[c]+((1/campaign_counters4[c])*(b-campaign_exp4[c])))+
10*(np.sqrt(np.log(t2)))
campaign_counters4[c]=campaign_counters4[c] +1
assisting_array=[0,0,0,0]

# Testlauf: Ergebnis nach 5 hypothetischen Durchläufen. Am besten performed in diesem Beispiel Kampagne 3
# mit 2 Zusatzklicks für das Gesamtkonto mit 4 Google Ads Kampagnen nach der Budgetverschiebung.

campaign_exp4

array([1, 1, 2, 0])

Der Artikel hat gefallen? Dann freue ich mich auf ein Feedback.
Bis dahin viel Spaß beim Modellieren
Jan

Wer schreibt hier? Mein Name ist Jan Tappé. Als selbstständiger Online Marketing Consultant berate ich Firmen aus der ganzen Welt zum Thema Online Marketing seit 2010. Ich bin überzeugt davon, dass die Zukunft des Online Marketings maßgeblich durch Machine Learning bestimmt wird. Um hierbei einen Beitrag zu leisten, promoviere ich berufsbegleitend zu einem Schnittstellenthema von angewandter Mathematik, Machine Learning und Online Marketing.