Makine öğrenmiyor: Öneri sisteminde Bağlamsal Haydut algoritmasının uygulanması ve uygulanması
Makine www.jqbxx.com'u öğrenmiyor: Derin toplu makine öğrenimi, derin öğrenme algoritmaları ve teknik mücadele
Öneri sistemi, kullanıcılara gösterilecek ürünleri seçer ve kullanıcıların olumlu geri bildirimlerini (tıklamalar, işlemler) bekler. Ancak öneri sistemi, kullanıcıların ürünü inceledikten sonra nasıl tepki vereceğini önceden bilemez, yani bu önerinin faydalarını önceden alamaz.Yapabileceği tek şey, deneme yanılma stratejisini güncellemek için gerçek zamanlı olarak denemeye devam etmek ve geri bildirim toplamaktır. Amaç, tüm sürecin kaybını en aza indirmektir. Bu süreç, bir kumarhanede kumar oynayan bir kumarbazınkine benzer. Kumarbaz, kumar makinelerini sallamak ve tam olarak aynı görünen bir dizi slot makinesi olduğunu görmek için kumarhaneye girmek istiyor, ancak her slot makinesinin olasılığı farklı. Her slot makinesinin olasılık dağılımını bilmiyor, bu yüzden her seferinde seçim yapmalı Hangi slot makinesi karı maksimize edebilir? Bu, Çoklu slot sorunudur (MAB).
MAB probleminin zorluğu, Exploitation-Exploration (EE) ikilemidir: nispeten yüksek bir para harcama olasılığına sahip olduğu bilinen slot makineleri için, belirli bir kümülatif getiri elde etmek için daha fazla girişimde bulunulmalıdır; bilinmeyen veya deneme sayısı için Daha az slot makinesiyle, daha yüksek getirili bir seçeneği kaçırmamak için belirli bir miktar keşif tahsis edilmelidir, ancak aynı zamanda daha fazla keşif, daha yüksek risk anlamına da gelir (fırsat maliyeti).
Haydut algoritması, Exploitation-Exploration mekanizmasını uygulamak için kullanılan bir strateji türüdür. Bağlam özelliğinin değerlendirilip değerlendirilmediğine göre, Haydut algoritması iki kategoriye ayrılır: bağlamdan bağımsız haydut ve bağlamsal haydut.
1. UCB
açgözlü, softmax, Thompson Örnekleme, UCB (Üst Güven Sınırı), vb. Gibi birçok Bağlamdan bağımsız Haydut algoritması vardır.
Burada UCB yönteminin temel fikrine odaklanacağım. İstatistikte, bilinmeyen bir miktarın tahmini için, güvenirliğini ölçmenin bir yolu her zaman bulunabilir. En yaygın dağılım normal dağılımdır (veya Gauss dağılımı) N (, ), burada tahmin edicinin beklentisidir ve
Belirsizliğini temsil eder ( ne kadar büyükse, o kadar az güvenilirdir). Örneğin, standart 6 yüzlü bir zar atarsanız, ortalama değeri 3.5'tir ve sadece bir kez atarsanız, örneğin 2, o zaman ortalama değer tahmininiz sadece 2 olabilir, ancak güven seviyesi çok düşük olmalıdır. Bu zarın tahmini ortalama değerinin 2 olduğu ve% 95 güven aralığında olduğu görülmektedir.
UCB (Üst Güven Sınırı-Üst Güven Sınırı), kolun gelecekteki getirisinin tahmini değerini temsil etmek için getirinin (bonus) ortalama değerinin güven aralığının üst sınırıdır:
Bunlar arasında, i ^ i kolunun beklenen getirisinin tahminidir, n toplam seçenek sayısıdır ve ni i'yi kurma teşebbüslerinin sayısıdır. Ne kadar çok deneme olursa, tahmin edilen değer ile üst güven limiti arasındaki farkın o kadar küçük olduğu görülebilir. Yani, daha fazla güven.
UCB'nin şu andaki kararı, güven aralığının en büyük üst sınırına sahip kolu seçmektir. Bu stratejinin avantajı, daha fazla deneme şansı olmayan kola daha fazla deneme fırsatı verebilmesidir.Atla çıkan katırlar!
- Bilinmeyen veya nadiren denenen kol için, ortalama değeri çok düşük olabilse de, belirsizliği, daha büyük bir keşif tetikleme olasılığına sahip olan daha büyük bir güven aralığı üst sınırına yol açacaktır.
- Zaten tanıdık olan (birden fazla denemek) kol için, sömürü mekanizmasını tetiklemek daha fazladır: eğer ortalama değeri yüksekse, onu kullanmak için daha fazla fırsat elde edecektir; aksi takdirde, deneme şansını azaltacaktır.
2. LinUCB
Öneri sisteminde tavsiye edilecek ürün genellikle MAB sorununun kolu olarak kabul edilir. UCB gibi bağlamdan bağımsız algoritmalar, önerilen sahnenin bağlamsal bilgisini tam olarak kullanmaz. Ürünleri tüm kullanıcıların seçimleri için sergileme stratejisi aynıdır, kullanıcının ilgisini, tercihini, satın alma gücünü vb. Yaşayan bir kişilik olarak görmezden gelir. Faktörler farklıdır, bu nedenle aynı ürünün farklı kullanıcılar ve farklı senaryolar altında kabulü farklıdır. Bu nedenle, gerçek öneri sisteminde bağlamdan bağımsız MAB algoritması temelde kullanılmaz.
Bağlamdan bağımsız MAB algoritmasına tekabül eden, Bağlamsal Haydut algoritmasıdır.Adından da anlaşılacağı gibi, bu tür algoritma EE'yi uygularken bağlam bilgisini dikkate alır, bu nedenle gerçek kişiselleştirilmiş öneri senaryoları için daha uygundur.
Resmi olarak konuşursak, adım t'de, bağlamsal haydut algoritması Mevcut kullanıcı ut ve her seçilebilir emtianın (kol) a özellik vektörünün Xt, a, Xt, a bağlamsal bilgi olarak adlandırıldığı ve hem kullanıcı hem de mal hakkındaki bilgileri özetlediği gözlemlenmiştir. Algoritma, daha önce gözlemlenen geri bildirim sonuçlarına göre kullanıcıyı göstermek için bir ürün seçer ve kullanıcının geri bildirimini alır. Gelir beklentisi, hem kullanıcıya hem de ürüne bağlıdır. Daha sonra, algoritma yeni gözlemlere (xt, a, at, rt, at) dayalı olarak emtia görüntüsünü seçme stratejisini geliştirir Amaç, tüm süreçteki, yani pişmanlık değeri RA (T) 'deki kaybı en aza indirmektir. RA (T) tanımı aşağıdaki gibidir:
Bunlar arasında T, deneydeki toplam adım sayısıdır; , önceden bilinemeyen, t zamanında maksimum beklenen getiriye sahip koldur.
LinUCB, Bağlamsal Haydutları işlemenin bir yöntemidir. LinUCB'de, her bir kolun beklenen getirisi, aşağıdaki gibi, kolun özellik vektörünün (bağlam) doğrusal bir fonksiyonu olarak ayarlanır:
a, LinUCB modelinin parametresidir ve boyut d'dir. Her kol bir a'yı korur Tek bir kol a için, satır vektörleri olarak ilk m bağlam vektörlerinden oluşan matrise Da adı verilir ve boyut m × n'dir. İlk m ödüllerinden oluşan vektöre ca denir. Kare kaybı işlevi
, normal terim katsayısıdır. Kayıp fonksiyonunun minimum değerini bulun, kayıp fonksiyonu a'yı türetsin, sonuç
aloss = 0, = 1 olsun,
Sırt regresyon yöntemini kullanarak, a'nın olasılık dağılımı bir Gauss dağılımı olarak elde edilebilir:
Kısalık uğruna
O zaman a'nın olasılık dağılımı aN ( ^ a, Aa 1) olarak ifade edilebilir.
Böylece tth anda alabiliriz
Gauss dağılımının doğasına göre, normal UCB kuralı, üst güven sınırı elde edildikten sonra, yani her seçtiğinizde kullanılabilir.
En büyük kol.
Aa ve DaTca'nın kademeli olarak eşzamansız olarak güncellenebileceği unutulmamalıdır, bu nedenle standart süreç aşağıdaki gibidir:
LinUCB algoritmasının avantajları:
- Hesaplama karmaşıklığı, silah sayısı ile doğrusal bir ilişkiye sahiptir
- Aday kol koleksiyonunun dinamik değişimini destekleyin
3. İş senaryolarına giriş
E-ticaret platformu Uygulamamızın ana sayfasında, her seferinde yaklaşık 30 ürün görüntüleyen bir ürün şelalesi öneri sahnesi bulunmaktadır. Ürün aday koleksiyonlarının tamamı iyi geçmiş satışlara sahip manuel seçimlerdir.Daha fazla trafiğin uyarılmasıyla popüler ürünler haline gelebilir ve her gün bir kısmı değiştirilir ve yeni ürünler eklenir.
LinUcb algoritmasını uyguladıktan sonra, sistem, gerçek satış potansiyeline sahip ürünleri keşfetmek, optimum olmayan ürünleri aşamalı olarak ortadan kaldırmak ve manuel ürün seçiminin sınırlamalarını düzeltmek için her ürünü tam olarak keşfedecek ve kullanacaktır. Test edilen ürünler, satış hacminin belirli bir süre içinde hala iyi olduğunu göstermektedir.Bu ürünlerin çalışması, tüccarların kullanıcılara daha fazla indirim ve taviz vermesini gerektirerek fiyatı derinlemesine kontrol edebilir, böylece erdemli bir çember oluşturur.Aynı zamanda diğer tüccarlar için de bir ölçüt oluşturur ve platformu destekler. Daha sağlıklı gelişim.
4. Sistem Mimarisi
Sistemimizde LinUCB algoritmasının uygulanması iki bölüme ayrılmıştır: bir parça öneri motorunda uygulanmaktadır, esas olarak öznitelik vektör çıkarımını tamamlayan, her bir ürünün Aa matrisini ve ba vektör verilerini elde eden, önceki oturumun güven aralığı hesaplamasını tamamlayan ve Görüntülenecek son ürünü seçin; mantığın başka bir kısmı gerçek zamanlı hesaplama platformu Storm'da uygulanmaktadır. Görevin bu bölümü sahnenin teşhirini, tıklama ve satın alma davranış günlüklerini gerçek zamanlı olarak analiz eder. Her günlük ürün kimliği, zaman damgası ve özellik vektörü gibi bilgileri içerir. Formül, her ürünün Aa matrisini ve ba vektörünü günceller ve güncellenen sonuçları öneri motorunun elde etmesi için Redis önbelleğine yazar.
5. Temel kod mantığı
Her ürün, alınan davranış olaylarının geçici olarak depolanması için bir kuyruk tutar. Konuyu aldığımızda hemen ilgilenmememizin iki ana nedeni vardır: Birincisi, kullanıcının görüntülenen her ürünle ilgili geri bildiriminin atomik bir işlem olmamasıdır, örneğin geri bildirimin açığa çıkıp çıkmaması veya tıklanmaması veya açığa çıkıp tıklanıp satın alınmaması veya Yani, teşhir ve tıklama ve son olarak satın alma. Bu işlemler tek adımda tamamlanmaz, ancak birkaç adım korunur. Bu nedenle, yalnızca karşılaşma veya tıklama aldığımızda, kullanıcının geri bildirim sırasının bitip bitmediğini bilmiyoruz. Bu nedenle, geri bildirimin dönüş değeri doğru bir şekilde ayarlanamaz; ikincisi, istemci maruz kalan olayları önbelleğe aldığından ve bunları gerçek zamanlı olarak rapor etmediğinden, açığa çıkan olayların olaylar tıklanmadan önce günlük sunucusuna yükleneceğine dair hiçbir garanti yoktur.
Spesifik uygulamada, bir zaman aralığı ayarlayın (örneğin, 5 dakika) Bir teşhir veya tıklama olayı Storm hesaplama düğümüne ulaştığında, önce kuyruğa alınır ve tüketimden önce ayarlanan zaman aralığını bekler. Zaman aralığı içinde yüksek öncelikli bir şey gelirse, düşük öncelikli şey doğrudan kaldırılacaktır. Öncelik sırası, satın alma işleminin tıklamadan büyük olması ve tıklama, karşılaşmadan daha büyük olmasıdır. Ek olarak, günlüğün tekrar tekrar raporlanmasını önlemek için, öneri motorunun istek kimliği (farklı istekler farklıdır) alınanları tekilleştirmek için kullanılacaktır. Elbette, hata toleransı için, önceden ayarlanmış görev kuyruğu doluysa, zaman aralığı dinamik olarak orijinalin yarısına kadar kısaltılacak ve yeni zaman aralığından önceki şeyler tüketmeye zorlanacaktır.Bu işlem kuyruğa kadar yinelemeli olarak yürütülecektir. Uzunluk, önceden ayarlanmış boyuttan daha az.
Fırtına görevinde, belirli bir malın parametresi (Aa matrisi ve ba vektörü) güncelleme mantığını:
public int Consume (Event newEvent, Config config) {
eğer (newEvent.getPid ()! = pid)
dönüş -1;
sıfırlama (yapılandırma);
int showConsumedCount = 0;
int clickConsumedCount = 0;
uzun akım = System.currentTimeMillis ();
Yineleyici < Etkinlik > iter = queue.iterator ();
while (iter.hasNext ()) {
Olay olayı = iter.next ();
eğer (event.isSameFlow (newEvent)) {
if (newEvent.isShow ()) {
newEvent = null; // Karşılaşmayı tekrarlayın, aksi takdirde tıklama olayı karşılaşma olayından önce gelir
kırmak;
}
if (newEvent.isClick () event.isClick ()) {
newEvent = null; // Tekrarlanan tıklama olayı
kırmak;
}
iter.remove (); // yüksek öncelikli şeyler, düşük öncelikli şeylerin üzerine yazılır
if (null == newEvent.getItemTrackData ()) {
newEvent.setItemTrackData (event.getItemTrackData ());
}
devam et;
}
eğer (current-event.getTimestamp () < config.cacheTimeSpan)
devam et;
INDArray xt = event.getFeature (config);
INDArray x = xt.transpose ();
A.addi (x.mmul (xt));
çift ödül = event.getReward ();
eğer (ödül > 0.0)
b.addi (x.muli (ödül));
iter.remove ();
eğer (event.isShow ())
showConsumedCount ++;
else if (event.isClick ())
clickConsumedCount ++;
}
eğer (null == newEvent)
dönüş 0;
eğer (newEvent.getType (). equals (EventType.BUY)) {
// Bir şeyler satın alın ve hemen tüketin
INDArray xt = newEvent.getFeature (config);
eğer (null == xt) {
LogPushUtil.push ("BuyFeatureMissingEvent");
}
else if (xt.length () == b.length ()) {
INDArray x = xt.transpose ();
A.addi (x.mmul (xt));
çift ödül = newEvent.getReward ();
b.addi (x.muli (ödül));
LogPushUtil.push ("BuyEventConsumed");
kayıtlar + = config.updateRecords;
}
} else if (StringUtils.isNotEmpty (newEvent.getItemTrackData ())) {
queue.add (newEvent);
checkQueueIsFullOrNot (config.cacheTimeSpan / 2, config);
}
eğer (showConsumedCount > 0) {
kayıtlar + = showConsumedCount;
LogPushUtil.push ("ShowEventConsumed", showConsumedCount);
}
eğer (clickConsumedCount > 0) {
kayıtlar + = clickConsumedCount;
LogPushUtil.push ("ClickEventConsumed", clickConsumedCount);
}
eğer (kayıtlar > = config.updateRecords) {
writeToRedis (config);
}
dönüş kayıtları;
}
Her ürünün ucb puanını hesaplayan çevrimiçi öneri motorunun kodu aşağıdaki gibidir:
private void parallelGetLinUcbScore (Oturum oturumu, INDArray özellikleri, Liste < Öğe > items) InterruptedException {
int concurrency = Math.min (session.config.linUcbConcurrency, items.size ());
int num = items.size () / eşzamanlılık;
ExecutorService es = session.context.getThreadExecutorService (session.reqId, session.reqId.getSceneId ());
final CountDownLatch countDownLatch = new CountDownLatch (eşzamanlılık);
int left = items.size () - num * eşzamanlılık;
int başlangıç = 0, bitiş = num;
for (int i = 0; i < eşzamanlılık; ++ i) {
Eğer ben < ayrıldı)
end ++;
Logger.debug ("linucb skor alt iş parçacığını başlatmak için hazırlanın:");
int finalStart = başlangıç;
int finalEnd = end;
Runnable runnable = () - > {
long startTime = System.currentTimeMillis ();
Deneyin {
getLinUcbScore (oturum, özellikler, öğeler, finalStart, finalEnd);
} catch (İstisna e) {
Dize istisnası = ExceptionUtils.getFullStackTrace (e);
Logger.error ("linucb işçi istisnası:", istisna);
}
en sonunda {
countDownLatch.countDown ();
}
uzun süre = System.currentTimeMillis () - startTime;
Logger.info ("alınan alt linUcb puanlarını hesapla", süre, "ms");
};
es.execute (TtlRunnable.get (çalıştırılabilir));
başlangıç = bitiş;
end = başlangıç + num;
}
countDownLatch.await (session.config.linUcbTimeOut, TimeUnit.MILLISECONDS);
}
özel void getLinUcbScore (Oturum oturumu, INDArray özellikleri, Liste < Öğe > items, int start, int end) IOException {
eğer (items.isEmpty () || null == özellikler)
dönüş;
StopWatch stopWatch = StopWatch.CreateStopWatchAndStart ();
for (int i = start; i < end; ++ i) {
stopWatch.restart ();
Öğe öğesi = öğeler.get (i);
uzun pid = item.getProductId ();
bayt matrisi = getLinUcbMatrix (oturum, pid);
INDArray özelliği = features.getRow (i);
INDArray featureT = feature.transpose ();
Logger.detail (" < ", ben, " > ", pid," öğe özelliği: ", item.getTrackInfo ()," vektör: ", özellik);
if (matrix == null) {
double p = session.config.linUcbAlpha * FastMath.sqrt (feature.mmul (featureT) .getDouble (0));
item.setMatchScore (p);
Logger.info (" < ", ben, " > linucb yeni öğe: ", pid," ucb puanı: ", p);
devam et;
}
ByteArrayInputStream in = new ByteArrayInputStream (matrix);
INDArray Ab = ByteSerde.fromByteArrayStream (in);
eğer (Ab.uzunluk < 2)
devam et;
INDArray invertA = Ab;
INDArray b = Ab;
Logger.detail (" < ", ben, " > ", pid," alınan matrisi getir ", stopWatch.click ()," ms ");
eğer (b.length ()! = özellik.length ()) {
Logger.error ("b'nin uzunluğu", b.length (), "olmalıdır", feature.length ());
double p = session.config.linUcbAlpha * FastMath.sqrt (feature.mmuli (featureT) .getFloat (0));
item.setMatchScore (p);
devam et;
}
INDArray theta = invertA.mmul (b);
INDArray thetaX = theta.transposei (). Mmul (featureT);
INDArray temp = feature.mmuli (invertA) .mmul (featureT);
çift p = thetaX.getDouble (0);
item.setPreferScore (p);
p + = session.config.linUcbAlpha * FastMath.sqrt (temp.getDouble (0));
item.setMatchScore (p);
Logger.detail (" < ", ben, " > ", pid," bir yineleme linucb puanı alındı ", stopWatch.click ()," ms. eşleşme puanı: ", p);
}
}
Matris hesaplama kısmının uygulanmasında ND4J (https://nd4j.org/) kütüphanesi kullanılmaktadır.
6. İş etkisi
Tam bir çevrimiçi A / B testinden sonra, nihayet, LinUCB algoritmasının UV CTR'sinin kıyaslama variline kıyasla% 25 + arttığı ve UV değerinin% 20 + arttığı ölçüldü. Ve algoritma, malların dinamik olarak yüklenmesini ve boşaltılmasını iyi bir şekilde destekleyebilir.
7. Referans
Kişiselleştirilmiş Haber Makale Önerisine Bağlamsal-Haydut Yaklaşımı.
Transfer: https://yangxudong.github.io/linucb/
