CoBoosting - CoBoosting

CoBoost, Collins ve Singer tarafından 1999'da önerilen yarı denetimli bir eğitim algoritmasıdır. Algoritmanın orijinal uygulaması, Adlandırılmış Varlık Sınıflandırması çok zayıf öğrenenler kullanıyor.^[1] Özelliklerde fazlalık olduğu durumlarda yarı denetimli öğrenmeyi gerçekleştirmek için kullanılabilir.

Bir kombinasyonu olarak görülebilir ortak eğitim ve artırma. Her örnek iki görünümde (özellik setinin alt bölümleri) mevcuttur ve güçlendirme, önceki yinelemenin alternatif görünümünde üretilen tahmin edilen etiketleri kullanarak her görünümle dönüşümlü olarak yinelemeli olarak uygulanır. CoBoosting, şu ülkelerde geçerli bir yükseltme algoritması değildir. PAC öğrenimi anlamda.

Motivasyon

CoBoosting, Collins ve Singer tarafından, sınıflandırıcıları yarı denetimli bir şekilde eğitmek için özelliklerde fazlalıktan yararlanmaya yönelik önceki girişimleri geliştirme girişimiydi. Blum ve Mitchell'in ufuk açıcı bir çalışması olan CoTraining'in, bir karar listesindeki kuralları yinelemeli olarak teşvik ederek az sayıda tohum örneği verilen sınıflandırıcıları öğrenmek için güçlü bir çerçeve olduğu gösterildi. CoBoosting'in CoTraining'e avantajı, CoTraining modelini herhangi bir sınıflandırıcıyla kullanılabilecek şekilde genelleştirmesidir. CoBoosting, bu başarıyı kavramları ödünç alarak gerçekleştirir. AdaBoost.

Hem CoTrain hem de CoBoost'ta eğitim ve test örnek setleri iki özelliği takip etmelidir. Birincisi, örneklerin özellik uzayının, her bir görünümün sınıflandırma için yeterince açıklayıcı olacağı şekilde iki özellik alanına (veya görünüme) ayrılabilmesidir. Resmi olarak iki işlev vardır ${displaystyle f_ {1} (x_ {1})}$ ve ${displaystyle f_ {2} (x_ {2})}$ öyle ki tüm örnekler için ${displaystyle x = (x_ {1}, x_ {2})}$, ${displaystyle f_ {1} (x_ {1}) = f_ {2} (x_ {2}) = f (x)}$. İdeal olsa da, bu kısıtlama aslında gürültü ve diğer faktörler nedeniyle çok güçlüdür ve her iki algoritma bunun yerine iki işlev arasındaki anlaşmayı en üst düzeye çıkarmaya çalışır. İkinci özellik, iki görünümün yüksek oranda ilişkilendirilmemesi gerektiğidir.

Algoritma

Giriş: ${displaystyle {(x_ {1, i}, x_ {2, i})} _ {i = 1} ^ {n}}$, ${displaystyle {y_ {i}} _ {i = 1} ^ {m}}$

Başlat: ${displaystyle forall i, j: g_ {j} ^ {0} ({oldsymbol {x_ {i}}}) = 0}$.

İçin ${displaystyle t = 1, ..., T}$ ve için ${displaystyle j = 1,2}$:

Sözde etiketleri ayarlayın:

${displaystyle {hat {y_ {i}}} = sol {{egin {dizi} {ll} y_ {i}, 1leq ileq m sign (g_ {3-j} ^ {t-1} ({eski sembol {x_ {3-j, i}}})), m$

Sanal dağıtımı ayarlayın:${displaystyle D_ {t} ^ {j} (i) = {frac {1} {Z_ {t} ^ {j}}} e ^ {- {hat {y_ {i}}} g_ {j} ^ {t -1} ({eski sembol {x_ {j, i}}})}}$

nerede ${displaystyle Z_ {t} ^ {j} = toplam _ {i = 1} ^ {n} e ^ {- {hat {y_ {i}}} g_ {j} ^ {t-1} ({eski sembol {x_ {j, i}}})}}$

Zayıf hipotezi bulun ${displaystyle h_ {t} ^ {j}}$ genişletilmiş eğitim hatasını en aza indirir.

İçin değer seçin ${displaystyle alpha _ {t}}$ genişletilmiş eğitim hatasını en aza indirir.

Mevcut güçlü eşiksiz sınıflandırıcının değerini güncelleyin:

${displaystyle forall i: g_ {j} ^ {t} ({eski sembol {x_ {j, i}}}) = g_ {j} ^ {t-1} ({eski sembol {x_ {j, i}}}) + alfa _ {t} h_ {t} ^ {j} ({eski sembol {x_ {j, i}}})}$

Son güçlü sınıflandırıcı çıktısı

${displaystyle f ({oldsymbol {x}}) = signleft (toplam _ {j = 1} ^ {2} g_ {j} ^ {T} ({eski sembol {x_ {j}}}) ight)}$

AdaBoost'u kurma

CoBoosting, AdaBoost AdaBoost diğer birçok öğrenme algoritması ile birlikte kullanılabildiğinden, CoBoosting'e genelleme yeteneğini veren algoritma. Bu birikim, iki sınıflı bir sınıflandırma görevi üstlenir, ancak birden çok sınıf sınıflandırmasına uyarlanabilir. AdaBoost çerçevesinde, zayıf sınıflandırıcılar seri halinde üretilir ve ayrıca eğitim setindeki örnekler üzerinden bir dağıtım yapılır. Her zayıf sınıflandırıcıya bir ağırlık verilir ve son güçlü sınıflandırıcı, atanmış ağırlıklarına göre ağırlıklandırılan zayıf sınıflandırıcıların toplamının işareti olarak tanımlanır. (Görmek AdaBoost Gösterim için Wikipedia sayfası). AdaBoost çerçevesinde Schapire ve Singer, eğitim hatasının aşağıdaki denklemle sınırlandırıldığını göstermiştir:

${displaystyle {frac {1} {m}} toplam _ {i = 1} ^ {m} e ^ {sol (-y_ {i} sol (toplam _ {t = 1} ^ {T} alfa _ {t} h_ {t} ({eski sembol {x_ {i}}}) ight) ight)} = prod _ {t} Z_ {t}}$

Nerede ${displaystyle Z_ {t}}$ dağılım için normalleştirme faktörüdür ${displaystyle D_ {t + 1}}$. İçin çözme ${displaystyle Z_ {t}}$ denkleminde ${displaystyle D_ {t} (i)}$ biz alırız:

${displaystyle Z_ {t} = toplam _ {i: x_ {t} otin x_ {i}} D_ {t} (i) + toplam _ {i: x_ {t} içinde x_ {i}} D_ {t} ( i) e ^ {- y_ {i} alfa _ {i} h_ {t} ({eski sembol {x_ {i}}})}}$

Nerede ${displaystyle x_ {t}}$ mevcut zayıf hipotezde seçilen özelliktir. Mevcut hipotezin doğru veya yanlış etiketi seçtiği dağılımların toplamını açıklayan üç denklem tanımlanmıştır. Sınıflandırıcının, verilen etiketin 0 olduğu bir örnek için bir etiket seçmekten kaçınmasının mümkün olduğuna dikkat edin. İki etiket -1 veya 1 olacak şekilde seçilir.

${displaystyle W_ {0} = toplam _ {i: h_ {t} (x_ {i}) = 0} D_ {t} (i)}$

${displaystyle W _ {+} = toplam _ {i: h_ {t} (x_ {i}) = y_ {i}} D_ {t} (i)}$

${displaystyle W _ {-} = toplam _ {i: h_ {t} (x_ {i}) = - y_ {i}} D_ {t} (i)}$

Schapire ve Singer, değerin ${displaystyle Z_ {t}}$ seçilerek en aza indirilebilir (ve dolayısıyla eğitim hatası) ${displaystyle alpha _ {t}}$ aşağıdaki gibi olmak:

${displaystyle alpha _ {t} = {frac {1} {2}} solda ({frac {W _ {+}} {W _ {-}}} ight)}$

Örnekler üzerinden dağılıma göre ağırlıklandırılan yanlış sınıflandırılmış örneklerin sayısına karşılık doğru sınıflandırılanların sayısına göre mevcut varsayılmış sınıflandırıcı için güven değerleri sağlamak. Bu denklem, aşağıdaki durumları telafi etmek için düzeltilebilir ${displaystyle W _ {-}}$ çok küçük. Türetme ${displaystyle Z_ {t}}$ bu denklemden şunu elde ederiz:

${displaystyle Z_ {t} = W_ {0} +2 {sqrt {W _ {+} W _ {-}}}}$

Böylece eğitim hatası, önceki denklemi en aza indiren her yinelemede zayıf hipotez seçilerek en aza indirilir.

İki manzaralı AdaBoost

CoBoosting, etiketli bir eğitim setine sahip olunması durumunda bu çerçeveyi genişletir (örneklerden ${displaystyle 1 ... m}$) ve etiketlenmemiş bir eğitim seti ( ${displaystyle m_ {1} ... n}$) şeklindeki özelliklerde fazlalık koşullarını karşılamanın yanı sıra ${displaystyle x_ {i} = (x_ {1, i}, x_ {2, i})}$. Algoritma, iki sınıflandırıcıyı aynı şekilde eğitir AdaBoost etiketli eğitim üzerinde anlaşan, doğru etiketleri belirler ve etiketlenmemiş eğitim setinde iki sınıflandırıcı arasındaki anlaşmayı en üst düzeye çıkarır. Son sınıflandırıcı, iki güçlü sınıflandırıcının toplamının işaretidir. CoBoost üzerindeki sınırlı eğitim hatası aşağıdaki şekilde uzatılır, burada ${displaystyle Z_ {CO}}$ uzantısı ${displaystyle Z_ {t}}$:

${displaystyle Z_ {CO} = toplam _ {i = 1} ^ {m} e ^ {- y_ {i} g_ {1} ({eski sembol {x_ {1, i}}})} + toplam _ {i = 1} ^ {m} e ^ {- y_ {i} g_ {2} ({eski sembol {x_ {2, i}}}} + toplam _ {i = m + 1} ^ {n} e ^ {- f_ {2} ({eski sembol {x_ {2, i}}}) g_ {1} ({eski sembol {x_ {1, i}}}} + toplam _ {i = m + 1} ^ {n} e ^ {- f_ {1} ({eski sembol {x_ {1, i}}}) g_ {2} ({eski sembol {x_ {2, i}}})}}$

Nerede ${displaystyle g_ {j}}$ hipotezlerin ağırlıklarının, güven değerleri ile toplamıdır. ${displaystyle j ^ {th}}$ görünüm (j = 1 veya 2). ${displaystyle f_ {j}}$ işaretidir ${displaystyle g_ {j}}$. CoBoost'un her yinelemesinde, her iki sınıflandırıcı da yinelemeli olarak güncellenir. Eğer ${displaystyle g_ {j} ^ {t-1}}$ için güçlü sınıflandırıcı çıktısı ${displaystyle j ^ {th}}$ kadar görüntüle ${displaystyle t-1}$ yineleme için sözde etiketleri ayarlayabiliriz j. güncelleme şu şekilde olacaktır:

${displaystyle {hat {y_ {i}}} = sol {{egin {dizi} {ll} y_ {i} 1leq ileq m sign (g_ {3-j} ^ {t-1} ({eski sembol {x_ { 3-j, i}}})) m$

İçinde ${displaystyle 3-j}$ diğer görünümü o anda güncellenmekte olana seçer. ${displaystyle Z_ {CO}}$ öyle ikiye ayrılır ki ${displaystyle Z_ {CO} = Z_ {CO} ^ {1} + Z_ {CO} ^ {2}}$. Nerede

${displaystyle Z_ {CO} ^ {j} = toplam _ {i = 1} ^ {n} e ^ {- {hat {y_ {i}}} (g_ {j} ^ {t-1} ({eski sembol { x_ {i}}}) + alfa _ {t} ^ {j} g_ {t} ^ {j} ({eski sembol {x_ {j, i}}})}}$

Her görünüm için örnekler üzerinden dağılım ${displaystyle j}$ yinelemede ${displaystyle t}$ aşağıdaki gibi tanımlanır:

${displaystyle D_ {t} ^ {j} (i) = {frac {1} {Z_ {t} ^ {j}}} e ^ {- {hat {y_ {i}}} g_ {j} ^ {t -1} ({eski sembol {x_ {j, i}}})}}$

Hangi noktada ${displaystyle Z_ {CO} ^ {j}}$ olarak yeniden yazılabilir

${displaystyle Z_ {CO} ^ {j} = toplam _ {i = 1} ^ {n} D_ {t} ^ {j} e ^ {- {hat {y_ {i}}} alfa _ {t} ^ { j} g_ {t} ^ {j} ({eski sembol {x_ {j, i}}})}}$

AdaBoost'taki denklem ile aynıdır. Böylece aynı işlem, değerlerini güncellemek için kullanılabilir. ${displaystyle alpha _ {t} ^ {j}}$ AdaBoost'ta olduğu gibi kullanarak ${displaystyle {hat {y_ {i}}}}$ ve ${displaystyle D_ {t} ^ {j}}$. Bunu değiştirerek, ${displaystyle Z_ {CO} ^ {1}}$ ve ${displaystyle Z_ {CO} ^ {2}}$ bu moda da ${displaystyle Z_ {CO}}$ açgözlü bir şekilde küçültülür.

Referanslar

Dipnotlar