2015-01-24

今回の TokyoWebmining はここ最近、特に注目を集めている Deep Learning と word2vec がトピックということで、参加者募集も数分で枠が埋まってしまうほどの大人気っぷりでした。

せっかくなので、（参加したくても参加できなかった方々も多いことかと思いますし）たまにはまとめエントリを、会場内での質問やディスカッションを中心に書いてみようかと思います。

(聞き間違い・勘違いなどがあるかと思いますので、気づかれたかたはツッコミ願います)

深層学習時代の自然言語処理 by @unnonouno さん

Recurrent Neural Network

  • p.11 Recurrent Neural Network
    • 1 個の単語に対して、1 個の dense ベクトルがある
      • 次元数は 100〜1,000 ぐらい
      • RNN への入力ベクトルはこれになる
      • この単語ベクトルは各層で共有される
      • 正則化して sparse にしてみたけど、別によくはならなかった
  • p.14
    • 時間方向に層を重ねることに相当する
      • 層が文長に相当する、ここが他の NN と異なる
  • p.16
    • RNN の学習は、Back Propagation (Through Time) で学習する
      • 時間をさかのぼって学習しているように見える
      • 図的には、赤が Back propagation になる
  • p.17
    • 誤差が最初の方に伝搬しないという問題がある
    • これを解決したのが Long Short-Term Memory という技術
  • p.18 Long Short-Term Memory
    • 隠れ層のベクトル間でされる演算
    • 影響の与えるタイミングと与えないタイミングがあるはず、という考え
    • これによりパラメータが増えることになるが、これは学習対象となっている
    • 昨年後半からこれが流行ってる
    • 機械翻訳や Wikipedia 文章ぽいものの再生成、構文解析などに適用されてる by Google
    • 1 個の文がベクトルになって、そこから文が湧き出てくる

Recursive Neural Network

「両方とも RNN って略すのやめろ」

  • p.22
    • こちらは木構造を学習してつくる
    • 文章の構文解析だけでなく、画像の構造推定に使える
      • 木構造を作る
      • 二つの要素をくっつける順番を学習する
  • p.23 評判分析にも使われてる
    • こちらは木構造が事前に与えらて、ポジネガを判定している
    • 前は feature engineering で頑張って精度を高めていたけど、この RNN を使ったら良くなった
    • 文章全体ではなく、一つの文に対して適用される

本題：構文解析

  • p.32 Shift-Reduce 法
    • ガーデンパス文に弱い
    • これが Recurrent Neural Network に近いんじゃないか？
  • p.41
    • 品詞情報だけだと、構文解析は全然できない
  • p.46
    • 構文解析はまだルール作りはなんとかなるが、意味解析は膨大過ぎてルール作りは辛い

まとめ

  • p.48
    • Recurrent が流行っている
    • 音声認識、特に G とか MS とかの大手では DNN が使われているんじゃなかろうか？

ディスカッション

  • 単語分割、構文解析は精度が出ているが、意味解析とか談話解析はまだまだなので、そのあたりで DNN 使って精度出せるといいね
    • そもそもの問題設定があいまいだったりするけど…
  • テトリスブロックを回転させたもの同士が同じかどうかを判定するタスクで、DNN はうまくいかないというツッコミを入れた論文があった
  • 「言語学者をクビにすればするほど精度が上がる」

ディープラーニング徹底活用 画像認識編 by @atelierhide さん

この発表で一番言いたいこと

  • 「学習済みモデルを徹底活用しよう！」
    • Convolutional Neural Networks (CNNs) のモデル
  • 世界一のモデルを使うことができる
  • 1000 次元のベクトルが出力として得られる

Deep learning frameworks

  • 選択観点
    • 学習済みモデルが提供されているフレームワークを選ぶのがいい
    • Caffe よさそう
    • Caffe と DeCAF はほとんど違いはない
    • OverFeat は使い勝手がよくない
  • Caffe
    • 画像のリサイズなどは、まあまあフレームワークがよろしくやってくれる
      • 横長画像は正方形に変換されてしまうので、その点は注意しないといけない
    • Detection と Recognition は別
      • DNN が効くのは Recognition のほう
    • モデルの学習をする場合は、背景などが写り込んでいないものを選ぶべき
      • 分類はその限りではない

学習済みモデルの活用のアイデア

  1. 特徴抽出器として使う
    • CNNs の最後から 2 番目に得られる部分のベクトルを使う
      • pre-training 相当になっている
    • これを特徴量として、SVM などで分類する
  2. ファインチューニングをする
    • 出力層・分類数を入力画像にあわせて変更し、学習済みモデルのパラメータを最適化する
  3. 物体検出に使う

ディスカッション

  • みんなが Caffe を使い出していて、いろんな適用例が発表されはじめている
  • Caffe に Recurrent / LSTM が入るらしいということで、その手の界隈がざわついている

word2vec のご紹介 by @piroyoung さん

word2vec

Python で word2vec を使う

  • p.36
    • gensim を利用する
      • Paragraph vector も実装されている
    • コーパスをライブラリに喰わせるときに工夫が必要になる
      • ナイーブにやるとメモリが足りなくなる
      • 1 行読んでスペース区切り文を分割する… の処理をイテレーションさせる

素性のクラスタリング

  • word2vec で得られた単語のベクトルをクラスタリング
    • わりとよくクラスタリングできてる

QPR の学習

  • QPR = Quick purchase report, 消費者購買動向データ
  • p.56
    • ウィンドウサイズはものすごく大きなサイズにした
      • バスケット内の商品は、順番には意味がない
      • ただし先ほどの海野さんのツッコミにあるとおり、順番が考慮された結果となってしまった

ディスカッション

  • 文章中の助詞などを省いてみたら結果はどうなるの？
    • 単語同士の関係性を構成する要素になるので、動詞を入れても動詞が出てこなくなる
    • ものにもよるが、助詞を入れた方がいいであろう
  • 次元数 200 以外でやってみた？
    • 次元を上げて、悪くなることはなかった
    • 計算時間はその分かかる

今回の TokyoWebmining の所感

  • Deep learning、いまいちちゃんと理解できてなかったけど、雰囲気はだいぶつかめてきた
  • 画像の取り扱いにおいては Deep learning を利用するのがもはや当たり前っぽい
    • ImageNet の学習済みモデル、応用の幅が広いね！
  • 自然言語処理での Deep learning 活用、研究の進展が速いので、常にキャッチアップしていかないと置いて行かれそう…
  • とにかく Deep learning 熱の高まりっぷりがはんぱない！

2015-01-19

前回 は CTR (クリック率)、CVR (コンバージョン率) に対するいくつかの区間推定方法を、それぞれの特徴とともに列挙してみました。今回はそれらの区間推定方法による実際の信頼区間を、Java や Python, R を用いて求める方法をまとめてみます。

Java による区間推定

Java で二項比率の区間推定をするには、commons-math3 の org.apache.commons.math3.stat.interval パッケージ以下のクラスを使うのが手っ取り早いでしょう。

それぞれの区間推定方法に対応するクラスは以下のとおりです。

  • Wald confidence interval
    • NormalApproximationInterval クラス
  • Clopper-Pearson (or 'Exact') confidence interval
    • ClopperPearsonInterval クラス
  • Wilson (or 'Score') confidence interval
    • WilsonScoreInterval クラス
  • Adjusted Wald confidence interval / Agresti-Coull confidence interval
    • AgrestiCoullInterval クラス

これらのクラスに定義されている #createInterval(int numberOfTrials, int numberOfSuccesses, double confidenceLevel) を呼び出すことで信頼区間を求めることができます。たとえば numberOfTrials にインプレッション数を、 numberOfSuccesses にクリック数を、 confidenceLevel に 0.95 を設定して呼び出せば、95% 信頼水準での CTR の信頼区間が得られます。

サンプルコードは以下のとおり。

注意点として、 CTR や CVR の割合が 0% or 100% になるケース (つまりは、クリックやコンバージョンがまったく発生していない or 毎回発生している状態) において NormalApproximationInterval クラス、もしくは ClopperPearsonInterval クラスの #createInterval(int, int, double) メソッドで信頼区間を求めようとすると、 MathIllegalArgumentException や NotStrictlyPositiveException などの例外が発生してしまいます。

Wald confidence interval ではそもそも区間の幅が 0 になるケースに相当するのでどうしようもないのですが、Clopper-Pearson confidence interval では区間の片側だけでも算出することはできるはずです。

なので、このようなケースでも無理矢理に算出することはできるわけで、例えば ClopperPearsonInterval クラスの実装を以下のように修正すれば例外を生じることなく信頼区間を求めることができます。

Python による区間推定

Python の場合は、statsmodels を使います。

使い方は こちらのドキュメント を参考に、statsmodels.stats.proportion.proportion_confint(count, nobs, alpha, method) を呼び出します。CTR を算出するのであれば count にクリック数を、nobs にインプレッション数を指定し、加えて信頼水準 $100(1-\alpha)\%$ の $\alpha$ を alpha に指定します。

method には、区間推定方法を文字列で指定します。

  • Wald confidence interval
    • normal
  • Clopper-Pearson (or 'Exact') confidence interval
    • beta
  • Wilson (or 'Score') confidence interval
    • wilson
  • Adjusted Wald confidence interval / Agresti-Coull confidence interval
    • agresti_coull

サンプルコードは以下のとおり。

Java 同様に注意すべきこととして、CTR や CVR の割合が 0% or 100% の場合に、Clopper-Pearson confidence interval による区間推定の結果のうち、一方の片側が NaN になってしまうことが挙げられます。この場合、下側のエンドポイントが NaN であれば 0% と、上側のエンドポイントが NaN であれば 100% と読み替えればよいかと思います。

R による区間推定

R では、binom パッケージ の binom.confintt(x, n, conf.level, methods, ...) を使って二項比率の区間推定をします。

methods に "all" を指定すると、すべての区間推定方法の結果を一覧で出力してくれます。もしくは以下の文字列を指定することで、対応する区間推定方法での結果を出力してくれます。

  • Wald confidence interval
    • prop.test
  • Clopper-Pearson (or 'Exact') confidence interval
    • exact
  • Wilson (or 'Score') confidence interval
    • wilson
  • Adjusted Wald confidence interval / Agresti-Coull confidence interval
    • agresti-coull

まとめ

今回挙げた言語の各ライブラリでは、いずれもメソッド・関数を呼び出す程度の簡単なコードで二項比率の区間推定をすることができました。

ただ Java と Python については、CTR / CVR が 0% or 100% といったコーナーケースにおいてあまり好ましくない振る舞いをするため、多少の注意が必要となります。

また、各ライブラリで区間推定方法の呼称が異なることがあるため (Python / statsmodels の beta (Clopper-Pearson) や、R / binom の prop.test (Wald) など)、この点にも注意すべきかと思われます。

(次回こそはシミュレーション結果を…)

2015-01-07

わけあってクリック率・コンバージョン率の信頼区間を算出したくなったのだけど、そのやり方を調べてみたら結構ややこしかったので、調べた結果をメモに残しておきます。

はじめに

クリック率 (Click-through rate, CTR) やらコンバージョン率 (Conversion rate, CVR) を扱う仕事をしていると、少なくとも一度ぐらいはそれらの信頼区間を求めて (区間推定して) みたくなるものかと思います。

それというのも、例えば「100 回のインプレッションのうち、1 回のクリックが得られた」という標本 (サンプル) があったとして、これから CTR を点推定すると 1% になるものの、これは「サンプルサイズを増やしたときにも同様に 1% になるのか？」と言ったらそんなことは言えないわけで、ならば「どれくらいの信頼水準のときにどれくらいの範囲に真の CTR が存在しうるのか？」ということを知りたくなるわけです。この範囲を求めることがすなわち信頼区間を求める・区間推定をすることに相当します。

さて以上のようにクリック率・コンバージョン率の区間推定をしてみたいのですが、具体的にはどのようにすればいいのか？ これは二項比率 (binomial proportion, この日本語訳で適切なのか、わからない…) の区間推定をすることに等しくなります。

二項比率の区間推定をする方法について、あいにく日本語で網羅的にまとまった解説が Web 上には存在しないのですが (だからこのブログエントリを書いているわけでして…) 英語 Wikipedia のページ がそこそこ充実しているので、わかる人はこちらのページを合わせて参照することをおすすめします。以降はこの Wikipedia ページと、同ページでリファレンスされているいくつかの論文 (後述) をもとに話を進めます。

二項比率の区間推定をするいくつかの方法

さて二項比率の区間推定をする方法として、今回は以下の 4 つを取り上げてみます (他にもベイズ的な確信区間などがあるわけですが、こちらは僕自身まだちゃんと理解しきれていないので割愛します)。

  • Wald confidence interval
  • Clopper-Pearson (or 'Exact') confidence interval
  • Wilson (or 'Score') confidence interval
  • Adjusted Wald confidence interval / Agresti-Coull confidence interval

以下、それぞれの区間推定方法について、数式とともにその特徴などを列挙していきます。

Wald confidence interval

$$\hat{p} \pm z_{\alpha/2} \sqrt{ \hat{p} (1 - \hat{p}) / n}$$

($\alpha$ は信頼係数、$z_{\alpha/2}$ は標準正規分布の上側 $100(\alpha/2)$ % 点、$n$ はサンプルサイズ or 試行回数、$\hat{p}$ は二項比率の推定値)

二項分布 $B(n,p)$ は正規分布 $N(np, np(1-p))$ で近似できることから、二項比率の信頼区間も正規分布 $N(p,p(1-p)/n)$ で近似することができるため、上記の式で信頼区間を求めることができます。

  • 数式がわりと容易である
    • つまりは実装するのも比較的楽、ということ
  • この手法により求まる信頼区間は、信頼水準から得られるそれよりも狭くなる (= 実際のカバレッジが低くなる) 傾向にある
    • サンプルサイズが小さい ($n < 100$ ぐらいの) 場合に、特にその傾向が表れる
    • また、 $p$ が 0.5 から 0 もしくは 1 に偏っているほどに顕著になる
  • 下側信頼限界が負数に、もしくは上側信頼限界が 1 を超える場合がある
    • それぞれ、 $p$ が 0 に近い場合、1 に近い場合にそのような状況になる
  • 成功回数 $x$ が、$x=0$ や $x=n$ の場合は、信頼区間を求めることができない (幅が 0 の区間になる)
    • クリック数が 0、もしくはインプレッション数に等しい場合が該当する

Clopper-Pearson (or 'Exact') confidence interval

$$\left[1 + \frac{n-x+1}{x F_{2x,2(n-x+1),1-\alpha/2}} \right]^{-1} < p < \left[1 + \frac{n-x}{(x+1)F_{2(x+1),2(n-x),\alpha/2}} \right]^{-1}$$

($F_{n,m,z_{\alpha/2}}$ は、自由度 $n,m$ の F 分布における右側 $100\alpha$ 点)

Wald confidence interval は正規分布で近似することで信頼区間を求めていましたが、サンプルサイズが小さい場合や $p$ が 0 もしくは 1 に偏っている場合は正規分布での近似が難しくなります。その代わりに、F 分布を用いることで正確な (?) 信頼区間を求めることができるそうです。

  • サンプルサイズが小さくても、求まる信頼区間は Wald confidence interval のように狭くはなく、比較してカバレッジがよい
    • むしろ逆に、ちょっと広すぎる…

Wilson (or 'Score') confidence interval

$$\left( \hat{p} + \frac{z_{\alpha/2}^{2}}{2n} \pm z_{\alpha/2} \sqrt{[\hat{p}(1 - \hat{p}) + z_{\alpha/2}^{2} / 4n] / n} \right) / (1+z_{\alpha/2}^{2}/n)$$

Wald confidence interval も Clopper-Pearson confidence interval も、それぞれ信頼区間の幅については狭かったり広かったりしてちょっと扱いづらいわけですが、Wilson confidence interval ではその点においてバランスがとれた幅の信頼区間が求まるようです。

  • 数式が複雑である
    • 実装する際にエンバグしやすい ※参考
  • 得られる信頼区間は狭すぎず、広すぎず
  • サンプルサイズによらず、$p$ が 0 もしくは 1 に偏っている場合に信頼区間が狭くなる傾向がある

Adjusted Wald confidence interval / Agresti-Coull confidence interval

$$\tilde{p} \pm z_{a/2} \sqrt{ \tilde{p} (1 - \tilde{p}) / \tilde{n}}$$

$$(\tilde{n} = n + z_{\alpha/2}^{2},\ \tilde{p} = \frac{1}{\tilde{n}} \left(x + \frac{z_{\alpha/2}^{p2}}{2} \right) )$$

Wald confidence interval はサンプルサイズが小さい場合に信頼区間の幅が狭く、結果としてカバレッジが低下する問題がありました。一方でこの Adjusted Wald confidence interval では、信頼係数 $\alpha$ から定まる $z_{\alpha/2}$ を用いて $n,x$ を調整し、 $\tilde{n}, \tilde{p}$ を算出しています。そして、この $\tilde{n}, \tilde{p}$ を用いて、Wald confidence interval の式を使い、信頼区間の近似値を算出しています。

特に $\alpha$ が 0.05 の場合は adding two "successes" and two "failures" と言っているとおり、$n$ に $2 + 2 = 4$ を加え、$x$ に $2$ を加える操作をすればだいたいいい感じになってくれます。

  • 数式はまだ容易な方ではある
  • サンプルサイズが小さい場合であっても、信頼区間が狭くなるようなことはない
    • Wilson confidence interval 同様にバランスのとれた幅の信頼区間が求まる
  • 下側信頼限界が負数に、もしくは上側信頼限界が 1 を超えうる問題は健在している

クリック率・コンバージョン率の特性

ここまで区間推定方法について見てきましたが、これらを適用する先のクリック率やコンバージョン率の特性についても見ておきましょう。

  • クリック率
    • サンプルサイズ (インプレッション数) は十分な大きさとなる
      • コンテキストを考慮した CTR を算出する場合はその限りではない
    • 値は常に小さな値になりがちで、0 に近くなる
      • 1% に満たないことも十分にあり得る
  • コンバージョン率
    • サンプルサイズ (クリック数) が小さいことがある
    • 値はまちまちで、一桁 % のときもあれば二桁 % になることもある
  • 共通して言えること
    • 0% となるケースを考慮するべき

現時点での推測

長々と書いてきましたが、上記をふまえると、クリック率やコンバージョン率の区間推定には Agresti & Coull の Adjusted Wald confidence interval を利用するのがよいのではないか、と考えられます。

ただ厳密には、クリック率・コンバージョン率の特性を想定したテストケースをいくつか用意して、実際のカバレッジを測定するシミュレーションをしてみないことには胸を張って「○○ がいい！」とは言えないかな… と思います (シミュレーションは次回のブログエントリに書く予定)。

参考文献

本ブログエントリは、主に以下 2 つの論文で述べられている内容をまとめたものとなっています。より詳しく知りたい方はこれらの論文を読まれることをおすすめします。

登録: 投稿 (Atom)