カシミアのニット

カシミヤのニット

日々のメモです

An Adaptive Version of the Boost by Majority Algorithm

An Adaptive Version of the Boost by Majority Algorithm

Freund, Y.: An adaptive version of the boost by majority algorithm, Machine Learning, vol. 43, no. 3, pp. 293‒318, 2001.

link.springer.com

実装はこちらです.

github.com

以前ゼミで,Introduction to ensemble methods for beginners Introduction to ensemble methods for beginners

というタイトルで以下のようなアンサンブルについての概要を簡単にまとめた資料を発表しました(突貫工事なのでまとまりがないのは目を瞑っていただきたく).

その中でも,History of Boosting節のBrownBoost*1について今回は紹介します.

BrownBoost

本論文では,AdaBoostがノイズに弱い*2という特徴を考慮したBrownBoostを提案しています.

本論文以外でも,ノイズ耐性を持つBoostingは提案されています*3

しかし,PACの枠組みの中で定義されている正式なブースティング特性はありません.

そこで,FreundはBoosting-By-Majorityを適用することでノイズ耐性を受け継いだPACに基づいたBrownBoostを提案しました.

Boosting-By-Majority*4

Boosting-By-Majority(以下,BBM)は,Freundによって提案された最初のブースティングアルゴリズムです.

また,ノイズ耐性*5があります.

しかし,BBMを使用するためには,基本学習器の誤差限界パラメータとして与える必要があり,実用には向きません.

BBMとBrownBoostの関係

このパラメータを削除した手法がBrownBoostです.

具体的には,パラメータを削除し,候補モデルの誤差に適応的に最終的なアンサンブルを生成します.

BrownBoostでは,候補モデルの数を指定するパラメータはなく,代わりに cというパラメータがあります.

このパラメータによって”残り時間”が決められます.

この”残り時間”は,BrownBoostのイテレーションに関するパラメータです.

また,候補モデルが訓練された時,”残り時間”と分類マージンに基づいてそのモデルの重みが決まります.

そして,その重みに基づいて”残り時間”は減算されます.

この分類マージンにより,BBMやBrownBoostでは各インスタンスを正解するように候補モデルを訓練することができます.

一方で,各候補モデルの正答率が低いインスタンスに対しては,負のマージンが割り当てられ,そのようなインスタンスはノイズであると判断されます.

これがBBM,BrownBoostがノイズに強い所以です.



BrownBoostのイテレーションは,”残り時間”が収束するまで続きます.

候補モデルの重み付き誤差によって決まるのでアルゴリズムの実行時間はBBMに比べて非常に長くなり得ます.

この問題に関しては,候補モデルの誤差を0.5に近づけた時のアンサンブルの振る舞いを考えることで答えることが可能です.

モデルの誤差を(1/2 - \delta)とし,時間 tにおけるアンサンブルの出力を \sum h(x)と表します.

この時,時間を t=\delta ^2 iをすると,BrownBoostの収束後の時間は \deltaとは無関係の定数となり,これにより下式で表現される”位置”を定義します.

\begin{align} r_\delta(t) = \delta \sum^{\lceil t/\delta^2 \rceil}h(x) \end{align}

モデルの誤差を0.5に近づけることが前提であり,この時の”位置r_\delta(t)”は下式で得られる平均 \mu(t)と分散 \sigma ^2 (t)によって特徴付けられるブラウン運動による連続時間確率過程r(t)に近づきます.

{
\begin{align}
\mu(t) = \int_{0}^{t} \frac{1}{\gamma(s)}ds
\end{align}
}
{
\begin{align}
\sigma^{2}(t) = t
\end{align}
}

ここで, 1/2 - \gamma(t)は時刻tにおけるモデルhの重み付き誤差を表します.

ここまでで誤差を0.5に近づけた時のアンサンブルの振る舞いがわかりました.

ここからはBBMで定義される重みの限界を考えます.

BBMの重み関数は二項分布であり,以下で表します.

\begin{align} \alpha^i_r = {}_{k_\delta - i - 1} C _{\lfloor k_\delta/2 \rfloor - 2} \biggl(\frac{1}{2} + \delta \biggr)^{\lfloor k_\delta/2 \rfloor - r} \biggl(\frac{1}{2} - \delta \biggr)^{\lfloor k_\delta/2 \rfloor - i - 1 + r} \end{align}

ここで, k_\deltaイテレーションの回数で,iは現在のイテレーション番号です.

rはこれまでの正しい予測の数です.

前述のr_\deltatの定義から誤差を0.5に近づけると\alpha^{i}_{r}の限界を得ることができます.

\begin{align} \alpha(t,r) = \exp \biggl(-\frac{(r(t)+c-t)^2}{c-t} \biggr) \end{align}

ここで, c = \lim_{\delta \to 0} \delta ^2 k_\deltaです.

同様に,誤差限界は下式のように表せます.

\begin{align} \beta^i_r = \sum^{\lfloor k_\delta/2 \rfloor - r} {}_{k_\delta - i} C _{j} \biggl(\frac{1}{2} + \delta \biggr)^{j} \biggl(\frac{1}{2} - \delta \biggr)^{\lfloor k_\delta \rfloor - i - j} \end{align}
\begin{align} \beta(t,r) = \frac{1}{2}\biggl(1 - erf \biggl(\frac{r(t)+c-t}{\sqrt{c-t}} \biggr) \biggr) \end{align}

ここで, erf(\cdot)は誤差関数であり,下式で表現されます.

\begin{align} erf(a) = \frac{2}{\pi}\int_{0}^{a} \exp(-x^2)dx \end{align}

以上のようにtr(t)\alpha(t,r),及び,\beta(t,r)の定義が与えられると、BBMアルゴリズムを連続時間領域に変換できるようになります.

この領域では,BBMを実行する代わりに,候補モデルの誤差が0.5である分布に対応するtの値を定義する微分方程式を解くことで近似解を得ることができます.

また,BrownBoostの損失関数は,\beta(t,r)に対応した形になり,同様に近似によって多項式時間での収束が可能となります.

ブラウン運動のシュミレーション

ブラウン運動は,連続時間ランダムウォークをモデル化したものです.

2次元ブラウン運動のシュミレーションを行い,その結果を可視化しました.

f:id:lapis_zero09:20180330014413p:plain
2次元ブラウン運動のシュミレーション

実装はここにあるので,遊んでみてください.

BrownBoost/brownian_motion.ipynb at master · lapis-zero09/BrownBoost · GitHub

BrownBoostの実装

BrownBoostのアルゴリズムは以下に示すとおりです.

f:id:lapis_zero09:20180330014919p:plain

アルゴリズム中ステップ3は論文に示されているとおり,Newton-Raphson法により解を導いています.

実装はこちらです.

github.com

実験

ここに簡単な実験を示しています.

BrownBoost/brownboost.ipynb at master · lapis-zero09/BrownBoost · GitHub

感想など

尻すぼみ感が否めませんが,明日も朝から研修なので許して.

後ほど追加実験をします.

*1:Freund, Y.: An adaptive version of the boost by majority algorithm, Machine Learning, vol. 43, no. 3, pp. 293‒318, 2001.

*2:Dietterich, T. G.: An experimental comparison of three methods for constructing ensembles of decision trees: Bagging, boosting, and randomization. Machine Learning, 40:2, 139–158.

*3:Friedman, J., Hastie, T., Tibshirani, R.: Additive logistic regression: a statistical view of boosting. Ann. Statist. 28 (2000), no. 2, pp. 337-407.

*4:Freund, Y.: Boosting aweaklearning algorithm by majority. Information and Computation, 121:2, 256–285.

*5:J. a. Aslam and S. E. Decatur, General bounds on statistical query learning and PAC learning with noise via hypothesis boosting, Proc. 1993 IEEE 34th Annu. Found. Comput. Sci., vol. 118, pp. 85‒118, 1993.

pythonのlambda式をtex形式に変換する

pythonのlambda式をtexに変換する

pythonで書いた数式と本来の数式を比較して正しいか見るのが意外とめんどくさいです.

sympy.simplifyとsympy.latexを使うとsympyで定義した数式をtex形式に変換することができます.

これらを利用してlambda式を与えるとtex表記を返してくれる関数が以下です.

gist.github.com

Model Compression

Model Compression

Bucilua, C., Caruana, R. and Niculescu-Mizil, A.: Model Compression, Proc. ACM SIGKDD, pp. 535–541 (2006).

https://dl.acm.org/citation.cfm?id=1150464

モデル圧縮

この論文はHintonらによるDistilling the Knowledge in a Neural Network*1の先駆けとなった論文です.

Once the cumbersome model has been trained, we can then use a different kind of training, which we call “distillation” to transfer the knowledge from the cumbersome model to a small model that is more suitable for deployment. A version of this strategy has already been pioneered by Rich Caruana and his collaborators.

[1503.02531] Distilling the Knowledge in a Neural Network

Hintonらの"distillation"では,soft targetと呼ばれる教師モデルが各正解クラスに対して出力した確率分布を入力として与えます.

これにより,教師モデルが相対的に間違った答えを導き出した場合でも,生徒モデルは教師モデルの確率という情報を新たに得ることで正解できるように訓練できる場合があります.

この時,教師モデルに含まれる基本モデルの予測分布の算術または幾何平均をsoft targetとしています.

一方,Caruanaらの提案では,教師モデルによって予測したone-hotなクラスラベルを正解ラベルとして生徒モデルを学習します.

これだけでは,生徒モデルは元の訓練データで訓練できるモデルよりもいいパフォーマンスを発揮できません.

教師モデルの性能を維持したまま元の訓練データで訓練できる軽量なモデルよりも優れたモデルを得るために擬似データを使用しました.

Model Compression*2

Caruanaらは,同論文でMUNGEと呼ばれる擬似データ生成手法を提案し,訓練データから大量のラベルなし擬似データを生成し訓練に用いました.

ラベルなし擬似データは,教師モデルによってラベル付けし,生徒モデルの訓練に利用します.

MUNGEのアルゴリズムは以下の通りです.

f:id:lapis_zero09:20180322174833p:plain
Pseudo code of MUNGE

MUNGEは見ての通り非常にシンプルな擬似データ生成手法です.

まず,訓練データ内のインスタンス {e}について,最近傍を発見します.

次に,確率パラメータに基づいて最近傍とインスタンス {e}から得られる正規分布からランダムに値を得ます.

これを各インスタンスに対し,複数回行うことで任意数の擬似データを得ることができます.

MUNGEの実装はこちらです.

github.com

Caruanaらは,MUNGEを用いたモデル圧縮によって教師モデルと同等の精度を持ち,教師モデルよりも高速かつ軽量な生徒モデルを得ています.

f:id:lapis_zero09:20180322175855p:plain

簡単な実験

irisデータを使って擬似データ生成アルゴリズムMUNGEの簡単な実験を行います.

詳細はこちらです.

github.com

正規化したirisデータは以下のようにプロットできます.

f:id:lapis_zero09:20180322215209p:plain
iris with normalization

このデータに対してMUNGEで擬似データを生成した結果が以下です.

f:id:lapis_zero09:20180322215304p:plain
p = 0.5, s = 10.0

良さそうですね.

しかし,確率パラメータを低くすると擬似データ数が多くなった場合,過学習する可能性が高くなります.

f:id:lapis_zero09:20180322220200p:plain
p = 0.8, s = .01

導出アルゴリズムからわかるように分散パラメータが小さすぎると明らかにおかしいデータが出来上がります.

f:id:lapis_zero09:20180322215543p:plain
p = 0.8, s = 1.0

一見良さそうですが,データが密集しすぎていて経験的にこのような場合は過学習することがあります.

f:id:lapis_zero09:20180322215624p:plain
p = 0.8, s = 10.0

いい感じです.

f:id:lapis_zero09:20180322215709p:plain
p = 0.8, s = 100.0

少し規則的に並び過ぎて人工データ感が否めません.

感想など

MUNGEはとてもシンプルなアルゴリズムであるが,データの特徴をよく捉えた擬似データを生成できます.

しかし,クラスの決定境界を意識して擬似データを生成しているわけではありません.

よって,上述のirisデータのプロットにおける青と緑のように境界面で接地したデータを分離しづらくなってしまいます.

あくまでも,モデル圧縮の文脈における擬似データ生成アルゴリズムなので教師モデルの特徴を活かしてこの辺りを改善したいですね.

*1:Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. In In Deep Learning and Representation Learning Workshop, NIPS, 2014.

*2:Bucilua, C., Caruana, R. and Niculescu-Mizil, A.: Model Compression, Proc. ACM SIGKDD, pp. 535–541 (2006).

Selective Ensemble under Regularization Framework

Selective Ensemble under Regularization Framework

Li, N. and Zhou, Z.-H.: Selective Ensemble under Regularization Framework, Proc. MCS, pp. 293–303 (2009).

link.springer.com

実装はここに置いています.

github.com

アンサンブル枝刈り

アンサンブル枝刈りはensemble pruningとも呼ばれます.

アンサンブル枝刈りは訓練された複数の基本モデルが与えられた上で,その全てを結合するのではなく,部分集合を選択することです.

アンサンブル枝刈りにより,より小さなサイズのアンサンブルでより良い汎化性能を得ることが期待されます.

Tsoumakasらは,アンサンブル枝刈りを順序付けに基づく枝刈り,クラスタリングに基づく枝刈り,最適化に基づく枝刈りの3つのカテゴリーに分類しました*1

この詳しい話については後ほど別の記事にしようと思ってます.

今回はその中でも最適化に基づく枝刈りに属するRSE(regularized selective ensemble)についてです.

RSE(regularized selective ensemble)*2

RSEはLiとZhouによって提案されたアンサンブル枝刈りをQP問題へと帰着させる手法です.

この手法の良いところは,従来のアンサンブル枝刈り手法よりもアンサンブルに含まれる基本モデルの数が少ないにもかかわらず,その性能がいいという点です.

また,正則化項にグラフラプラシアン正則化を用いており,半教師あり学習の場面でも使用することができます.

それでは詳しく見ていきましょう.

{M}個のモデル{\{h_1, \ldots, h_M\}}に対し,アンサンブル結合重みベクトルを{\boldsymbol{w} = [w_1, \ldots, w_M]^{\mathrm{T}}}と定義します.

この時,{w_i \geq 0} かつ {\sum_{i=1}^{M}w_i = 1}です.

RSEは,以下の正則化リスク関数を最小化することにより{\boldsymbol{w}}を決定します.

\begin{align} R(\boldsymbol{w}) = \lambda V(\boldsymbol{w}) + \Omega(\boldsymbol{w}) \end{align}

ここで,{V(\boldsymbol{w})}は訓練データ{D = {(\boldsymbol{x}_1, y_1), \ldots, (\boldsymbol{x}_N, y_N)}}に対する誤分類の経験損失で, {\Omega(\boldsymbol{w})}正則化項であり, {\lambda}{V(\boldsymbol{w})}{\Omega(\boldsymbol{w})}の最小化における正則化パラメータを表す.

ヒンジ損失とグラフラプラシアン正則化項をそれぞれ経験損失と正則化として用いることにより,問題は下式で定式化されます.

\begin{align} & \underset{\boldsymbol{w}}{\text{minimize}} & & \boldsymbol{w}^{\mathrm{T}}{\boldsymbol{PLP}^{\mathrm{T}}}\boldsymbol{w} + \lambda\sum_{i=1}^N {\text{maximize}}(0, 1 - y_i\boldsymbol{p}_i^{\mathrm{T}}\boldsymbol{w})\\ & \text{subject to} & & \boldsymbol{1}^{\mathrm{T}}\boldsymbol{w} = 1, \; \boldsymbol{w} \geq \boldsymbol{0}. \label{eq:hinge_laplacian} \end{align}

ここで,{\boldsymbol{p}_i = (h_1(\boldsymbol{x}_i), \ldots, h_M(\boldsymbol{x}_i))^{\mathrm{T}}}は訓練データ{\boldsymbol{x}_i}に対する個々のモデルの予測を表し, {\boldsymbol{P} \in {{-1, +1}}^{M \times N}}は全訓練データに対する全モデルの予測を集めた予測行列で, {\boldsymbol{P}_{ij} = h_i(\boldsymbol{x}_j)}です.

{\boldsymbol{L}}は訓練データの近傍グラフ{G}の正規化グラフラプラシアンです.

グラフラプラシアンの詳細については,長くなってしまうので件の論文や他文献に譲ります.

行列{G}の重み付け隣接行列を{\boldsymbol{W}}で表し,{\boldsymbol{D}}{D_{ii} = \sum_{j=1}^N W_{ij}}の対角行列です.

この時,{\boldsymbol{L} = \boldsymbol{D}^{-\frac{1}{2}}(\boldsymbol{D} - \boldsymbol{W})\boldsymbol{D}^{-\frac{1}{2}}}となります.

上式の{maximize(\cdot)}は滑らかではので,スラック変数{{\boldsymbol{\xi}} = (\xi_1, \ldots, \xi_m)^{\mathrm{T}}}を導入することにより,上式は下式で書き表せます.

\begin{align} & \underset{\boldsymbol{w}}{\text{minimize}} & & \boldsymbol{w}^{\mathrm{T}}{\boldsymbol{PLP}^{\mathrm{T}}}\boldsymbol{w} + \lambda\boldsymbol{1}^{\mathrm{T}}\boldsymbol{\xi} \\ & \text{subject to} & & y_i\boldsymbol{p}_i^{\mathrm{T}}\boldsymbol{w} + \xi_i \leq 1, \; (\forall i = 1, \ldots, N) \\ & & & \boldsymbol{1}^{\mathrm{T}}\boldsymbol{w} = 1, \; \boldsymbol{w} \geq \boldsymbol{0}, \; \boldsymbol{\xi} \geq \boldsymbol{0}. \label{eq:hinge_laplacian_slack} \end{align}

この時,上式は標準的なQP問題となり,従来の最適化パッケージを用いて,効率的に解くことができます.

また,{\boldsymbol{1}^{\mathrm{T}}\boldsymbol{w} = 1, \boldsymbol{w} \geq \boldsymbol{0}}という制約は、スパース誘導性を持つ{l_1}ノルム制約となり,重み{\boldsymbol{w}}のいくつかの要素を強制的にゼロにします.

この特徴により,従来のアンサンブル枝刈り手法よりもアンサンブルに含まれる基本モデルの数が少ないにもかかわらず,それなりの性能を出すことができます.

また,簡単な例を代入すればわかりやすいのですが,正則化 {\boldsymbol{PLP}}の部分が似ているデータに対して違うラベルを割り当てると正則化するという振る舞いをします.

導出された結合重みベクトル{\boldsymbol{w}}を用いて,下式のようにアンサンブルの予測を得ます.

\begin{align} H(\boldsymbol{x}) = \sum_{w_i > 0}w_ih_i(\boldsymbol{x}) \quad\text{(RSE-w)} \label{eq:rse-w} \end{align}

また,下式のように{\boldsymbol{w}}の要素がゼロでない候補モデルの投票により予測を決定する選択的アンサンブルも提案されています.

\begin{align} H(\boldsymbol{x}) = \sum_{w_i > 0}h_i(\boldsymbol{x}) \qquad\text{(RSE)} \label{eq:rse} \end{align}

少なくともerrorに関してはなかなかいい結果です.

f:id:lapis_zero09:20180321163932p:plain

errorだけの比較なのは,あまりいい感じはしませんが,アンサンブルの目指す所的にいいのかな

実装

実装はここに置いています.

github.com

最適化を行う前に,グラフラプラシアンに用いる行列{\boldsymbol{W}}を導出する必要があります.

これは,pythonでは遅すぎたのでJavaで実装しています.

しかし,訓練データはnpz形式で保存していたので,pythonでデータを読み込んでpy4j*3で起動したJavaサーバで計算を行っています.

    /**
     * get the matrix W for Laplacian
     * @return w_link filename
     * @throws Exception
     */
    public String[] getKernelLinkMatrix(byte[] data, String fold) throws Exception {
        System.out.println("\t\t[*] Hello from Java!");
        // get the link matrix
        // create java matrix from numpy
        Instances d = createFromPy4j(data);
        Matrix LMat = new Matrix(m_numInst, m_numInst);
        RBFKernel krl = new RBFKernel();
        double g = 0.5 / m_numAttr;
        krl.setGamma(g);
        krl.buildKernel(d);

        System.out.println("\t\t[*] calculating w_link on Java...");
        for (int i = 0; i < m_numInst; i++) {
            for (int j = 0; j <= i; j++) {
                double vt = krl.eval(i, j, d.instance(i));
                LMat.set(i, j, vt);
                LMat.set(j, i, vt);
            }
        }
        d = null;
        krl = null;
        System.out.println("\t\t[-] calc done...");

        return returnFilename(LMat, m_numInst, fold);
}

ラプラシアン行列の計算や重みの最適化はMatlabで行いました.

本件ではpythonよりも速く,また,最適化パッケージであるmosek*4の扱いが簡単だったためです.

mosekは論文でも採用されており,QP問題に関しては最速らしいです.

function Lap = LaplacianMatrix(W)
% compute the laplacian matrix
%
% Input:
%       W: the line matrix
% Output:
%       Lap: the laplacian matrix


D = diag(sum(W,2));
N = D^(-0.5);
Lap = N *(D-W)* N;
function weight = compute_weight(lambda, Y, Prd, Q, dirname);
% compute the weights for the base classifiers
%
% Input:
%       Cfr: the ensemble classifier, which contains multiple base
%       classifiers
% Output:
%       weight: the weights for the base classifiers in the ensemble


% M : set the size of classifiers
% N : set the size of training data
[M, N] = size(Prd)
NumVar = M + N;

% ---- Prepare QP ----
%equal constaint

Aeq = [ones(1,M),zeros(1,NumVar - M)];
beq = 1;
% lower and upper bounds
lb = zeros(NumVar,1);
% Ax <= b
AP = Prd';
for id = 1:N
    AP(id, :) = AP(id, :) * Y(id);
end
AP = -1 .* AP;
A = [ AP, -1 * eye(N) ];
b = -1 * ones(N ,1);

% H
H = zeros(NumVar,NumVar);
H(1:M, 1:M) = Q;
% f
% lambda = 1.0;
f = lambda * [zeros(M,1);ones(N, 1)];

% Optimization Using QP - MOSEK
options = optimset('Display','off','TolFun', 1e-100);
x0 = quadprog(H,f,A,b,Aeq,beq,lb,[],[],options);
weight = x0(1:M);
weight((weight <= 1e-6)) = 0;
filename = sprintf('%sweight/weight_lambda_%d%s',dirname,lambda,'.csv')
disp(filename)
csvwrite(filename,weight);

簡単な実験

Phonemeデータセットに対して,5分割交差検証でRSEを使用しました.

SVM,KNN,Decision Tree,Bagged Decision Trees,Boosted Decision Trees,Boosted Decision Stumpsなどを様々なパラメータで767個のモデルをアンサンブルの候補としました.

このとき最もよかった候補モデルは,XGBoostではなくRandomForestで,mseが0.092937219730941698,f1が0.93484136670163342という値でした.

RSEは,mseが0.0859865470852018,f1が0.93981530924414192という結果だったので良くなっていますね.

best base model RSE
mse 0.0929372197309416 0.93484136670163342
f1 0.0859865470852018 0.93981530924414192

詳細は,

github.com

感想など

グラフラプラシアンを使っている以上うまく適合するデータとそうでないデータはもちろんあると思います.

また,この手法では,アンサンブル候補モデルに対する結合重みを二次計画問題と捉え最適解を導出しますが,候補モデルが一律に似たような性能を示している場合,二次計画問題となり得ず,解くことができません.

{l_1}ノルム制約を使って候補モデルの数をガンガン減らすのはとても理にかなっていると思ったので,回帰とかにも使えると嬉しいですね.

*1:Tsoumakas, G., Partalas, I. and Vlahavas, I.: An En- semble Pruning Primer, SUEMA, pp. 1–13 (2009).

*2:Li, N. and Zhou, Z.-H.: Selective Ensemble under Regularization Framework, Proc. MCS, pp. 293–303 (2009).

*3:https://www.py4j.org/

*4:https://www.mosek.com/

春はなぜか新しいWebページを作りたくなる

春はなぜかWebサイトを作りたくなる

なりません?

僕はなります.

https://www.lapis-zero09.xyz/profile/

https://www.lapis-zero09.xyz/profile/

https://www.lapis-zero09.xyz/profile/

iPhoneで見られることをあまり想定していないものになってしまいました.

デザイン教えて

水冷パーツの個人輸入

自作PCの水冷パーツ


ドル金利が低下し,日米金利差が縮小して円高となっていますね.

日経平均がぐんぐん下がってトップニュースにもなっていました.

円高となればやることは一つ,そう輸入です.

もともと,自作PCの2台目を作りたいと思い,1年くらい前からずっとパーツを集めていたのですが,今回の円高で水冷パーツを海外から輸入しました.

きっかけ

2台目の自作PCは,性能よりも見た目重視で組もうと考えていました.

そんな最中,ちょうど秋葉原の中古ショップで目星つけてたマザボが安売りしして,「これは組むしかない」と思い,今に至ります.

https://www.amazon.co.jp/ASUSTeK-Z170%E6%90%AD%E8%BC%89-LGA1151%E5%AF%BE%E5%BF%9C-SABERTOOTH-Z170/dp/B01ARORJF2/ref=sr_1_1?ie=UTF8&qid=1519552792&sr=8-1&keywords=SABERTOOTH%2FZ170%2FS

ASUSTeK Intel Z170搭載 マザーボード LGA1151対応 SABERTOOTH/Z170/S 【ATX】

スペック的には結構型落ち感が否めないです..が,今回は見た目重視ということで.

このマザボにはCPUとマザボと一緒に冷却できる一体型の水冷ブロックがあります.

EK-FB ASUS Z170S Monoblock - Nickel – EK Webshop

f:id:lapis_zero09:20180225175720j:plain
EK-FB ASUS Z170S Monoblock

この商品が,国内の水冷パーツショップではどこも扱ってなくて,個人輸入することにしました.

PPCS


注文

輸入はおなじみperformance-pcs社を利用しました.

ここで,EK-FB ASUS Z170S Monoblockを購入するんですが,Availability:Preoederとなっていました.

これは,「今お店に在庫がないから,注文してくれたらEKWB社に受注するよ!」ってことなので急いでもないし,そのまま注文します.

f:id:lapis_zero09:20180225181528p:plain
Availability: Preorder

EKWBのオンラインショップで購入しても良かったのですが,ポンプとリザーバは他社のを使おうと考えており,送料の関係上荷物をまとめたかったのでPPCSでPreorderしました.

配送

配送はFedExのInternational Economyにしました.

Preorderで時間かかるし,今更配送を早くしてもな..と思ったので,

注文の翌営業日に下図のようなメールが来ました.

f:id:lapis_zero09:20180225183337p:plain
from ppcs

知っての通り,EK-FB-ASUS-Z170S-MONO-NPはプレオーダー品だよ! EKからの荷物が次に届くのは2/16(金),2/19(月)だ! 君が注文した品物が全部揃ったらまとめて送るね!

とのことなので,待っていると2/19に

Order shipped on 02/19/2018 via FedEx FedEx International Economy with Tracking Number ************.

ときました.

注文したのが日本時間で2/10(土)でプレオーダー品確認のメールが来たのが2/12(月),

注文品が揃ったのが2/19(月)なのでプレオーダー品を注文すると発送まで1週間くらいかかることが分かりました.

急ぐ場合は,メールなどで注文前に直接確認した方がいいかもしれません.

以下は,FedExの追跡です.思ってたより追跡が細かくて丁寧ですごい.

f:id:lapis_zero09:20180301011417p:plain
FedEx追跡

「認可済み業者」は,セイノースーパーエクスプレスFedExの追跡番号そのままで追跡可能でした.

f:id:lapis_zero09:20180301011858j:plain

開封と構築の記事はまた今度

参考

blog.livedoor.jp

sandysoil.blog.fc2.com

memotora.com

The night, and the dream, were long...

はじめに

この記事はklis Advent Calendar 2017の21日目の記事です.

adventar.org

昨日はktmnさん(@piyopiyo_tititi)生活にアザラシを取り入れてから気が楽になった話 - 日記という記事でした. あざらし可愛いですね. 短気なので生活にあざらしを取り入れていきたいと思います.

kotori-tititi.hatenablog.com

さて,この記事の題目となっている"The night, and the dream, were long..."というセリフをご存知でしょうか.

"The night, and the dream, were long..."は,"Bloodborne"のラスボスの一人であるゲールマンのセリフです.

私(@lapis_zero09)は現在klis14の学生で卒業を間近に控えておりますが,大学生活は長いようで短く,夢のように過ぎ去っていきました. まだ残ったモラトリアムも有意義に過ごしたいです.

Bloodborneについて

さて,くさいセリフは置いておいてBloodborneは,FromSoftwareより出ているゲームです.

FromSoftwareは,Bloodborneの他に"DarkSouls"や"ARMORED CORE"などのソフトを出していることで知られています.

www.fromsoftware.jp

Bloodborneは,DarkSouls,及び,Demon's Soulsと並んでソウルシリーズと呼ばれ,その雰囲気やスタイリッシュさから壮絶な人気を博しています*1*2

また,Bloodborneは,"死にゲー"と呼ばれるほど難しく,かっこよさに惹かれ,始めたはいいものの途中で攻略を諦める人が後を絶ちません*3. しかし,その難しさを諸共せず,あるいは難しさに惚れ込み,四六時中このゲームのことを考えたり,プレイしたりする人間もおり,そのような人は地底人と呼ばれています*4

このBloodborneは,その他のFromSoftwareの作品と同様,ほとんどと言って良いほどゲームの世界観を伝えるNPCの台詞やムービーが無く,解釈の一切をユーザに委ねています. このことから,フロム脳を患うユーザが後を絶ちません. フロム脳とは,ゲームの設定を必要以上に考察してしまう精神病の一種で,重度の場合,現実世界の事象についても考察し始めます*5. フロム脳罹患者によるBloodborneに関する考察や2次創作は後を絶ちません.

フロム脳の発症者の中には高い技術力や文才を持った者もおり、こういった人々の解釈・考察・動画は作品の世界を更に広げていく可能性を持っているため、フロム脳をただの妄想癖と言って悪く決めつけきれないところがある。

出展:フロム脳とは (フロムノウとは) [単語記事] - ニコニコ大百科

前置きが長くなりましたが,この記事は何らかの形でBloodborneの二次創作を作成し,Bloodborneをより多くの人に知ってもらうと共に,Bloodborneを盛り上げ,フロム脳患者を増やし,あわよくばBloodborne2の発売を願うものです.

二次創作

そもそも私が,Bloodborneにハマったのは中の良い二人の悪いオタクが主な原因です. ある日,いつものようにたまり場にいる時,二人の悪いオタクが「お前もやってみろ」と私にPS4のコントローラを渡し,気づけば,無意識にBloodborneのことを考え,作業中にBloodborne考察動画を流し,また,大学から家までの道のりにある木の位置や階段の段数を考察するフロム脳の自分がいました.

そして,Bloodborneにハマった要因の一つに,"original soundtrack(以下,OST)の良さ"があります.楽団と聖歌隊によるコーラスによって重厚な曲は作業用のBGMに向いており,この記事の執筆時にも流しているほどです.

Amazon Musicにあるので是非聞いてみてください.

一方で,人間,同じ曲ばかり聴いていると飽きが生じてしまうもので,Bloodborneそのもののプレイにも支障を来すことになり兼ねません. OSTに含まれる曲数は限られ,ゲームの続編が出ない限りサウンドトラックが増えないことは想像に難くないでしょう.

なので,この記事では似たような曲を作ることを二次創作とします. しかし,私はピアノやギターは弾いたりするものの作曲に関しての知識は毛頭ありません. そこでその辺の機械学習ラボに属している私らしく機械学習によって作曲することを考えます.

作曲

まず,私が所持している音楽データは全てステレオmp3形式なので,音楽を学習・生成するニューラルネットワークを設計するために,ニューラルネットが理解できる形式に変換する必要があります.

皆さんご存知の通り,音波は連続的な信号であり,無限のデータ点に分割することが可能です. サンプリングでは,サンプリング周波数で決まる一定の時間間隔で信号の値を保存します. したがって,サンプリングによって無理やり有限のデータで連続信号を表すことを考えます. サンプリング周波数は44100Hzに設定しました. 一般的に,人間の耳は,20000Hzまでの周波数を聞き取ることができると言われています. したがって,20000Hzを超える周波数が存在しても,違いはないと想定します. また,Nyquist–ShannonのSampling Theorem*6によると,サンプリング周波数は20000Hzのほぼ2倍にする必要があります. したがって,44100Hzは理論的に学習可能なサンプリング周波数とみなすことができます.

次にステレオmp3をモノラルmp3に変換することで,音楽を空間性を持たないものに変換します. モノラルであるということは,例えばイヤホンで音楽を聞いた時,左右の耳から聞こえる音が同じであることを示しています. 簡単に言えば,モノラルサウンドは,ステレオサウンドを表現するために必要なマトリックスのサイズの半分で表現することができます. これにより,ニューラルネットワークを訓練するのにかかる時間だけでなく,必要なメモリも削減することができます.

しかし,モノラルに変換したと言えど,mp3は,圧縮形式であるというのには変わりなく,まだニューラルネットで学習するのに優れた形式ではありません. そこで,モノラルmp3をWAV形式に変換します. WAV形式は,FLAC以外に最も簡単に利用できる非圧縮オーディオであり,pythonライブラリであるscipyによって簡単に扱うことができます. これで,時間領域で圧縮されていないサンプリングされたオーディオ形式が得られました.

さらに,WAVファイルをニューラルネットが理解できるものに変換します. ニューラルネットに時間信号の異なる周波数をよりよく理解させるために,離散フーリエ変換(以下FFT)を使用して,時系列の複雑なデータを対応する周波数領域に変換しました. これで前処理の終わりではなく,FFTの出力は複素数の配列であり,ニューラルネットワークの入力にするために実数部と虚数部に分割する必要があります. また,時間が一致しないものはゼロパディングを行いました.

これにより,元のステレオmp3データは3次元のテンソルとして構造化することができました. この3次元マトリックスニューラルネットに与えることで音楽を生成します. これで前処理のタスクは終了しました.

次に発生する問題はニューラルネットアーキテクチャーをどう設計するかです. リカレントニューラルネットワーク(以下,RNN)は音声のような時系列データを扱うのに最適なニューラルネットワークです. シーケンスのすべての要素(このケースではテンソル)に対して,事前定義された操作を繰り返し実行するため,リカレントと呼ばれます. 重要な点は,次の一連の操作でも,前の計算の結果が考慮されることです. したがってRNNには情報を記憶できるmemoryがあることがわかります. 音楽データに対して考えると,ネットワークに一連の音符を与え,それはシーケンス全体を通って次の音符を予測します. しかしノーマルのRNNには,長い間情報を保持することができないという欠点があります. そこで,Long Short Term Memory(以下,LSTM)が提案されています. LSTMでは,セルと呼ばれる別のベクトルが情報を記憶するために用いられています. LSTMの大きな利点の1つは,学習する必要のあるパラメータの数が従来のネットワークに比べて少ないことです. 情報の転送・更新,出力の生成のための重みとして機能する基本的に3つの行列があります. 3つの行列は、シーケンスの各要素に対して操作を実行するために繰り返し使用されます RNNやLSTMに関するより詳細な情報はDeep Learning Book*7などを参照してください.

今回は,自前のGPUを使用したため計算的リソースは非常に限られており,浅いネットワークを構築しましたが,訓練には数日を要しました. モデルの生成と学習にはkerasを使用しました.

以下が生成した音楽例になります.

最初の方は良さげですね.

もっと潤沢なリソースで複雑なネットワークを扱うことでより皆さんの感性に合う音楽が作れるかもしれません.

最後に

明日は卒論の提出日ですが,最後まで気は抜けないのでそろそろ寝ることにします.

明日のklis Advent Calendar 2017はまっつんさん(@crc9dijo)の担当ですが,卒論の話が聞けるかもしれません.

おやすみなさい.


商品を買ってFromSoftwareを応援しよう!!

Mangakiチャレンジ

日記です.

Mangakiチャレンジに参加した.

マンガ・アニメを推薦するタスク

このコンペティションでは、アニメ・マンガに対するユーザの評価の予測に取り組んでもらいます。データセットとして、実際のユーザによる評価結果が提供されます。



0828に一発目を投げて,1位だったのでほったらかして結局4位だった.




予測タスクが簡単すぎた(?)のかどのモデルでもパフォーマンスが頭打ちの感


最終的にベースモデルにはSVMを使った.


評価値は,評価行列を作って,"ユーザ"と"アイテム"それぞれでクラスタリング(k-means).
クラスタ数は,施行により設定.


ユーザもアイテムも何千のオーダーだったけど,クラスタ数は一桁が一番良かった.




追加データも出たらしいけど見てない.





2位だった先輩の解法:http://nzw0301.github.io/2017/10/mangaki




このくらいのコンペなら隙間時間にできて良い.

意味表現学習まわり

CBOW, SG, GloVeについて

github.com

連続単語袋詰めモデル(continuous bag-of-words model,CBOW) と 連続スキップグラムモデル(continuous skip-gram model,SG) は Mikolovらによって提案された単語の分散的意味表現手法.

これらのモデルを公開しているツール→word2vec

CBOW

与えられた文脈の中で出現している文脈語を使って,ある対象語が出現しているかどうかを予測可能な意味表現を学習.

対象語 意味を表現したい単語 文脈語 ある単語の周辺に現れる単語

s = 「私はご飯と味噌汁を食べた.」について,

形態素は,[私,は,ご飯,と,味噌汁,を,食べた]

対象語を「ご飯」とすると,それ以外の語が文脈語として用い,「ご飯」の出現を予測.

CBOWモデルでは,文章中に[私,は,と,味噌汁,を,食べた]という文脈語が出現していた時に, その文章中に「ご飯」という単語が出現するかどうか予測できるように, それぞれの単語の意味表現ベクトルを更新することが目的.

1つの単語につき,d次元のベクトル

i番目の単語が対象語の場合,その単語の対象語ベクトル\boldsymbol{x}_iを使用.

i番目の単語が文脈語の場合,その単語の文脈語ベクトル\boldsymbol{z}_iを使用.

対象語\boldsymbol{x}が文脈中のi番目の単語して出現している場合, \boldsymbol{x}を中心とする(2k+1)個の単語からなる文脈 (i-k), \cdots, (i-1), i, (i+1), \cdots, (i+k)を使って予測する問題を考える.

この文脈中に出現する文脈語についての文脈ベクトルを  \boldsymbol{z}_{i-k}, \cdots, \boldsymbol{z}_{i-1}, \boldsymbol{z}_{i+1}, \cdots, \boldsymbol{z}_{i+k} とすると対象語の出現確率は,  p(\boldsymbol{x}_i|\boldsymbol{z}_{i-k}, \cdots, \boldsymbol{z}_{i-1}, \boldsymbol{z}_{i+1}, \cdots, \boldsymbol{z}_{i+k}) と表すことができる.

→ kを大きくするとより広い範囲で単語の共起が考慮可能.関係が低い離れた単語同士の共起も考慮されてしまう

→ kはCBOWのハイパーパラメータ.Mikolovらはk=2として5単語からなる文脈窓を用いて学習

問題:長い連続する単語列の出現は大きなコーパスについても少ない→その出現確率を推定することは難しい

CBOWにおける解決策:文脈語の出現順序を無視,下式で与えられる文脈語ベクトルの平均ベクトル\hat{\boldsymbol{x}}を,対象語xの文脈を代表するベクトルとして用いる.

\begin{align} \hat{\boldsymbol{x}} = \frac{1}{2k}(\boldsymbol{z}_{i-k} + \cdots + \boldsymbol{z}_{i-1} + \boldsymbol{z}_{i+1} + \cdots + \boldsymbol{z}_{i+k}) \end{align}

\boldsymbol{x}\hat{\boldsymbol{x}}を用いて,対象語の出現確率をソフトマックス関数で以下のように計算

\begin{align} p(\boldsymbol{x}_i|\boldsymbol{z}_{i-k}, \cdots, \boldsymbol{z}_{i-1}, \boldsymbol{z}_{i+1}, \cdots, \boldsymbol{z}_{i+k}) = \frac{\exp(\hat{\boldsymbol{x}}^{\mathrm{T}} \boldsymbol{x})}{\sum_{x' \in \boldsymbol{\nu}}\exp(\hat{\boldsymbol{x}}^{\mathrm{T}} \boldsymbol{x'})} \end{align}

\boldsymbol{\nu}コーパス中の全単語からなる語彙集合,\boldsymbol{x'}\boldsymbol{\nu}中の単語を表す

xが文章中に出現する可能性が高いほど右辺・分子の内積の値が大きくする

1つの単語について2つのベクトルが付与される(文脈語ベクトルと対象語ベクトル)→単語の共起をベクトルの内積で表現しているから

1つじゃダメなの?→1つの場合,\hat{\boldsymbol{x}}の中にもxが現れることになり,\boldsymbol{x}^{\mathrm{T}} xを小さくすることになる.

→ xの長さ(l2ノルム)を小さくすることになる

→ xのl2ノルムを変えてもソフトマックス関数はスケール不変

→ xをそのl2ノルムで割って正規化しても p(x_i|\boldsymbol{z}_{i-k}, \cdots, \boldsymbol{z}_{i-1}, \boldsymbol{z}_{i+1}, \cdots, \boldsymbol{z}_{i+k}) の値は変わらない

→異なる2つのベクトルを使うことでこの問題を解決

tips:単語の共起頻度を離散的な数ではなく,連続な値(ベクトルの内積)でモデル化しているので「continuous」

上記では出現順序を無視し,文脈語の平均を使って文脈を表現したが,出現順序を保つベクトルを作成することも可能

→文脈語のベクトルを連結する

SG

対象語を使って,文脈に出現している文脈語を予測する

対象語の「ご飯」を持ちいて,他の単語([私,は,と,味噌汁,を,食べた])の出現を予測

対象語xi番目の単語として出現している文脈で他の単語を同時に予測する場合の確率を下式で計算.

\begin{align} p(z_{i-k}, \cdots, z_{i-1}, z_{i+1}, \cdots, z{i+k}|x) = p(z_{i-k}|x)\cdots p(z_{i-1}|x)p(z_{i+1}|x)\cdots p(z_{i+k}|x) \end{align}

※対象語xが与えられているとき,文脈語が全て独立

独立性の仮定により,

\begin{align} p(z|x) = \frac{\exp(\boldsymbol{x}^{\mathrm{T}} \boldsymbol{z})}{\sum_{z' \in \boldsymbol{\nu} (x)}\exp(\boldsymbol{x}^{\mathrm{T}} \boldsymbol{z'})} \end{align}

(→「わかりやすいパターン認識」など参照のこと)

\boldsymbol{\nu} (x)は対象語xが出現している文脈中での文脈語の集合.ある特定の文脈でxと共起する文脈語の集合ではなく,コーパス全体におけるxが出現する全ての文脈に関しての文脈語の集合

CBOWと同様文脈として,対象語xを中心とするk個の単語からなる文脈窓を選ぶことも可能

→ kを固定せずに,それぞれのxの出現においてkとしてある区間内のランダム値を取るなど,文脈窓の幅を動的に決めることも可能

n個の単語それぞれについて,d次元の対象語ベクトルを学習

それぞれの単語について何らかの文脈で共起する文脈語が\boldsymbol{\nu} (x)なので,その単語全てについてd次元の文脈語ベクトルを学習


CBOWはSGに比べ,文脈語の独立性を近似していないため,より正確

1対1の共起をモデル化しているSGに比べ,CBOWは1対複数の文脈語をモデル化しているので,複数の文脈語からなる単語列がコーパス中に十分な回数現れなければならない

→CBOWはより大きなコーパスが必要

CBOWとSGのモデル最適化

SGのモデルについて,

\begin{align} p(z|x) = \frac{\exp(\boldsymbol{x}^{\mathrm{T}} \boldsymbol{z})}{\sum_{z' \in \boldsymbol{\nu} (x)}\exp(\boldsymbol{x}^{\mathrm{T}} \boldsymbol{z'})} \end{align}

xまたはzについて凸関数ではない→局所解が存在

xのある要素に注目するとxz内積はその要素に対して線形な関数となる

xzのどちらかを固定した場合,片方の関数について上式は凸関数となる→双線形関数,交互最適化可能

さらに,上式は\exp{()}を含むので対数をとることで対数双線形関数

xzを固定すると片方の変数に関してソフトマックス関数→多クラスロジスティック回帰としてみなせる

負例サンプリング

SGのモデルについて,単語の分散的意味表現を学習するために, ある単語と共起する単語(正例)だけでなく, 共起しない単語(負例)に関する情報も必要

→共起しない単語集合は膨大.その中から学習のために「良い負例」を選択しなければいけない

→この負例手法のことを負例サンプリング(Negative Sampling)

SGのNegative Sampling

ある単語xの分散的意味表現\boldsymbol{x}を求める問題を考える

正例として扱える文脈語の集合を\boldsymbol{D}_{pos} = \boldsymbol{\nu} (x)とし,負例の集合を\boldsymbol{D}_{neg} \in \boldsymbol{\nu}とする

それぞれの定義より,\boldsymbol{D}_{pos} \cup \boldsymbol{D}_{neg} = \phi

この時,SGモデルで定義される共起の予測確率に従い, 対数尤度を最大化するxの対象語ベクトルは下式で与えられる

\begin{align} \hat{\boldsymbol{x}} = argmax_{x} (\sum_{z \in \boldsymbol{D}_{pos}} \log(p(t=1|\boldsymbol{x} ,\boldsymbol{z})p_{pos}(z|x)) + \sum_{z \in \boldsymbol{D}_{neg}} \log(p(t=-1|\boldsymbol{x} ,\boldsymbol{z})p_{neg}(z|x))) \end{align}

右辺第1項は対象語xと共起する文脈語zに関する対数尤度を表す. その項のt=1は正例であることを示す.

p_{pos}(z|x)xの正例集合\boldsymbol{D}_{pos}での出現確率を表しており, 正例集合はコーパス中に出現している単語集合\boldsymbol{\nu} (x)なので, \sum_{z \in \boldsymbol{D}_{pos}} p_{pos}(z|x) = 1となる

右辺第2項について,負例\boldsymbol{\nu}はランダムにサンプリングしているためサンプリング手法に依存する.

本来なら負例は正例を除いた\boldsymbol{\nu}からサンプリングすべきだが, \boldsymbol{\nu}に比べ,\boldsymbol{D}_{pos}は極めて小さいため 近似的に\boldsymbol{D}_{neg}\boldsymbol{\nu}からサンプリングしている

→どの対象語xについても同一分布が使える利点

サンプリング手法は?

→SGではコーパス中で高出現確率である単語zが単語xの意味表現学習の負例として選ばれるように,単語zのユニグラム分布p(z)に基づいて負例集合を選択

負例が(x, z)のペアで決まるのなら,ユニグラム分布ではなく,xzの同時分布からサンプリングすべきでは?

→2単語の同時共起確率に比べ,1単語の出現確率がゼロになりにくいという利点.

→膨大なコーパスから共起を計算するには大きな共起表を作らなければならず,空間計算量という点で好ましくない

単語の出現はZipfの法則に従うのでp(z)ロングテールの分布となる.

p(z)を3/4乗した値に比例する分布をサンプリング分布として用いている.

→出現確率p(z)が小さい文脈語zも比較的高頻度でサンプリングされるようになる

以上より,

 \displaystyle
argmax_{x} (\sum_{z \in \boldsymbol{D}_{pos}} \log(p(t=1|\boldsymbol{x}, \boldsymbol{z})) + \sum_{z \in \boldsymbol{D}_{neg}} \log(1 - p(t=1|\boldsymbol{x}, \boldsymbol{z}) \tilde{p} (z)))
 \displaystyle
= argmax_{x} (\sum_{z \in \boldsymbol{D}_{pos}} \log(\sigma (\boldsymbol{x}^{\mathrm{T}} \boldsymbol{z})) + \sum_{z \in \boldsymbol{D}_{neg}} \log(\sigma (-\boldsymbol{x}^{\mathrm{T}} \boldsymbol{z})\tilde{p} (z)))

\sigma(\theta)はロジスティックシグモイド関数

第2項の負例に関するサンプリング分布\tilde{p}(z)xに無関係. よって,第2項を期待値の形で書き表すことが可能

\displaystyle
\sum_{z \in \boldsymbol{D}_{pos}} \log(\sigma (\boldsymbol{x}^{\mathrm{T}} \boldsymbol{z})) + E_{\tilde{p}(z)} [ \log(\sigma (-\boldsymbol{x}^{\mathrm{T}} \boldsymbol{z}))

1つの正例に対して,k個の負例を用いる.

負例はランダムに選択している擬似負例のため正例数に比べ,負例数を大きくしなければならない.

実用的にはk=20

word2vecに実装されているCBOWとSGでは, 非同期パラメータ更新による並列処理を行うことで学習時間の短縮

→複数のスレッドを用いて,同一学習モデルを更新していく.

→同じ学習モデルを更新すると互いに更新する値を打ち消しあう可能性,必ずしも正しく学習が行えるわけではない

より正確にするには

→オンライン学習の並列化でよく用いられるように反復的パラメータ混合方

→スレッドごとに独立にモデルを持たせて,独立的に学習させたモデルを足し合わせる

学習の正確さ トレードオフ 大量のデータから短時間で学習

階層型ソフトマックスによる近似計算

大規模なコーパスについて,多数の対象語と文脈語に関してベクトルを計算しなければならず, 高速に計算できることが望まれる.

\begin{align} p(z|x) = \frac{\exp(\boldsymbol{x}^{\mathrm{T}} \boldsymbol{z})}{\sum_{z' \in \boldsymbol{\nu} (x)}\exp(\boldsymbol{x}^{\mathrm{T}} \boldsymbol{z'})} \end{align}

右辺分母は全文脈語彙集合にわたって規格化しなければならず,この計算に時間がかかる

解決策

→単語の階層構造を事前に事前に用意し,それに従って規格化を行う→階層型ソフトマックス

→単語の出現を考慮する代わりに,その単語を含むグループを考慮できるので, 式中の和の計算を行う際に,考慮すべき語彙集合を小さくできる

ある単語xがある1つのグループにのみ含まれるようにグループ分けされていれば, 全単語集合ではなく,このグループ内でのみxの確率を規格化しておけば良い

言語モデル構築の際に,単語そのものの出現頻度の代わりに,単語グループの出現頻度を使うことで出現頻度が少ない単語の出現確率を求める手法から発想を得ている

単語の階層構造をどのようにして作るか

  1. 階層的クラスタリングで全ての単語を含む階層構造を作成
  2. すでに構築されている概念構造を使う
  3. WordNet→単語を語義ごとにグループ化
    • グループ間で上位下位関係が記述されている

階層的クラスタリングWordNetを使って大規模なコーパスから単語の分散的意味表現を学習する際の問題点

  • 階層的クラスタリングの場合

    1. 単語と単語間の類似度とグループとグループ間の類似度を計算しなければならないため,計算時間がかかる

    2. どのような類似度尺度を使うべきかが明確ではない

    3. 階層的クラスタリングによって作られる階層構造が,類似度尺度によって変わる
  • WordNetの場合

    • WordNetに登録されていない単語をどのように分類するか

word2vecではハフマン木を使うことで単語の階層構造を構築

→単語の出現頻度を計算し,出現頻度の高い順にソート

→階層的クラスタリングよりも計算量の点で有利

コーパス中の全ての単語がハフマン木のノードで表されているので未知語の問題が起きない

単語の階層構造を用いて,どのようにして確率P(z|x)を計算するか

ハフマン木上で単語zに対する頂点を見つけ,根からその頂点への経路Path(z)を求める

各ノードでは-1もしくは1という2つの枝があるため,p(z|x)の予測確率をロジスティック関数を使って,次のように近似できる

 \displaystyle
p(z|x) = \frac{\exp(\boldsymbol{x}^{\mathrm{T}} \boldsymbol{z})}{\sum_{z' \in \boldsymbol{\nu} (x)}\exp(\boldsymbol{x}^{\mathrm{T}} \boldsymbol{z'})}
 \displaystyle
\approx \prod_{(l,y) \in Path(z)} p( t=l | \boldsymbol{x}, \boldsymbol{y})
 \displaystyle
= \prod_{ (l,y) \in Path(z)} \sigma( l \boldsymbol{x}^{\mathrm{T}} \boldsymbol{y})

yは根から単語zに対する葉への経路上のノードを表し,lは各ノードでの枝の値(1, -1)を表し, このlに対応する確率変数がt

ハフマン木は単語の出現頻度だけを使って構築されているので, 単語の意味的関係を反映しているとは言えないが元の式を近似するには十分な階層構造である.

大域ベクトル予測モデル

CBOWとSGはコーパスを一文単位で処理し,単語毎の2つのベクトルを更新している

→単語の共起を予測する際に,一文に含まれている情報しか使うことができない

→分散的意味表現ベクトルを学習する際に一文中の共起共起情報ではなく, 分布的意味表現のように,コーパス全体における2つの単語共起情報を使う手法

→大域ベクトル予測モデル(global vector prediction,GloVe)

分布的意味表現のように,コーパス全体における対象語と文脈語のコーパス全体における共起頻度を計算し, 共起行列\boldsymbol{x}を作成

\boldsymbol{x}の各行が対象語・各列が文脈語に対応しているとする

→ i番目の対象語ij番目の文脈語jが共起する確率回数を \boldsymbol{x}(i,j)番目の要素 \boldsymbol{x}_{ij}

次の目的関数を最小化する対象語ベクトル\boldsymbol{x}_iと文脈語ベクトル\boldsymbol{z}_jを学習

\begin{align} J = \sum_{i,j=1}^{|\boldsymbol{\nu}|}f(X_{ij})(\boldsymbol{x}_i^{\mathrm{T}}\boldsymbol{z}_j + b_i + b_j - \log(X_{ij}))^2 \end{align}

b_ib_jスカラーのバイアス項

→対象語ベクトルと文脈語ベクトルの内積を用いて,この共起頻度の対数を予測

関数fは次の3つの性質を満たす関数

  1. f(0)=0
  2. x \to 0のとき\lim_{x \to 0} f(x)\log^2(x)が有限の値を持つ.

    • 共起頻度が0であるペアに関してもJが無限大に発散してしまうのを防ぐ
  3. f(x)は単調増加関数.

  4. 低共起頻度のペアを過剰評価するのを防ぐ

  5. f(x)はある閾値以上の共起頻度に関しては比較的小さな値を持つ

  6. 不要語など高頻出する単語との共起を過剰評価するのを防ぐ

GloVeはfに下式を採用

{} $$ f(t) = \begin{array}{} (t/t_{max})^\alpha & (t < t_{max}) \\ 1 & (otherwise) \end{array} $$

J\boldsymbol{x}_iあるいは\boldsymbol{z}_jのどちらか一方を固定させた場合, 片方に対して線形であり,双線形関数.

→交互最適化手法


GloVeがCBOW SGと大きく異なる点→負例を必要としない

→負例サンプリングを行うための様々な仮定や近似が不要になる

n個の単語の共起情報を保存するためには{n(n-1)/2 - n}個の変数(自分自身の共起は計算しないので-n)が必要となる

→空間情報量としてはO(n^2)のオーダーの変数が必要

→共起行列をどのように計算するかがGloVeを用いて学習するための重要な前処理タスク

→実際どうするか

  1. 分散処理
  2. コーパス全体における各単語の出現頻度を求め,頻度が小さいものは共起行列に含まないようにする.
  3. 出現頻度の低いもの→スペルミスの可能性
  4. 出現頻度が低いと共起の可能性も低い→信頼できる統計情報が得られない可能性
  5. 共起行列を構築するために最低2回コーパスを処理しなければならない

→CBOWとSGは一文単位で学習できるのでオンライン学習が可能

意味表現の評価

分散的意味表現において,ベクトルの各次元がどのような意味に対応しているか分かっていない

→学習された意味表現を別のタスクに応用し, その応用先タスクにおける精度がどれくらい出るかで正確さを評価

→間接的評価方法

→評価対象を直接評価→直接的評価方法

間接的評価方法

→CBOWやSGでは分散的意味表現を学習するのにある文脈において2つの単語が共起するかを予測している

→共起が正確に予測できているかで評価可能

単語の意味表現の正確さを評価するために用いられるタスク

  1. 2つの単語間の意味類似性を予測するタスク
  2. 2つの単語ペア間の関係類似性を予測するタスク

意味的類似性予測タスク

単語同士の意味がどれくらい似ているか (意味的類似性(semantic similarity))を求めることができれば, 意味が近い単語同士に高い類似性スコアが計算できるかどうかで 意味表現そのものの正確さを間接的に評価可能

意味的類似性は類義性(synonymy),関連性(relatedness)よりも広義な概念

例:「暑い」と「寒い」という対義語について 温度という属性は共通しているので意味的類似性が高い単語ペア

使ってみる

上記のCBOW,SG,GloVeに加え,分布的意味表現を日本語記事に対して適用してみる.

対象はlivedoorニュースコーパス

コードはここ(https://github.com/lapis-zero09/compare_word_embedding)に

全記事に対して,preprocess.pyで形態素解析を行い,gensimで処理可能な形にする.

解析器にはMeCabを用いて,辞書はipadic-nelogd

glove_pythonの導入に戸惑ったMacユーザは以下のREADMEを参照すると良いかも

https://github.com/lapis-zero09/compare_word_embedding

全ての形態素の原型を取り出し,一記事を一行にまとめる.

それぞれの学習は,

$ python w2v.py
$ python glove_train.py
$ python ppmi.py
$ python svd.py

それぞれイテレーション10,windowサイズ10,次元指定できるものは100次元で学習させた結果が以下

いずれもiphoneの類語を予測

CBOW_with_hs
[('iphone4', 0.515411376953125), ('webブラウザ', 0.4230906665325165), ('ios6', 0.4147755801677704), ('ipad', 0.4116036593914032), ('ipad2', 0.38188278675079346), ('アップル', 0.37905681133270264), ('iphone4s', 0.367786169052124), ('ソフトバンクbb', 0.36410054564476013), ('タンブラー', 0.36315712332725525), ('大丈夫', 0.35265758633613586)]

CBOW_with_ns15
[('iphone4', 0.6266778707504272), ('ipad', 0.6240962743759155), ('touch', 0.6063281297683716), ('ipod', 0.5750889778137207), ('ios', 0.5344790816307068), ('4s', 0.5055159330368042), ('アップル', 0.49820417165756226), ('ipad2', 0.4975413680076599), ('防水ケース', 0.4778713583946228), ('kobo', 0.47309401631355286)]

CBOW_with_hs_ns15
[('iphone4', 0.5731303691864014), ('iphone4s', 0.4358748197555542), ('ios', 0.42091381549835205), ('ipad2', 0.41879040002822876), ('アップル', 0.41285741329193115), ('防水ケース', 0.3713395595550537), ('ios6', 0.3705442547798157), ('ソフトバンクbb', 0.3699251115322113), ('ホカホンhd', 0.3648505210876465), ('コネクター', 0.36398276686668396)]

SG_with_hs
[('4s', 0.7601545453071594), ('ipod', 0.7516292333602905), ('ipad', 0.7158170938491821), ('touch', 0.7114615440368652), ('ios', 0.6660245656967163), ('第4世代', 0.6656962037086487), ('3gs', 0.6580607891082764), ('iphone4', 0.6171021461486816), ('配布', 0.5599908828735352), ('互換', 0.551994264125824)]

SG_with_ns15
[('ipad', 0.7440428733825684), ('4s', 0.741912305355072), ('ipod', 0.7315280437469482), ('3gs', 0.7070977091789246), ('touch', 0.672669529914856), ('ios', 0.6507753729820251), ('iphone4', 0.6480903625488281), ('第4世代', 0.6351419687271118), ('for', 0.6325072050094604), ('フリーペーパー', 0.5929508209228516)]

SG_with_hs_ns15
[('ipod', 0.7355147004127502), ('4s', 0.7283318042755127), ('ipad', 0.7088928818702698), ('touch', 0.6909142732620239), ('3gs', 0.6866996884346008), ('ios', 0.6676512956619263), ('iphone4', 0.6078430414199829), ('フリーペーパー', 0.6007919907569885), ('配布', 0.6005358695983887), ('第4世代', 0.6001726388931274)]

glove
[('ipad', 1.7425963151785258), ('アプリ', 1.4982636197187946), ('4s', 1.4977384448379325), ('ipod', 1.4966988373925263), ('4', 1.4776524801798216), ('touch', 1.3836936937733773), ('話題', 1.2830962460190283), ('使える', 1.267703173083845), ('用', 1.2650386013010513), ('向け', 1.26418467742026)]

ppmi
[('ipod', 0.2859661921087914), ('ipad', 0.24883286298039248), ('4s', 0.2447535806470899), ('touch', 0.2349337206345609), ('第4世代', 0.22949601240870882), ('3gs', 0.18854934562128067), ('4', 0.15223633417263555), ('ios', 0.14752415366324956), ('第3世代', 0.14382973978764851), ('据え置く', 0.13690344251866945)]

svd
[('売れ筋', 0.07950519361803438), ('touch', 0.07289990333758399), ('ガイガーカウンター', 0.0720546914668142), ('ipod', 0.06996932998910954), ('お浚い', 0.06655078247840501), ('ホルダー', 0.06373112962844232), ('電子書籍', 0.06339235714445059), ('スタンド', 0.062353061811765656), ('計測', 0.06080525440724401), ('ゲーム機', 0.06062771603307594)]

パラメータ最適化とかは以下の論文を参照のこと

参照

導入

klis14のしんさく (@lapis_zero09) | Twitterです.

この記事は,klis advent calendar 2016の23日目の記事です.

今日からクリスマス三連休ですね.

www.adventar.org

昨日は

本題

財布の膨らみ


突然ですがこれはなんでしょう.

f:id:lapis_zero09:20161218214236j:plain

そう筑波大生なら誰しもが持っている学生証ですね.

学生証の使い所は,身分証,筑波大附属図書館の入館・貸与証,コピー機での認証,各証明書・旅客運賃学生割引の発行などがあります.

人によってはあまり使わない機能もあるかもですね.

この機能を実現しているのは裏面のバーコードあるいは内蔵されているICチップです.

詳しく知りたい方はSony JapanのWebページ*1*2*3を御覧ください.

www.sony.co.jp

www.sony.co.jp

有益


せっかく財布に入れて持ち歩いているのですから,もっと有益に使いたいですね.

学生証のICチップはクレジットカードのように剥き出しなものではなく,完全に内蔵されているタイプであり,非接触型のICカードリーダを用いて内容を読み込むことができます.

非接触ICカードリーダには以下のようなものがあります.

www.sony.co.jp

このカードリーダとnfcpy*4を用いることで学生証のICチップを読み取ることができます.

Python module for near field communication — nfcpy 0.13.4 documentation

nfcpyのインストールについては割愛します.

nfcpyのexampleであるtagtoolを用いて以下のように学生証のID,PMM,SYSを取得することができます.

f:id:lapis_zero09:20161218222559p:plain

IDは製造ID(IDm)のことで8バイトのバイト列です.上位2バイトの値が製造者コード,続く6バイトがカード識別番号です.

PMMは製造パラメータのことで,こちらも8バイトのバイト列です.これはカードの種別および性能を識別するためのパラ メータです.

SYSはシステムコードのことで,システムを特定するための2バイトの値です.

また,Type3とありますから学生証は「JIS X 6319-4」に準拠したソニーFeliCaをベースとしていると認識されています.

さらに,筑波大学の学生証は裏面にロゴがある通り,FCFフォーマット*5です.

ここ*6には,FCFキャンパスカードフォーマット仕様*7に準拠したものとありますね.

有効活用したい


klisの研究室の入室には学生証とは別のICカードが必要です.

どうせなら学生証で入れるようにしてほしいというのは誰しもが思うことですね.

いきなり研究室に設置するのは色々問題がありそうなので,筆者のマンションでデモを行います.

まず,先ほどのICカードリーダに加え,みんな大好きRaspberry Piとサーボを用意し,繋ぎます.

サーボはGWSサーボ GWSMIRMGFA(MICRO/2BBMG/FP) フタバ: パーツ一般 秋月電子通商 電子部品 ネット通販です.

サーボの操作はServoBlasterを用いて行うことができます.

nfcpyとカードリーダで取得したパラメータを照合し,合致すればサーボを回転させるというプログラムを適当に書きます.

www.instagram.com

これをドア鍵に設置することで学生証をかざすことでサーボでサムターン*8を回転させ,開閉することが可能です.さらには,10秒後には鍵が閉まるオートロック機能も付与しています.f:id:lapis_zero09:20161222214921j:plain

不要時には電圧がかからないので,本来の鍵を鍵穴に差し込み開錠・施錠も可能です.

www.instagram.com

懸念事項として,ドアからPaSoRi RC-S380が生えている御宅が少ないので住居を特定される可能性があります.

しかし,これはあまり問題にはなりません.

なぜなら,本来の目的は我が家の鍵を開閉することではなく,研究室の認証方式を変換することだからです.

数日後,B3の初ゼミが研究室で行われました.

f:id:lapis_zero09:20161222180422j:plainf:id:lapis_zero09:20161222180430j:plainf:id:lapis_zero09:20161222180441j:plain

明日はhimktさんです.期待しましょう.

参考

*1:"Sony Japan | FeliCa | 法人のお客様 | ダウンロード"."Sony Japan". http://www.sony.co.jp/Products/felica/business/tech-support/index.html

*2:"Sony Japan | FeliCa | FeliCaとは | FeliCaって何?"."Sony Japan".https://www.sony.co.jp/Products/felica/about/index.html

*3:"Sony Japan | FeliCa | NFCについて | NFCの定義"."Sony Japan".https://www.sony.co.jp/Products/felica/NFC/index.html

*4:"Python module for near field communication — nfcpy latest documentation".nfcpy.http://nfcpy.readthedocs.io

*5:"一般社団法人 FCF推進フォーラム".http://fcf.jp/index.html

*6:澤村 博道."情報科学類・CS専攻入退室管理システム".http://www.tech.tsukuba.ac.jp/2010/report/n14_report2010.pdf

*7:"FCFキャンパスカードとは"."一般社団法人 FCF推進フォーラム".http://fcf.jp/fcf12461125151253112497124731245912540124891239212399.html

*8:"図解 - 鍵の各部名称|鍵と防犯の用語集|住まいの防犯特集"."美和ロック株式会社".http://www.miwa-lock.co.jp/lock_day/glossary/lock/12.html