Upper Confidence Bound

Kategori: Machine Learning , 17 Aralık 2019 , JanFranco


Upper Confidence Bound bir Reinforcement algoritmasıdır. Reinforcement yani pekiştirmeli öğrenmede bilgisayar her yanlış yaptığı tahminde ceza, doğru yaptığı tahminde ödül alacaktır. Yani doğru yapılan her tahmin için bir ağırlık güncellemesi yapılacaktır. Mantık buna dayanır.

Upper Confidence Bound algoritmasını anlatmadan önce bir örnek yapalım. Bir firmamız var. 10 farklı reklam hazırladık. Müşterilerimiz bu reklama her tıkladığında biz bir lira kazanacağız. Herhangi bir öğrenme vs. kullanmadan bu reklamları rastgele yayınlayalım. Sonucu görmek için bir veri seti kullanacağız. Veri setinde 10 reklam var ve bu reklamlara tıklanmaları gösteriyor. Python üzerinden görelim. Kütüphaneleri ve verileri alalım:


import math
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

pd.set_option('display.max_rows', 200)
pd.set_option('display.max_columns', 20)
pd.set_option('display.width', 1000)

df = pd.read_csv('Ads_CTR_Optimisation.csv')
print(df)

>>

      Ad 1  Ad 2  Ad 3  Ad 4  Ad 5  Ad 6  Ad 7  Ad 8  Ad 9  Ad 10
0        1     0     0     0     1     0     0     0     1      0
1        0     0     0     0     0     0     0     0     1      0
2        0     0     0     0     0     0     0     0     0      0
3        0     1     0     0     0     0     0     1     0      0
4        0     0     0     0     0     0     0     0     0      0
5        1     1     0     0     0     0     0     0     0      0
6        0     0     0     1     0     0     0     0     0      0
7        1     1     0     0     1     0     0     0     0      0
8        0     0     0     0     0     0     0     0     0      0
9        0     0     1     0     0     0     0     0     0      0
10       0     0     0     0     0     0     0     0     0      0
11       0     0     0     0     0     0     0     0     0      0
12       0     0     0     1     0     0     0     0     0      0
13       0     0     0     0     0     0     0     0     1      0
14       0     0     0     0     0     0     0     1     0      0
15       0     0     0     0     1     0     0     1     0      0
16       0     0     0     0     0     0     0     0     0      0
17       0     0     0     0     0     0     0     0     0      0
18       0     0     0     0     0     0     0     1     0      0
19       0     0     0     0     0     0     0     0     1      0
20       0     1     0     0     0     0     0     1     0      0
21       0     0     0     0     1     0     0     0     0      1
22       0     0     0     0     0     0     0     0     0      0
23       0     0     0     0     0     0     0     1     1      0
24       0     0     0     0     1     0     1     1     0      0
25       0     0     0     0     0     0     0     0     0      0
26       0     1     0     0     1     0     0     1     0      0
27       0     1     0     1     0     0     0     0     0      0
28       0     0     0     0     0     0     0     0     0      0
29       0     0     0     0     1     0     0     1     1      0
30       1     0     0     0     1     0     0     0     0      0
31       0     0     0     0     0     0     0     0     0      0
32       0     0     0     0     0     0     0     0     0      1
33       0     0     0     1     0     0     0     0     0      0
34       0     0     0     0     0     1     0     1     1      0
35       0     0     0     0     0     0     0     0     0      0
36       0     0     0     0     0     0     0     0     0      0
37       0     0     0     0     0     0     0     0     0      0
38       0     0     0     1     0     0     0     0     0      0
39       0     0     0     0     1     0     1     1     0      0
40       0     0     0     0     1     0     0     0     0      0
41       0     0     0     0     1     0     0     1     0      0
42       0     0     0     0     0     0     0     1     0      0
43       0     0     0     0     1     0     0     0     0      0
44       0     0     0     0     0     0     1     0     0      0
45       0     0     0     0     1     0     0     0     0      0
46       0     0     0     0     0     0     0     0     0      0
47       0     0     0     0     0     0     0     0     0      0
48       0     1     0     0     0     0     0     1     0      0
49       0     0     0     0     1     0     0     0     0      0
50       0     0     0     1     0     0     0     1     0      0
51       0     0     0     0     0     0     0     0     0      0
52       0     0     0     0     1     0     0     1     0      0
53       1     0     0     0     1     0     0     0     0      0
54       0     0     1     0     1     0     0     0     0      0
55       0     1     1     0     0     0     0     0     0      0
56       1     0     0     0     0     0     0     0     0      0
57       0     0     1     0     0     0     0     1     0      0
58       0     0     0     0     0     0     0     0     0      0
59       0     1     0     0     0     0     0     0     0      0
60       1     0     0     0     0     0     0     0     0      0
61       0     0     1     0     0     0     0     0     0      0
62       0     0     0     0     1     0     0     0     0      0
63       0     0     0     0     1     0     0     0     0      0
64       0     0     0     0     0     0     0     0     1      0
65       0     0     0     1     0     0     0     0     0      0
66       0     0     0     0     1     0     0     0     0      0
67       0     1     0     0     1     0     0     0     0      0
68       0     0     0     0     0     0     0     0     0      0
69       0     0     0     0     0     0     0     0     0      0
70       0     0     0     0     0     0     0     0     0      0
71       0     0     0     0     0     0     0     1     0      0
72       0     1     0     0     1     0     0     0     0      0
73       0     0     0     0     0     0     0     0     0      0
74       0     0     0     0     0     0     1     0     0      0
75       0     0     0     0     0     0     0     0     0      0
76       0     0     0     0     0     0     0     0     0      0
77       0     0     0     0     0     0     0     1     0      0
78       0     1     0     0     1     0     0     0     0      0
79       0     0     0     0     0     0     0     0     0      0
80       0     0     0     0     0     0     0     1     0      0
81       0     0     0     0     0     0     1     1     0      0
82       0     0     0     1     0     0     0     0     0      0
83       0     1     1     0     0     0     0     0     0      0
84       0     0     0     1     0     0     0     0     0      0
85       0     1     0     0     0     0     0     0     0      0
86       0     0     0     0     0     0     0     0     0      0
87       0     0     0     0     0     0     1     0     0      0
88       1     0     0     1     0     0     0     1     0      0
89       0     0     0     0     0     0     0     1     0      0
90       0     0     0     0     1     0     1     0     0      0
91       0     0     0     0     0     0     0     1     0      0
92       0     0     0     0     0     0     0     0     0      0
93       0     0     0     0     0     0     0     0     0      0
94       1     0     0     1     0     0     0     0     1      0
95       0     0     0     0     0     0     0     0     0      0
96       0     1     0     0     0     0     0     0     1      0
97       0     0     0     1     0     0     1     0     0      0
98       0     0     1     1     1     0     0     1     0      0
99       0     0     0     0     1     0     0     0     1      0
...    ...   ...   ...   ...   ...   ...   ...   ...   ...    ...
9900     1     1     0     0     1     0     0     0     1      0
9901     0     0     0     0     1     0     1     0     0      0
9902     0     0     0     0     0     1     0     1     0      0
9903     0     0     1     0     0     0     0     0     0      1
9904     0     0     0     0     0     0     0     0     0      0
9905     0     0     0     0     1     0     0     0     0      0
9906     1     0     0     0     0     0     0     0     0      0
9907     0     0     0     0     0     0     0     0     0      1
9908     0     0     0     0     0     0     0     0     0      0
9909     0     0     0     0     0     0     0     1     0      0
9910     1     0     0     0     1     0     0     0     0      0
9911     0     0     0     0     0     0     0     0     0      0
9912     0     1     0     0     0     0     0     0     0      0
9913     0     0     0     0     0     0     0     1     0      0
9914     0     1     0     0     0     0     0     1     0      0
9915     0     0     0     0     1     0     0     0     0      0
9916     0     0     0     0     0     0     0     0     0      0
9917     0     1     0     0     0     0     0     0     0      0
9918     0     1     0     0     0     0     0     1     0      0
9919     1     1     1     0     0     0     0     0     0      0
9920     1     0     0     0     1     0     0     0     0      0
9921     0     1     0     0     0     0     0     0     0      0
9922     0     0     0     0     0     0     0     0     0      0
9923     0     0     0     0     0     0     0     0     0      0
9924     0     1     0     0     1     0     0     1     0      0
9925     0     0     0     0     0     0     1     0     0      0
9926     1     0     0     0     1     0     0     0     1      0
9927     1     0     0     0     1     0     0     0     0      0
9928     0     0     0     0     0     0     0     0     0      0
9929     0     0     0     0     0     0     0     0     0      0
9930     1     0     0     0     1     0     0     0     0      0
9931     0     0     0     0     0     0     0     0     0      0
9932     0     0     0     0     0     0     0     1     0      1
9933     0     0     0     1     0     0     0     0     0      0
9934     0     0     0     1     0     0     0     0     0      0
9935     0     0     0     0     0     0     0     0     0      0
9936     0     1     0     0     1     0     0     0     0      1
9937     0     0     0     0     0     0     0     0     0      0
9938     0     0     0     0     1     0     0     0     0      0
9939     0     0     0     0     0     0     1     0     0      0
9940     0     0     0     0     1     0     0     0     0      0
9941     0     0     0     0     0     0     0     0     0      0
9942     0     0     0     0     0     0     1     1     0      0
9943     1     0     0     1     0     0     0     0     0      0
9944     0     0     0     0     0     0     0     0     0      0
9945     0     1     0     0     0     0     0     0     1      0
9946     1     0     0     0     1     0     0     1     0      0
9947     0     0     0     0     0     0     0     1     0      0
9948     0     0     0     1     0     0     0     0     0      0
9949     0     0     0     0     0     0     0     1     0      0
9950     0     0     0     0     1     0     1     1     0      0
9951     0     0     0     0     0     0     0     0     0      0
9952     0     0     0     0     0     0     1     1     0      0
9953     0     0     0     0     0     0     0     0     0      0
9954     0     0     0     0     1     0     0     1     0      0
9955     0     0     0     1     1     0     0     0     0      0
9956     1     0     0     0     0     0     0     0     0      0
9957     0     0     1     0     0     0     0     0     0      0
9958     0     0     0     0     1     0     1     0     0      0
9959     0     0     0     0     0     0     0     0     0      0
9960     0     0     0     0     0     0     0     0     0      0
9961     0     0     0     0     0     0     0     0     0      0
9962     0     1     0     0     0     0     0     0     0      0
9963     0     0     0     0     0     0     0     0     0      0
9964     0     1     0     0     1     0     0     0     0      0
9965     0     0     0     0     0     0     0     0     0      0
9966     0     0     0     0     0     0     0     0     0      0
9967     0     1     1     0     0     0     1     0     0      0
9968     0     1     0     1     0     0     0     0     0      1
9969     0     0     1     0     1     0     0     0     0      1
9970     0     0     0     0     0     0     0     0     0      0
9971     0     0     0     0     0     0     0     1     0      0
9972     0     0     0     0     0     0     0     0     0      0
9973     0     0     0     0     1     0     0     0     0      0
9974     0     0     0     0     0     0     0     1     1      0
9975     0     0     0     0     1     0     1     0     1      0
9976     0     0     0     0     1     0     0     1     0      0
9977     0     1     0     0     1     0     1     0     0      0
9978     0     0     0     0     1     0     0     0     0      0
9979     0     0     1     0     0     0     1     0     0      0
9980     1     1     0     1     0     0     0     0     0      0
9981     0     0     0     0     0     0     0     0     0      0
9982     0     1     0     0     0     0     0     0     0      0
9983     0     0     0     0     1     0     0     1     1      0
9984     0     0     0     0     1     0     0     0     0      0
9985     0     0     0     0     0     0     0     1     0      0
9986     0     0     0     0     1     0     0     0     0      0
9987     0     0     0     0     1     0     0     0     0      0
9988     1     0     0     0     1     0     0     0     0      0
9989     0     0     0     0     0     0     0     0     0      0
9990     0     0     0     1     0     0     0     0     0      0
9991     0     1     0     1     1     0     1     0     0      0
9992     0     0     0     1     0     0     1     0     0      0
9993     0     0     0     0     1     0     0     0     1      0
9994     0     0     1     0     0     0     0     0     1      0
9995     0     0     1     0     0     0     0     1     0      0
9996     0     0     0     0     0     0     0     0     0      0
9997     0     0     0     0     0     0     0     0     0      0
9998     1     0     0     0     0     0     0     1     0      0
9999     0     1     0     0     0     0     0     0     0      0
0-10 arasında rastgele bir sayı üreteceğiz. O sayıya karşılık gelen reklamı göstereceğiz. Eğer verisetinde o reklam tıklanmışsa bir lira kazanmış olacağız. Şuan bunu canlı yapamıyoruz bu nedenle veri setini kullanacağız:


rows, columns = df.shape
totalReward = 0
selected = []
for n in range(rows):
    ad = np.random.randint(0, columns)
    selected.append(ad)
    reward = df.values[n, ad]
    totalReward += reward

plt.title('In Random Total Reward = ' + str(totalReward))
plt.hist(selected)
plt.show()
Upper Confidence Bound

Toplamda 1264 lira kazandık. Reklamlara hemen hemen eşit tıklanılmış. Bu bizim için en kötü sonuçtur. Rastgele reklam gösterdik, öğrenme kullanmadık. Yani öğrenme kullanarak bu değeri geçmeye çalışacağız. Upper Confidence Bound algoritmasını kullanacağız. Upper Confidence Bound şu adımlardan oluşur:

1- Her adımda (10.000 adımımız vardı) reklamın tıklanma ve o reklamdan gelen ödül rakamlarını tut, güncelle.

2- Ödül / Tıklanma değerini ve güven aralığı oynama potansiyelini (kök(3/2 * log(n) / tıklanma)) hesapla.

3- Ödül / Tıklama + Oynama Potansiyeli bizim UCB değerimiz. En yüksek UCB değerine sahip olanı al.

Görüyoruz ki bir öğrenme mevcut. Önceki adımlarıdaki bilgileri kullanıyoruz. Her bir adımda 10 reklam için Confidence değerini buluyoruz ve en yüksek değere sahip olana tıklıyoruz. Tabii başlangıçta her reklama bir kez tıklanacak ve rastgele bir confidence değerini biz vereceğiz. Bu algoritmaya göre eğer bir reklam gösterilir ve ödül alınırsa ortalama değer yükselecek. Bu ortalama değeri direk olarak UCB değerinde kullanacağız. Yani direk olarak UCB değerini artırıyor. Güven aralığı oynama potansiyeli ise tıklanma oldukça düşüyor. Bu da tek bir reklamda sıkışıp kalmayalım diyedir. Yani tıklanma oluyor ve ödül de oluyorsa UCB değeri artacaktır. Eğer tıklanma oluyor ancak ödül olmuyorsa zaten düşecektir:


rewards = [0] * columns
clicked = [0] * columns
totalReward = 0
selected = []
for n in range(rows):
    ad = 0
    max_ucb = 0
    for i in range(columns):
        if clicked[i] > 0:
            avg = rewards[i] / clicked[i]
            delta = math.sqrt(3/2 * math.log(n)/clicked[i])
            ucb = avg + delta
        else:
            ucb = rows * 10
        if max_ucb < ucb:
            max_ucb = ucb
            ad = i
    selected.append(ad)
    clicked[ad] = clicked[ad] + 1
    reward = df.values[n, ad]
    rewards[ad] += reward
    totalReward += reward

plt.title('UCB Total Reward = ' + str(totalReward))
plt.hist(selected)
plt.show()
Upper Confidence Bound

Burada görüyoruz ki toplam kazandığımız para artmış.


Sonraki Yazı: Thompson Sampling
Yorumlar

Henüz bir yorum bulunmuyor.