Bandit算法
該算法是為了解決MAB問題(多臂賭博機(jī)問題)
問題原形是憾朴，面對(duì)多個(gè)一樣的老虎機(jī)，每個(gè)老虎機(jī)吐錢幾率不一樣。要怎么樣選擇才能達(dá)到利益最大化镜廉。
這里會(huì)有一個(gè)EE問題签餐，即Exploitation-Exploration(E&E)我們?nèi)绾卧诶婧吞剿髦g均衡寓涨。我們已經(jīng)有幾臺(tái)的吐錢率高，我們是選擇只在這幾臺(tái)操作氯檐，還是要繼續(xù)探索其他可能吐錢率更好的機(jī)器戒良。
對(duì)于Bantid算法我們的核心思想是，使遺憾度最低冠摄。
前者是 最好機(jī)器上的獲利糯崎，后者是所選機(jī)器的獲利。兩者之差就是遺憾度耗拓。
我們又可以按照是否利用上下文(商品和用戶特征值)拇颅，分為兩類。當(dāng)然利用上下文的要好很多乔询。
LinUCB
該算法是從不使用上下文的UCB改進(jìn)而來(lái)樟插。
UCB算法，會(huì)計(jì)算一個(gè)得分
+號(hào)前面是收益竿刁，后面是最大置信上限
ni是一共的嘗試次數(shù)黄锤，n是該商品的嘗試次數(shù)。
該式子很好的均衡了探索和已知利益食拜。
最后對(duì)每個(gè)商品的得分排序鸵熟，選出最該推薦的商品。
由于該算法沒有任何的上下文信息负甸，所以雅虎對(duì)其進(jìn)行了修改流强。
他們假設(shè)痹届，我們的上下文與收益是成線性關(guān)系
現(xiàn)在我們的任務(wù)是學(xué)習(xí)到這個(gè)參數(shù)theta，這樣對(duì)于新來(lái)的數(shù)據(jù)打月，我們就可以根據(jù)數(shù)據(jù)上下文計(jì)算其收益队腐。
我們采用嶺回歸(L2正則)，由于我們的方程只有一個(gè)未知量奏篙。我們用標(biāo)準(zhǔn)化解法
(一般只用于數(shù)據(jù)量比較少的時(shí)候柴淘，不然計(jì)算起來(lái)很緩慢)
得到theta，這時(shí)我們可以把theta表示為
theta = A轉(zhuǎn)置＊b? ? b = DTc
于是我們實(shí)時(shí)計(jì)算步驟在此
這就是我們的LinUCB了秘通。
該算法的速度很快是線性的为严。
不是上面說theta標(biāo)準(zhǔn)化運(yùn)算數(shù)據(jù)量大會(huì)很慢嗎?其實(shí)因?yàn)槲覀兪菍?shí)時(shí)更新，所以A和b都是每次更新一行肺稀，最后運(yùn)算的不過是b＊A
置信上限是什么呢?
程序中的
是置信上限第股。它是由L2參數(shù)theta服從高斯分布得來(lái)的。具體過程我也沒研究盹靴。
