2019-11-14

なぜ疑似ラベルが効果的か調べてみた

機械学習

はじめに

なぜ疑似ラベル ( Pseudo-Label ) が効果的かを知るために、「Pseudo-Label : The Simple and Efficient Semi-Supervised Learning Method for Deep Neural Networks」を読んだので、内容を記載します。

http://deeplearning.net/wp-content/uploads/2013/03/pseudo_label_final.pdf

疑似ラベル ( Pseudo-Label ) とは

疑似ラベルを使った半教師あり学習の方法

1. ラベルづけされているデータで学習済みモデルを作る
2. 1.で作成したモデルを使って、ラベルづけされていないデータで予測値を出す
3. 2.の予測値を疑似的なラベル、疑似ラベルとし、疑似ラベルづきデータをラベルづきデータに混ぜて学習する

なぜうまくいくのか

Abstractを読むと「エントロピー正則化として作用するから」と書かれてました。

これだけだとよく分からなかったので、順を追って読んでみました。
多クラス分類問題を扱っています。

損失関数

損失関数を、ラベル付きデータと未ラベルデータで分けて表現すると、以下のように記載できます。
$n$ がラベル付きデータの個数で、 $n'$ が未ラベルデータの個数で、 $C$ がクラス数です。

$\displaystyle{L = \dfrac{1}{n}\sum_{m=1}^{n}\sum_{i=1}^{C}L(y_{i}^{m}, f_{i}^{m}) + \alpha(t) \dfrac{1}{n'}\sum_{m=1}^{n'}\sum_{i=1}^{C} L(y_{i}^{'m}, f_{i}^{'m})}$

第 1 項目がラベル付きデータのLoss、第 2 項目が未ラベルデータのLossで、その合計が全体のLossです。

ここで、未ラベルデータの疑似ラベルで、以下のように、ネットワークの出力の最大予測確率を持つクラスを選択します。

$y'_i= \begin{cases} 1 & \text{if $i = argmax_{i'} f_{i'}(x)$} \\ 0 & \text{otherwise} \end{cases}$

この損失関数の $\alpha(t)$ はバランスを取るための係数で、徐々に大きくなるようにスケジューリングする必要があるそうです。あまりにも高いと学習を阻害し、低すぎると疑似ラベルの恩恵を受けられなくなるのだそう。

エントロピー 正則化

エントロピー正則化は、エントロピーを最小化することで、クラス間の境界部分を低密度な状態 ( 境界にデータがあまりなくてが分類しやすい状態 ) にしてくれるそうです。
エントロピーは各クラスのデータのオーバーラップに対する評価値となります。

エントロピーは以下のように表されます。
$\displaystyle{H(y|x^{\prime})=-\dfrac{1}{n^{\prime}}\sum_{m=1}^{n^{\prime}} \sum_{i=1}^{C}P(y_{i}^{m} = 1 | x^{\prime m}) logP(y_{i}^{m}=1|x^{\prime m})}$

$n'$ : 未ラベルデータの個数
$C$ : クラスの個数
$x'_{\prime m}$ : 未ラベルデータ
$y_{i}^{m}$ : 未ラベルデータの疑似ラベル

先ほどの損失関数 (各 $L$ : 交差エントロピー誤差) の両辺に負の値をとり、損失関数の最小化問題をMAP推定 ( 事後確率を最大化するようなパラメータを推定する問題 ) に置き換えるため、先ほどのエントロピーの式も合わせて、以下のように書き直して考えます。

$\displaystyle{C(\theta, \lambda) = \sum_{m=1}^{n}logP(y^{m}|x^{m}; \theta) - \lambda H(y|x'; \theta)}$

これを最大化させるので、未ラベルデータのエントロピー（第2項）を最小化して、ラベル付きデータの対数尤度（第1項）を最大化することになり、ラベル付きデータだけの学習よりもパフォーマンスがよくなるそうです。

結果

MNISTのデータを使い、Pseudo-Labelを使ったものと使わなかったものとで、t-SNEにより比較しています。
確かに、Pseudo-Labelを使ったものの方が、各クラス間の境界部分が低密度な状態になっていると言えそうです。
f:id:YukoIshizaki:20191114113855p:plain:w300

終わり

完全に腑に落ちるところまで理解することはできなかったです( ˘ω˘ ; )

KaggleでもPseudo-Labelが上手くいく場合と、上手く行かない場合があるように見受けられ、疑似ラベル付きデータをどのくらいの数、どのタイミングで入れるかが難しいのかな、と思いました。

記載に誤りがあれば教えていただけたら嬉しいです。

終わり 2

転職して、まだ入社していないのですが ( 12月から入社です \( •̀ω•́ )/ ) 次の会社の勉強会に参加させてもらってます。めっちゃ面白いです。
今回のブログも、勉強会中で疑問になったことをきっかけに調べてみようと思って書きました。

ちなみに、勉強会の内容ですが、先輩がGitHubで公開してくれています！！良きです！
github.com

参考
https://papers.nips.cc/paper/2740-semi-supervised-learning-by-entropy-minimization.pdf
https://pdfs.semanticscholar.org/1ee2/7c66fabde8ffe90bd2f4ccee5835f8dedbb9.pdf
arxiv.org

2019-11-10

推薦のアルゴリズムを調べた

はじめに

基本的な推薦のアルゴリズムについて勉強しました。

「推薦システム: 統計的機械学習の理論と実践」を参考に、一部ピックアップして、要点を記載しました。

Pythonで実装する場合、使えそうなライブラリも一緒に記載しています。

www.kyoritsu-pub.co.jp

はじめに
推薦のタスク
古典的手法
探索と活用
推薦システムの評価
ランク学習
Dataset
おわり

古典的手法

bag-of-words

アイテム素性ベクトルを構成するためにbag-of-wordsベクトル空間モデルを使用。各単語を次元として扱う。
このベクトル空間に写像する方法。

バイナリ表現

単語の有無を0,1で表現

TF

単語の出現率

$\textrm{tf}(t,d) = \dfrac{n_{t,d}}{\sum_{k \in d}n_{k,d}}$

$n_{t,d}$ : 単語 t の文書 d 内での出現回数

TF - IDF

文書中に含まれる単語の重要度を表す。
まず IDF 逆文書頻度を以下とする。

$\textrm{idf}(t) = \log{\dfrac{N}{df(t)}}$

$N$ : 全文書数
$df(t)$ : ある単語 t が出現する文書の数

TF-IDF は以下であわらされる。

$\textrm{tf-idf}(t, d) = tf(t, d) \cdot idf(t)$

sklearn.feature_extraction.text.TfidfVectorizer — scikit-learn 0.21.3 documentation

次元削減

bag-of-wordsの表現は、次元が大きくなってスパースネスになってしまう。
それを抑える代表的な方法。

類義語拡張

類義語を加えてスパース性に対応
日本語 Wordnet
SudachiDict/synonyms.md at develop · WorksApplications/SudachiDict · GitHub

素性選択

過剰に出現率が高い/低い単語は無視する

特異値分解

行列Xを以下のように分解して、σiが重要度を表すので、重要の低いものを削除してしまう。

$X = (\boldsymbol{u}_1, \boldsymbol{u}_2, \cdots, \boldsymbol{u}_n) \begin{pmatrix} \sigma_1 & & & \\ & \sigma_2 & & \\ & & \ddots & \\ & & & \sigma_n \end{pmatrix} \begin{pmatrix} \boldsymbol{v}_1^{\mathrm{T}} \\ \boldsymbol{v}_2^{\mathrm{T}} \\ \vdots \\ \boldsymbol{v}_n^{\mathrm{T}} \end{pmatrix}$

numpy.linalg.svd — NumPy v1.17 Manual

ランダム射影

距離関係を保ったまま次元削減する。

sklearn.random_projection.SparseRandomProjection — scikit-learn 0.21.3 documentation

トピックモデル

文章からトピックを推定する。
LDAモデルが単語を生成する仕組みを学習するもの。

トピック分布

文章が各トピックに属する確率

トピック分布を以下のようにあわらす
$\Theta_{d} = \{ \theta_{(d, 0)}, \theta_{(d, 1)}, \dots, \theta_{(d, k)} \}$

ベクトルの和が 1 であるシンプレックス。

例 )
$\Theta_{d} = \{ 0.3, 0.2, \dots, 0.1 \}$

トピック0 がゲームなら、ゲームに属する確率は0.3
トピック1 が教育　なら、教育に属する確率は0.2
トピックk が IT　　なら、IT に属する確率は0.1

潜在トピック

文章 d の各単語 0~n に対して、それぞれ潜在トピックが存在しており、それはトピック分布から生成される。

$Z = \{z_{(d, 0)}, z_{(d, 1)}, \dots, z_{(d, n)} \}$

単語の生起確率

トピックk における、各単語 0~n の生起確率が存在し、各単語の潜在トピックとそのトピックの単語出現率から実際の単語が生成される。

$\Phi_{k} = \{ \phi_{(k, 0)}, \phi_{(k, 1)}, \dots, \phi_{(k, n)} \}$

トピック分布は、全トピック数の次元のベクトルをパラメータにもつ、ディリクレ分布から生成される。

単語の生起確率も、全単語数の次元のベクトルをパラメータにもつ、ディリクレ分布から生成される。

そのパラメータを変分近似またはギブスサンプリングで推定するらしいが....パラメータ推定の部分の理解は省略。

gensim: models.ldamodel – Latent Dirichlet Allocation

協調フィルタリング

アイテムの評価行動が似ている2人のユーザは嗜好が似ていると言える。ユーザ i に類似する他のユーザの集合を得て、アイテムを好む程度を予測する。

ユーザ間の類似度に基づいた手法

ユーザ i と似ているユーザがアイテム j に与えた評価を元に、ユーザ i がまだ評価していないアイテム j のレイティング(スコア)を以下のように表す。

$s_{ij} = \bar{y_{i}} + \dfrac{ \sum_{l \in T } w(i,l)(y_{lj} - \bar{y_{l}} )}{ \sum_{l \in T} |w(i,j)|}$

$\bar{y_{i}}$ : ユーザ i の平均レイティング
$y_{l j}$ : ユーザ l のアイテム j に対すレイティング
$T$ : ユーザ i に似ていて、アイテム j を評価したユーザの集合
$w(i,l)$ : ユーザ i がアイテム j を評価する時のユーザ j に対する重み

重み $w(i,l)$ を一般的には以下のユーザ間の類似度 $sim_{(i, l)}$ で表す。

ユーザ間の類似度

ユーザ i とユーザ l の類似度。

$sim_{(i, l)} = \dfrac{ \sum_{l \in J_{il} } (y_{ij} - \bar{y_{i}} ) (y_{lj} - \bar{y_{l}} )}{ \sqrt{\sum_{j \in J_{il}} (y_{ij} - \bar{y_{i}} )^2} \sqrt{\sum_{j \in J_{il}} (y_{lj} - \bar{y_{l}} )^2}}$

$J_{i,l}$ : ユーザ i とユーザ l の両方に評価されたアイテムの集合

アイテム間の類似度に基づいた手法

アイテム j と似ているアイテムに与えられた評価を元に、ユーザ i がまだ評価していないアイテム j のレイティング(スコア)を以下のように表す。

$s_{ij} = \bar{y_{i}} + \dfrac{ \sum_{l \in J } w(i,l)(y_{lj} - \bar{y_{l}} )}{ \sum_{l \in J} |w(i,j)|}$

$J$ : ユーザ i によって評価されたアイテム j と似ているアイテムの集合

探索と活用

多腕バンディット

複数のスロットマシーンで各マシーンの当たりが出る確率がわからない状況で、腕を選択する試行を繰り返し報酬を最大にする課題。

探索と活用のトレードオフ問題に対する、いくつかのアプローチがある。

ベイジアンアプローチやミニマックスアプローチがあるが、実践でよく使われる、ヒューリスティックなバンディット戦略を記載。

$\varepsilon$ - グリーディ

$\varepsilon$ の確率で探索をし、 $1 - \varepsilon$ で活用(報酬確率の推定値が最大となる選択)をする。
過度の探索をさせないために時間の経過と共に、 $\varepsilon$ を減少させる。
例えば、今の時点で腕を引いた総数 $n$ に対して、 $\varepsilon_{n} = min \{ 1, \frac{\delta}{n} \}$ とする。

SoftMax

腕を探索する確率を以下のようにする方法。 $\tau$ はハイパーパラメータ。良さそうな腕を多く探索できるが、分散を考慮できていない。

$\dfrac{e^{\hat{p_i}/\tau}}{\sum_{j} e^{\hat{p_j}/\tau}}$

$\hat{p_i}$ : 腕 i から得られた報酬の標本平均

Thompson Sampling

スロットマシーンごとにベータ分布を以下のように定めて乱数を発生させて、その値が大きかったマシーンを引く。

$Be(\alpha + 1, \beta + 1)$

$\alpha$ : そのマシーンで当たりがでた回数
$\beta$ : そのマシーンでハズレがでた回数

Most-Popular推薦

ポジティブなレスポンスを最大化させるため、全てのユーザに最も人気のあるアイテムを推薦する方法。ユーザの個別化は行わない。

ただし、昼間のデータを使って、夜間の人気アイテムを推定するようなケースだとバイアスがかかる可能性があるため、カルマンフィルタや単純指数加重移動平均などを使ってバイアスを取り除く必要がある。

個別化推薦

ユーザを荒いセグメントに分類して、各セグメントに対してMost-Popular推薦を適応する。セグメントを特定するために決定木やクラスタリングを使う。

ランク学習

ランク学習は素性ベクトルからアイテムのスコアリストへの写像を学習。

その写像を
$F(x) = (f(x_1), f(x_2), f(x_3), \dots, f(x_n))$

とし、教師データは以下のように表す

$\mathcal{L} = \{ l_1, l_2, \dots ,l_n \}$

Pointwise approach

1つのアイテムに対して、ランキングのどの位置かを予測するアプローチ。

損失関数の例

$L'(F(x), y) = \sum_{k=1}^{i}(f(x_i)-l_i)^2$

Pairwise approach

2つのアイテムに対して、どっちの方がランキングが上かを予測するアプローチ。

損失関数の例

$L'(F(x), y) = \sum_{s=1}^{n-1}\sum_{i=1, l_i < l_s}^{n} \phi (f(x_s)-f(x_i))$

$\phi$ はヒンジ関数や指数関数など。

Listwise approach

複数のアイテムに対して、それぞれのアイテムがランキングではどの位置かを予測するアプローチ。ランキング全体としての良さを求めている。

損失関数の例

$L'(F(x), y) = \sum_{s=1}^{n-1}(-f(x_{y(s)}) + ln( \sum_{i=s}^{n} exp(f(x_{y(i)})))$

$y(i)$ は i 番目にランクづけされたオブジェクトをさす

RankNet

NNを利用したPairwise approach。

$f$ をモデルとし、２つのアイテム $x_i$ 、 $x_j$ のスコアを $f(x_i) = s_i$ 、 $f(x_j) = s_j$ とする。
アイテム $x_i$ の方が $x_j$ よりランクが高いことを、 $x_i\triangleright{x_j}$ と書く。

$x_i\triangleright{x_j}$ となる確率を以下のように定める。

$P_{ij} = \dfrac{1}{1+ exp(-( f(x_i) - f(x_j)))}$

損失関数はクロスエントロピーとし、勾配降下法で最適化する。

$C_{ij} = -\bar{P}_{ij} \log P_{ij} -(1-\bar{P}_{ij}) \log (1-P_{ij})$

$\bar{P}_{ij}$ は真の確率で、以下のように定める。

$\bar{P}_{ij}= \begin{cases} 1 & \text{if ${x_i} \triangleright {x_j}$} \\ 0 & \text{if ${x_j} \triangleright {x_i}$} \\ 1/2 & \text{otherwise} \end{cases}$