froglog

プログラミングや統計の話など

機械学習を利用するプロダクトのテスト

このエントリについて

ポエムです。

11/8(火) に開催された Cloudera World Tokyo 2016 に参加しました。

その中で上記の2つの発表がとてもいい話でした。 多少絡みのある内容として機械学習を利用するプロダクトのテストについて述べたいとちょっと前から考えていたので、いい機会なので書いてみます。

おそらくできてる組織は当たり前のようにできているでしょうし、できてない組織は当たり前のようにできていない話です。

2種類の要件

通常テストはプロダクトの仕様や要件にもとづいて用意されますが、システムの要件には機能要件・非機能要件の2種類があります。

ここでは機能要件と、非機能要件の中でも性能要件にフォーカスします。 機械学習を利用するプロダクトにおいては、例えば

  • 参考にした論文に記載の式のとおりにパラメータを更新しているか → 機能要件
  • 予測・分類等で期待される精度が出ているか → 性能要件

などと考えることができます(もちろんこれだけではありませんが)。 個人的にはどちらの要件のテストも必要だと考えています。

ところがこれまで私が見てきた中ではこれらのどちらか(または両方)ができていないチームもありました。 機械学習アルゴリズムの実装は組織によって、エンジニア的な人がやる場合と研究職(or アナリスト)的な人がやる場合とがあると思います。 私の経験からすると、機械学習アルゴリズムの実装を担当するのが前者の場合は性能要件のテストが、後者の場合は機能要件のテストが抜け落ちてしまうことがあるようです。

性能要件のテスト

普段エンジニアが性能要件を考慮していないかというとそんなことはなくて、システムのスループットレイテンシー等は常に見ていると思われます。 ですが機械学習のプロジェクトの経験があまりないような場合は「予測や分類等のタスクをどの程度の精度でこなせるか」という検証が盲点になることがあります。 最初に計画していた実装でアプリケーションに求められる精度を達成できるかは分からない場合が多いのではないでしょうか。

offline と online

性能のテストには offlineと online があります。 offline とは本番運用に影響を与えないという意味です。 過去のログデータ等を用いて手元で精度を検証し、より良いアルゴリズムの選定やパラメータの調整を行います。

一方で online の性能テストは本番環境に乗った形で行います。 例えば web サービスなら A/B テストで実際のユーザの行動によってアルゴリズムやパラメータの良し悪しを比較します。

二者を比較すると、

  • offline 性能テスト
    • 本番運用、つまり売上等への直接的な影響がない
    • 比較的高速にテストできる(過去ログを使うため実時間でログがたまるのを待つ必要がない)
    • 同じログデータを使うことで再現性のあるテストが可能
  • online 性能テスト
    • 実際の本番運用の条件でテストできる

という特徴があります。

以上から、たくさんのアルゴリズムやパラメータそれぞれについて性能テストを実施し、性能が高い組み合わせにあたりをつけるのは offline の性能テストが向いていると言えます。 なおかつ offline では本番環境と条件が異なる場合もよくあるので最終的に online 性能テストで可否を確認するというのが堅実な流れです。 発表 1 でもこの流れが説明されていますね。

offline 性能テストの自動化

頻繁に offline 性能テストを回したい部分についてはテストの自動化をしたいところです。 xUnit のような各言語のテストフレームワークに offline の性能テストを無理矢理のせることもできますが、おすすめしません。 性能のテストには大量のデータが必要となるため、それなりの時間がかかります。 つまりスローテストになるので CI に組み込むのはつらい感じです。

自動化する場合は CI で実施するテストとは別物と割り切って、前処理・特徴抽出・学習・評価を行うワークフロー的な仕組みを導入するのがよいでしょう。 shell 等で自作してもいいのですが、Spark の ML PipelinesSpotify が開発した Luigi 等のワークフローをサポートするフレームワークを使うと楽かもしれません。

重要なのは例えば1ヶ月後にチームの別のメンバーが同じ条件のテストを再現できるか(できればなるべく簡単に)です。 必要ならドキュメントも残しておきたいです。

A/B テストはすぐにほしい

機械学習を導入したいのであれば、まずABテストから

上記は発表 2 でからの引用です。 私もこれに激しく同意です。 *1

「まずは機械学習的なものを導入しましょう、A/B テストは必要になってから開発しましょう」みたいなケースを何度か見たことがありますが、これは以下の2点から好ましくありません。

  • 既存システムに機械学習を追加する場合、機械学習があったときとなかったときの比較ができない
    • ex. EC サイトに商品レコメンデーションを追加したけどその効果が測れない
  • A/B テストを後から導入するのは結構たいへん
    • 経験上、最初は「性能はとりあえず問わない」みたいな話で開発が始まっても結局後で性能が問題になるのはあるあるで、どうせ A/B テストが必要になる *2

プレスリリース芸や営業資料等のビジネス上の観点から少ない開発リソースで A/B テストなしで機械学習を実装せざるを得ないケースもあるかもしれませんが、設計時になるべく後から A/B テストを入れられるようにしておきたいところです。

機能要件のテスト

さて、次は機能テストの必要性について話していきます。

ここで言う機能テストはいわゆる CI に組み込まれて自動で実行される、機能が要件・仕様どおりの挙動を示すかをチェックするテストです。 性能テストのように数値の尺度があるのではなく、「◯◯ができる/できない」でチェックできる項目がテスト対象です。 機械学習アルゴリズムにおいては、例えば元となっている論文の式がそのとおりに実装されているか、入力データのある次元の分散が 0 でもおかしな挙動にならないか、などといったことをチェックするテストが挙げられます。

通常こういったテストは各言語のテストフレームワークを使って作られます。 Python なら unittestnose, C++ なら googletestCppUnit, Scala なら Specs2ScalaTest など各言語でいろいろありますが、それぞれのフレームワークで考え方は似ているので慣れれば難しくありません。

性能テストのみで十分なのでは?

「性能テストでそれっぽい精度が出てれば問題ないのでは」という意見を実際に聞いたことがあります。 そうとも言えそうだし結局性能テストもやらないといけないわけなのですが、これには反論があります。

まず「期待する性能を確認できること」と「アルゴリズムを想定通りに実装できていること」はイコールではありません。 アルゴリズムの実装の一部に問題があってもそこそこの性能が出ることはあります。 しかしその後パラメータチューニング等をするときに理論どおりの挙動にならず「???」となった上で実装の問題を発見して、性能テストをやり直し…ということもあるでしょう。

また、プログラムを修正したけど性能には大きな影響はないはず、という場合もあります。 このような場合に動作確認のためにわざわざ性能テストをしないといけないのもコストが高いです。 もちろん修正に悪影響がないか確認しないというのもよろしくありません。 機能テストを自動化していれば影響をすぐに確認できます。

テストデータ生成

通常の xUnit のテストでは「この関数にこのデータを入れるとこの値が返ってくる」というようなチェックの仕方をすることが多いですが、返ってくる値の正解を用意してやる必要があります。 例えば勾配の更新式等、数式レベルの機能であれば Excel 等(できれば非プログラム的な方法)で簡単に計算した値を正解データとして使うといいかと思います。 これは答えが明確で用意しやすいです。(とはいえ面倒臭い)

難しいのは予測や分類などの大きめのレベルの機能の正解データをどう用意するかですが、私は例えば分類なら少量の入力データかつごく簡単な分類タスクを用意してやり、「これならいくらなんでも分類できるでしょ」というのを正解にします。 本当に最低限の性能は保証されている前提でテストデータを作るわけです。 *3

開発リソースに余裕があるのであれば、実装する人とテストデータを作る人を別にすると安全かつ仕様の共有が捗ります。

機能テストをいつ作るか

自動化された機能テストを用意するタイミングとしては

  1. offline 性能テストにかける段階
  2. online 性能テストにかける段階
  3. baseline として適用される段階(online 性能テストで勝利した後)

のどれかになるかと思いますが、チームとしてのルールの中で決められていればいいと思います。

個人的には 1. の時点ではアルゴリズムの肝となる数式の部分や問題が起こりそうなところ、2. の時点では今のデータで本番サーバでの運用に耐えられるレベル、3. の時点ではテストするのが面倒臭いけど潰しておきたいところ、と段階的にテストを充実させていくのがいいんじゃないかなと思います。

まとめ

このエントリで言いたかったのは性能も機能もどちらもテストしましょうということです。

これを実現するのに難しいところがあるとするなら、それはデータ分析を担当するチームの構成ではないでしょうか。 発表 1 & 2 でも述べられていますが、データ分析のチームにはいろいろなスキルを持った人が必要です。 言い換えると異なった文化的背景を持った人たちが集まった low context なチームというわけです。 そういった状況でゴールに向かうにはチーム内をルールなりでまとめることが必要で、そのルールを適切に運用できるリーダー的な人の存在が重要なのだと思います。

最後になってしまいましたが、何のためにテストをやるかと言うと平たく言ってしまえば安心するため、不安を軽減するためだというのが個人的な認識です。 機能的な不安も性能的な不安も減らしていきたい所存です。

*1:もちろん A/B テスト可能なアプリケーションであればの話です。

*2:最悪 A/B テスト等の評価手段がない状態で「性能を上げろ」という話になりますが、個人的にこれを「屏風の虎」問題と呼んでいます。虎(性能)を退治するためにはまず屏風(評価不能な状況)から出さないといけません。

*3:性能のテストと機能のテストは完全に分離することはできません。

線形分類器のオンライン学習を実装してみた

このエントリについて

最近読んだオンライン学習の本が分かりやすくて面白かったので、紹介されているアルゴリズムを実装して遊んでみました。

書籍紹介

オンライン機械学習 (機械学習プロフェッショナルシリーズ)

オンライン機械学習 (機械学習プロフェッショナルシリーズ)

タイトルのとおりオンライン学習について書かれた書籍です。 かなり分かりやすく書かれていて、数学*1が苦手な私でも比較的楽に読むことができました。 機械学習の入門書としても良いかもしれません。 主に2値分類の線形分類器について書かれていますが、SVM や深層学習の話も出てきます。

このエントリでは本書のセクション "4.1 高度なオンライン学習" で紹介されている線形分類器のオンライン学習アルゴリズムを実装して動かしてみます。

ソースコードはこちら、Scala です。

アルゴリズム

セクション "4.1 高度なオンライン学習" では以下のオンライン学習アルゴリズムが紹介されています。

  • Perceptron*2
  • PA (Passive-Aggressive)*3
  • PA-I
  • PA-II
  • CW (Confidence Weighted Learning)*4
  • AROW (Adaptive Regularization of Weight Vectors)*5
  • SCW-I (Soft Confidence-Weighted Learning)*6
  • SCW-II

上から古い順になっており、新しいものほど性能が良いとされているとのこと。

これらのアルゴリズムの学習はすべて以下の形のアルゴリズムで表すことができます。

A base class of online learning for binary linear ...

学習はメソッド train() で行います。 w は学習しようとしている線形分類器の重みベクトル、またはそれを生成する正規分布の平均ベクトルで、sigma はその共分散行列です。 これらを更新していくのがこのオンライン学習の目的です。 *7

アルゴリズムごとに異なるのはパラメータ更新の条件判定に用いる e 、および wsigma の更新に使われる alphabeta になります。 各アルゴリズムの具体的な説明は省きますが、こちらにそれぞれの実装があるのでご興味のある方はどうぞ。

実験

実際にデータを突っ込んで性能を見てみます。

データ

Breast Cancer Wisconsin (Diagnostic) Data Set を使いました。 30次元で数値化された乳房の組織の画像の特徴およびその組織が良性か悪性かというラベルを含むデータです。 実験はこの良性/悪性の2値分類をするタスクとなります。

手順

こんな感じ

  • 以下繰り返し
    1. サンプルを1個読む
    2. 更新前の線形分類器で分類して結果を記録
    3. そのサンプルと正解ラベルを使って分類器を学習・更新

学習サンプル数に対するエラーの数をカウントして、それをアルゴリズム間で比較します。

ハイパーパラメータは全データを使って軽く手でチューニングしています。 (本当はデータ分けてチューニングした方がいいんだけど) なのでアルゴリズムごとにこのデータで出せるベストの性能を目指している形になります。

実験結果

f:id:soonraah:20160606050927p:plain

AROW が一番良いという結果になりました。 SCW が AROW に負けるのはデータのせいなのか、チューニングが足りないのか、実装に問題があるのか… SCW はハイパーパラメータが2つあることに加え、ハイパーパラメータに対するエラー数の動きが予測しにくく、チューニングが難しそうでした。

共分散行列を使わない*8 Perceptron と PA 系はやはり他と比べてかなり性能が落ちます。 直前に学習したサンプルに振り回されてる感がありました。

まとめ

以上の結果から実際に業務等で使うとしたら AROW が使い勝手良さそうです。 実装もすごくシンプル。 SCW もポテンシャルはあるはずなんですが…

今回オンライン学習を初めて実装してみましたが、関数型プログラミングと相性が良いと感じました。 実際 var メンバーを使わずに実装することができました。 並列化とか考えだすと難しくなりそうな気はしますけどね。

ここで挙げたアルゴリズムの元論文の導出とか見ると数式だらけでウゲーってなりますが、実装は比較的シンプルになります。 オンライン学習ってそういうもんなんですかね。

レコメンデーションシステムのオフライン評価、どうやるんですか

カエルなので分かりません、誰か教えてください。

レコメンデーションシステムのオフライン評価について調べてました。 そのメモ的なエントリです。

ここでいうレコメンデーションシステムについてはよくある EC サイトの商品推薦のようなものをイメージしていただければと。 また、オフライン評価とは "一般的な A/B テストのように実運用に影響のある方法" ではなく、過去ログ等を用いてローカル環境でバッチ的に行える評価のことです。

尺度

尺度については以下によくまとまってます。

ここに挙げられている中で個人的に有用そうだと思ったものを列挙。

順序を考慮した精度的な尺度

  • MAP (mean average precision)
  • nDCG (normalized discounted cumulative gain)
  • nDPM (normalized distance performance measure)
  • AUC (Area Under the ROC Curve)

レコメンデーションシステムは複数のアイテムによるリストをユーザに提示することが多いかと思います。 なので単なる再現率や適合率だけでなく、アイテムが表示される順序も考慮されてる方が直感に合います。 これらの尺度ではユーザの嗜好が強いアイテムが上位に来た方が良いとされます。*1

どのくらいのユーザに出るかの尺度

  • user coverage (fraction of users who get recommendations)

どんなに高精度なロジックでも1%のユーザにしか出せないのであれば残念なものになります。 一方でアイテム被覆率は私としてはそんなに重要だとは思ってません。*2 アイテム被覆率見るなら、出方の偏りを見るためのジニ係数的なものまで見るべきでは。

その他尺度について思うところ

  • serendipity は大事なのはわかるけど計測できるのだろうか…
  • diversity はアイテム間の類似度があれば定義できる*3

オフライン評価のバイアス問題

バイアスについて

そういった尺度を使ってオフライン評価したいわけなんですが、私の頭でぱっと考えると以下のような流れになります。

  1. 実運用でログデータを集める
    • どのユーザに
    • どのアイテムが表示され
    • どのアイテムにアクション(クリック、購買等)があったか
  2. 学習データと評価データに分ける
  3. 評価対象のロジックで学習データを学習し、ログに含まれるユーザへの推薦リストを生成
  4. 推薦リストに含まれるアイテムと評価データ中でアクションのあったアイテムを比較し、何らかの尺度を計算

ただしこれだと実運用時にユーザが何を見せられているかによるバイアスがかかってしまいます。 例えばユーザが推薦ロジック X を見てアクションしたことにより得られたログであった場合、アクションのあったアイテム、つまり推薦で当てたいアイテムは当然 X の出力に含まれるアイテムとなり、おそらく X に近いロジックが良いロジックであると評価されやすくなります。

また、過去のログを学習するようなアルゴリズムであればたまっているログの状態が推薦結果に影響し、推薦結果がその後のログの状態に影響するのでバイアスが避けられない。 ログと見せ方(アルゴリズム)は表裏一体ってことですかね。

offline replay

このあたり扱っている論文はいくつかあるみたいですが、bandit algorithm 系でよく見るのがこちらの offline replay という方法。

    1. Li, W. Chu, J. Langford, and X. Wang. Unbiased offline evaluation of contextual-banditbased news article recommendation algorithms. In Proceedings of the fourth ACM international conference on Web search and data mining, pages 297–306, 2011.

すごく乱暴に解説すると、まず一様乱数でアイテム選択するというロジックで実運用ログデータを作ります。 オフラインでログデータに含まれるユーザに対して評価対象ロジックでアイテムを提示し、アイテムが一様乱数から表示されたものと一致しなければ無視、一致したらそのデータだけを用い尺度を得るという方法です。 もともとは bandit algorithm のために考えられたものですが、レコメンデーションにも応用可能です。

が、bandit でいうところの腕の数が多いと精度が下がるため、腕の数にあたるものはレコメンデーションではアイテム数ということになって商品数の多い EC サイトとかだときびしそう。 というのと一様乱数でログを作らないといけないのもネック。

最近の研究

最近の研究ではどうなってるのかと RecSys 2015 の発表で web で PDF で読めるものの評価実験のところを2, 3読んでみましたが、バイアスはあまり気にしてないような実験になってました。 気にしなくていいのか…

とりあえずのまとめ

ここまでで、データがあるのであればオンラインの A/B テスト CTR やら CVR やら見るのがいいのではって気がやっぱりしてきます。

とはいえオフライン評価したいときもあります。 ハイパーパラメータの最適値をだーっと探したりしたいときもあるし、オンラインの評価しかできないのであれば評価対象のアルゴリズムをいきなりプロダクトコードで実装しないといけないかもしれませんし。*4

  • 基本的にオンライン A/B テストで評価する
  • パラメータ調整など比較対象が多いときはバイアス覚悟でオフライン評価をする

というのが現実的な落とし所なのではというのが今のところの結論ですね。 レコメンデーションシステムを扱ってる他の皆さんはどうやってるんだろうか。

*1:並び順でユーザの嗜好が強い順が良いとされる場合が多いが、当て馬を入れた方が良くなるという文脈効果、リストの先頭と末尾が大事だとする初頭性/近親性効果などもある

*2:でもクライアントは気にする

*3:Ziegler, C.N., McNee, S.M., Konstan, J.A., Lausen, G.: Improving recommendation lists through topic diversification. In: WWW 2005, pp. 22-32 (2005)

*4:レコメンデーションシステムの作り方にもよる

人材流動性を高めました

このエントリについて

いわゆる退職エントリです。 と言っても退職したのはおよそ1ヶ月前ですが。

退職の経緯

8月末で株式会社 ALBERT を退職しました。 2年と2ヶ月の在籍でした。

退職を決めた理由は、

  1. 新しい分野・環境に身を置きたくなったこと
  2. 上場して会社としてのステージが変わったこと

などです。*1

入社してからは主にレコメンデーションっぽいシステムの開発に携わることが多かったのですが、特に去年の秋から今年の春にかけてやっていたプロジェクトにおいてレコメンデーションまわりでやりたかったことを一通り実現できてしまいました。 推薦システムは奥深い分野であり極めたなどとはもちろん微塵も思っていませんが、そこに至って環境を変えた方が自分にとってのインプットが大きいのは間違いないだろうとの見込みがありました。 そしてちょうど2月に IPO があり、組織としてのステージも変わってきたのでいいタイミングかなと思いました。

学んだこと

いわゆるシステム開発

ALBERT 以前の仕事でも開発はしていましたが、社内向けツールであったり社外向けに作っているシステムで使うためのライブラリみたいな感じの開発が多く、いわゆる一般的なシステム開発というものを経験したことがありませんでした。 例えば web システムの全体に対してコミットできたわけではありませんが、「ネットでよく見る『システム開発』ってこんな感じか〜」というイメージを持つことができました。

新しいモノを使う

新しい開発ツールフレームワーク等をガンガン使っていくという文化があり、「VCS を普通に使えるのが自分を含めて2人しかいない」みたいな組織にいたこともある自分にとってはそれがとても新鮮でした。 実際自分がいた間だと、AWS サービス群、JetBrain 社の製品群、Ansible や Vagrant 等のプロビジョニング関係ツールApache Spark 等のフレームワーク等が導入されました。

一方で新しいものを導入するというのは組織運営の面で困難なところもあり、導入に全員がすぐ適応できるわけでもないですし、導入したものをどのように運用するかまで考える必要があります。 個人として新しいものを抵抗なく取り入れられるのは素晴らしいことですが、組織としては運用面でのバランスの問題があり、個人的な感覚としてはやや導入を急ぐ方に寄っているかなという思いがありました。 とはいえいろいろなものが使えたのでとても勉強になりました。

社外勉強会の文化

私が入社したときは社外の勉強会に参加したり発表したりしているエンジニアが結構多くいました。 中には勉強会の主催者メンバーになっている方もいらっしゃいました。 それまで身近に勉強会に参加している人がおらず、「勉強会に参加する」という考えがありませんでした。 誘われて何度か勉強会に参加してみて、また機会をいただいて自分でも発表したりして、この文化はとてもいいものだと感じました。 これについては後述します。

以上は私の在籍期間中の話であり、上述のとおり組織のステージも人も変わっているので現在の状況とは違っている可能性があることをご留意ください。

転職について

バズってから2〜3年

前回の転職ではエージェントを使い、今回の転職ではエージェントおよび知人のツテを使いました。 エージェントで面白かったのが、「ビッグデータの文脈で機械学習をやりたい」的な感じで前回の転職でも今回の転職でもエージェントには同じ希望を伝えているのですが、エージェント側の反応がまったく違っていたことです。 今回の方が断然反応が良く、次から次に案件を持ってきてくれました。

前回の転職のときがちょうど「ビッグデータ」がバズり始めたときだったんですが、転職市場的にはまだそういった人材の需要は少なかったのでしょう。 というのを考えると、何かのスキルがバズってから2〜3年して転職市場での需要が大きくなる、つまり少し先の未来で需要が増えるスキルを予想するのはそんなに難しくない、ということなのかもしれません。 知らんけど。

エンジニアにとっての「弱い紐帯

有名な話なのでご存知の方も多いと思いますが、「弱い紐帯の強み」("The strength of weak ties")という説があります。 アメリカの社会学者 Granovetter さんが提唱したもので、まあ内容についてはリンク先をご参照いただければと。 エンジニアにとっての弱い紐帯って何なのかというのを考えたときに、社外の勉強会でのつながりが正にそれにあたるのではと思い当たりました。

公開のエンジニア勉強会ではいろいろな組織から人が参加しており、当然密な人間関係ではありません。 なのでそこに集う人の情報の冗長性は低いです。 一方で、その会のテーマという共通の興味があるために近い文脈で話をすることもできますし、発表などすれば自分がどういう人間かというのをちょっぴり知ってもらうこともできます。

私は決してコミュ力が高い方ではなく、というか低いのですが、それでも勉強会に参加したり発表したりして参加者とお話させていただいたりしました。 転職活動中にはその御縁で何名かの方から会社を見に来てみないか、とお声がけいただきました。 面談だけで終わってしまったり自分の力不足だったり私の方からお断りを入れたりで多くの場合はご期待には添えませんでしたが、お声がけいただいた方々には本当に感謝しております。 本当にありがたい話です。

エンジニア勉強会のような組織を超えたゆるい興味のつながりは、私のような強いコネもない・スタープレーヤーでもない人間にとって、弱い紐帯セーフティーネットとして意味があるものだというのが今回の転職での気づきでした。 (このエントリで一番言いたかった話です)

今なにしてるか

ということで勉強会つながりでお声がけいただいた某社で9月頭から働いております。 本当にありがたい話です。

*1:もちろん他にネガティブな理由もありますが、ここではふせておきます。

はじめての Apache Spark アプリケーション開発で困ったところ

このエントリについて

ここ2ヶ月ぐらい Apache Spark でバッチ処理をするアプリケーションを作っていました。 Apache Spark でがっつり何かを作るのは今回が初めてで、結構詰まったりしたところがありました。 自戒、および他の誰かの役にたてばという意味をこめてどういうところで困ったかというメモを残しておきます。

ちなみに Spark 1.1.0 で Java による開発という前提です。 (作ってるうちに Spark 1.2.0 が出てしまいました…)

困ったところ諸々

AWS EMR 上での jar ファイル利用

EMR 上で Spark アプリケーションとして作った jar ファイルを実行する方法が Apache Spark、AWS ともに公式提供されていません。 shell から動かせますよ、という記事ならあるのですが、やりたいのはそうじゃない。 最新の Spark バージョンが反映されるのもあまり早くありません。(本文執筆時点で 1.1.0 までしか載っていない)

なんかを参考にして頑張るしかありません。 そのうち誰かがいい感じの bootstrap スクリプトのセットをどこかに up してくれることでしょう…。(もしくは既に)

また Java で Spark を使う場合、ラムダ式を使えるかどうか、つまり Java 8 を使えるかどうかが開発効率にかなり影響します。 EC2 インスタンスはデフォルトでは Java 8 が入っていないので、Java の方にはそこも面倒な障壁になるでしょう。

Kryo Serializer のバイナリファイル入出力

公式ドキュメントにあるとおり、Spark ではシリアライズフレームワークとして Java Serialization と Kryo Serialization の2つを使えます。 ノード間のデータ移動やバイナリ形式でのディスク読み書きでシリアライズが使われるためパフォーマンスに大きな影響があります。 ドキュメントで

Kryo is significantly faster and more compact than Java serialization (often as much as 10x)

とあるとおり、公式では Kryo 推しな雰囲気があります。 Java Serialization の場合は自作クラスに java.io.Serializable を実装する必要がある一方、Kryo はよきにはからってくれる場合がほとんどであり、ここに書いてある速度・サイズの観点のみでなく開発効率でも Kryo に軍配が上がるでしょう。

ところが Kryo にも落とし穴がありました。

Though kryo is supported for RDD caching and shuffling, it’s not natively supported to serialize to the disk. Both methods, saveAsObjectFile on RDD and objectFile method on SparkContext supports only java serialization.

RDD からバイナリ形式でのディスクへのファイル読み書きが Kryo に対応していないとのこと。 saveAsObjectFile() が失敗して、結構悩んで上記リンクにたどりつきました。

解決策はリンク先にあるとおり、自分で byte 形式で読み書きできるメソッドを作ることです。 上記は Scala の例ですが、Java でも少し変えて似たような感じでできました。 早く Spark 本体で対応してほしいところです。

遅延評価

まあこれは Spark でプログラム書くなら最低限知っとけよって話だと思いますが…

次の例はテキストファイルを読み込み、各行の文字数を合計して全体の文字数を出すというものです。

logger.info("ファイル読み込みを開始します。");
JavaRDD<String> lines = sparkContext.textFile("data.txt");
logger.info("ファイル読み込みを完了しました。");

logger.info("各行の文字数カウントを開始します。");
JavaRDD<Integer> lineLengths = lines.map(s -> s.length());
logger.info("各行の文字数カウントを完了しました。");

logger.info("全体の文字数の合計を開始します。");
int totalLength = lineLengths.reduce((a, b) -> a + b);
logger.info("全体の文字数の合計を完了しました。");

こちらは極端な例ですが、システムのどこで問題が起こったか分かるようにアプリケーションのログを出すというのはよくあると思います。

上記の例は一見問題なさそうなんですが、実はログのメッセージと実際の動きが合っていません。 Spark の処理は効率化のため遅延評価されます。 Transformation 系のメソッドである map() の行を抜けた時点、つまり "各行の文字数カウントを完了しました。" のメッセージの時点ではまだ計算が始まっていません。 Action 系のメソッドである reduce() が実行されて初めて map 処理である文字数カウントの実行が始まります。

うっかりしているとこのように、実際の挙動と異なるタイミングのログメッセージを書いてしまったりします。反省。

Kryo でシリアライズできないケース

Kryo はほとんどの場合よきにはからってシリアライズしてくれる、と前述しました。 よきにはからってくれないケースの話です。

今回私が開発していたアプリケーションでは演算時間が結構シビアであるため、Java のコレクションクラスにもこだわろうという向きがありました。 こちらこのへんを見て、「Koloboke ってやつ良さそうやん?」ってなって Koloboke のコレクションクラスを多用した結果、これが失敗。 どうやら Koloboke のコレクションクラスのオブジェクトは Kryo でシリアライズできない場合があるらしく、NoSuchElementException が出まくって死にました。 一方でなぜか Kryo でシリアライズできてしまう場合もあり、そのために発見に時間がかかってしまいました。憎らしい。

よきにはからってくれない場合は KryoSerializable インターフェースを実装するという手もあります。 シリアライズまわりは何かと Spark 初心者が引っかかりやすいところなのかもしれません。

まとめ

  • Amazon さん、EMR の対応お願いします
  • Kryo でのバイナリ書き出しに注意
  • 遅延評価されていることを忘れるな
  • Kryo でなんでもシリアライズできるわけではない

繰り返しますが Spark 1.1.0 での話なので後続のバージョンでは改善されるかも。

同じようなことに引っかかった場合の一助にしていただけると幸いです。

参考になったサイト等

【勉強会】 Machine Learning with Apache Spark で発表しました

Machine Learning with Apache Spark

一昨日(2014-11-20)開催された Machine Learning with Apache Spark #sparkjp で「Spark MLlib でやってみる協調フィルタリング」というタイトルでお話させていただきました。

以下、発表資料です。

ここではないどこかのブログに書いた内容に+αしてお話させていただきました。 何気にオープンな勉強会での初めての発表だったという…

最後の方の推薦高速化の話ですが、こちらは同僚の @tof_mco 氏の仕事によるものでした。 ありがとうございます!

(以下は 2014-11-27 追記)

懇親会

イベント後に同会場で開催された懇親会で、他の発表者の方々と Apache Spark についてお話させていただきました。 非常に刺激的で面白く、勉強になりました。

その中でも印象的だったのが NTT データ 土橋さんがおっしゃっていた「Spark は書いてて楽しい」です。 Hadoop MapReduce にないサクサク感があるんですね。書いてみるとよくわかります。 私なんかはまだまだ Spark 初心者なんですが、すごく共感できました。

皆さん、Apache Spark は楽しいです。 使ってみましょう。

MCMC と EM アルゴリズムを比べてみた

このエントリについて

前回のエントリで PyStan の MCMC によって GMM (混合正規分布)を学習してみました。 一方、GMM の学習と言えば一般的には EM アルゴリズムが使われることが多いかと思います。

参考:

EM アルゴリズムは山登り法の一種であり、局所最適解(local minimum)に陥る可能性があるのが問題ですが、MCMC は局所最適解にとどまらないという利点を持っています。

この利点が活かされて本当に MCMC の方が EM アルゴリズムよりも良くなるのかを確認したいという欲求で実験してみました、というのがこのエントリです。 たぶん論文探せばあると思いますが自分でやってみたかったんですよ。

やること

やりたいことは以下のとおりです。 アルゴリズムの善し悪しは評価データに対する尤度で見ることにします。

  1. 多次元ベクトルデータを学習用/評価用に分ける
  2. 学習用データを使い、EM アルゴリズムで GMM を学習する
  3. 学習用データを使い、MCMC で GMM を学習する
  4. 評価用データに対するサンプル平均尤度を 2, 3 それぞれについて計算する
  5. 1〜4 をデータの区切りを変えて複数回実施する

使ったデータ

実験用にUCI Machine Learning Repositoryから適当なデータを探してきました。 今回は Wine Quality Data Set を使います。

このデータは酸性度や残存糖度、密度などの測定可能な11のパラメータおよび人の手による品質評価値により数々のワインを表現したものです。 その中でも白ワインのデータを使いました。(サンプル数: 4898) 品質評価値は除いて11次元のデータとして扱います。*1

プログラム

Stan および呼び出し側の Python のソースは以下です。

Stan

Stan code to train multi dimensional GMM (Gaussian ...

フル共分散だと学習対象のモデルパラメータが多くなるため、対角共分散を想定したモデルとなっています。

尤度計算の部分でフル共分散だと multi_normal_log() が使えたのですが対角成分だけでは使えないらしく、次元数で for ループを回していちいち加算しています。

Python

To compare EM algorithm and MCMC on GMM training.

長いですね…。以下解説です。

StanModel の永続化

Stan コードのコンパイルして StanModel インスタンスを作るには数十秒かかり、何回かスクリプトを回して試すときは結構なストレスになります。 これを避けるために StanModel インスタンスPythonpickle モジュールにより永続化しています。 (77行目付近)

pickle はシリアライゼーション、すなわちインスタンスのバイナリストリーム化を担うモジュールであり、かつ StanModel は pickable です。 コンパイル後に永続化しておくことで、次回以降はコンパイル処理は行わず、永続化されたインスタンスをロードするだけの短い処理で済ますことができます。

Cross Validation

4898サンプルの白ワインデータは学習データと評価データに分けて使いますが、1回の学習/評価だけでは心許ないので cross validation (交差検証)を行います。 Python機械学習ライブラリ scikit-learncross_validation モジュールは、データを学習用/評価用に分けるためのいくつかの手法を提供しています。

ここでは Random permutations cross-validation a.k.a. Shuffle & Split という手法を使います。ざっくり説明すると、指定の割合でのランダムなデータ分割結果を指定回数分作って List ライクな結果として返却します。 92行目でその結果を ss に入れています。その後、この ssfor 文を回してそれぞれの分割結果を取得します。

この実験では学習/評価データ分割を500回実施し、そのそれぞれで EM アルゴリズムMCMC を比較します。

EM アルゴリズム

EM アルゴリズムも scikit-learn で提供されています。misture.GMM インスタンスを生成し、学習データを与えて fit() を実行すれば OK。とても簡単。(107行目)

MCMC

MCMC によるモデルパラメータ学習は StanModel インスタンスoptimizing() メソッドで実施します。(114行目)

この実験ではデフォルトの2,000回のイタレーションでは学習が収束しないケースが多かったので、かなり長めの20,000回を指定しました。

尤度計算

アルゴリズムによる学習結果の GMM は、評価データに対する尤度という形で評価されます。 尤度は mixture.GMM.score() メソッドの結果をサンプルあたりの平均にするという形で計算しました。(109, 117行目) つまりサンプル平均尤度です。

上記のメソッドを利用するため、MCMC の結果は一度 mixture.GMM の形式に変換しています。

グラフ化

実験結果は最終的に matplotlib でグラフ化します。(127行目) X軸に EM アルゴリズムの尤度、Y軸に MCMC の尤度を取り、1つの実験結果のプロットが x = y のときの直線の上にくるか下にくるかでどちらが優勢かを判断します。 500回のデータ分割による cross-validation を実施しているので、500点プロットされます。

実験結果

尤度グラフ

ということでプロットされた結果は以下のようになりました。

f:id:soonraah:20141006041715p:plain

なんだこれは…???

EM アルゴリズムの尤度はだいたい -7.0 〜 -6.5 に収まっています。 一方で MCMC の尤度は2つに分かれており、-5.8 付近のグループ(上のかたまり)と-6.9付近のグループ(下のかたまり)に分かれています。 上のかたまりでは EM アルゴリズムに比べて MCMC の尤度がかなり良くなっていますが、下のかたまりでは MCMC が若干負けています。(対数尤度なので 0 に近い方が良い)

上記のスクリプトとは別で同一の学習/評価データで複数の、つまり乱数の異なる optimizing() を実行したところ、上のかたまり相当の尤度になる場合と下のかたまり相当の尤度になる場合があることが分かりました。 つまり Stan の MCMC も常に最適なところまでたどり着けるわけではなく、最適でないところで収束してしまうことがあるようです。(local minimum と言っていいのか?)*2

実行速度

MCMC の実行時間は EM アルゴリズムに比べ数百〜千倍のオーダーとなってしまいます。 予想はしていましたが、やはり遅い。

まとめ

その他、今回は Python の勉強が捗りました。scikit-learn はやはり面白い。

*1:このデータを表現するのに混合正規分布を使うのが本当に適切なのか?という点は考えません。同じフィールドで競わせたときに EM アルゴリズムMCMC どちらが良くなるのか、というのが今の興味だからです。

*2:しかし、①なぜこうもくっきり分かれるのか? ②なぜ下のグループは EM アルゴリズムにちょっぴり負けてしまうのか? ③MCMC の local minimum を避けるにはどうすればいいか? は未解決。分かる方いたら教えてください…