2011-09-12

Google Developer Day 2011 に参加するために、DevQuiz に初めて挑戦してみました。ウォームアップクイズ、分野別クイズはさておき、一番やりがいのあった「スライドパズル」について、自分の戦略などを書き残しておこうと思います。

ソルバーのソースコードは、http://code.google.com/p/k11i-gdd2011jp-slidepuzzle-solver/ にて公開しています。


言語

  • 回答期限までそこそこ時間があった
    →コーディングに多少時間がかかっても OK。
  • 計算・空間効率を追求する必要がありそう
    →言語自体の実行性能が高いこと。またある程度、内部の挙動を把握できる、かつ効率化のポイントを把握していること。
などの理由により、開発言語は Java を選びました。


ソルバーの戦略

ソルバーのプログラムは「ただひたすらにパズルを解く」ステージと、「利用可能な L/R/U/D の上限値をもとに、前ステージで得られた答えを取捨選択する」ステージに分けました。


パズルを解く戦略

「ただひたすらにパズルを解く」ステージは、当初から探索ベースの手法を前提としていろいろと試行錯誤した結果、「A* アルゴリズム」と「双方向探索」を組み合わせた実装となりました。この二つのアルゴリズムの組み合わせは、M.Hiroi さんの Algorithms with Python / ヒューリスティック探索 のページ内容をかなり参考にさせてもらっています。

この「A* + 双方向」の組み合わせでは最適解(最短手数)を求めるのが難しいのですが、それぞれを単体で利用する場合よりも圧倒的に速く問題を解くことができる(たいていの問題が 1 秒以下で計算可能)特徴があります。

A* アルゴリズムに限りませんが、幅優先的な探索アルゴリズムはメモリを富豪的に使うので、何も制御せずに問題を解かせると OutOfMemoryError をスローしてしまう可能性があります。今回のソルバーでは、展開される状態数に上限値を設けて、その上限値に達したところで解の計算を諦める制御ロジックを組み込んでいます。

A* アルゴリズムのヒューリスティック関数には、「マンハッタン距離」を用いています。ただ、壁の存在があるため、実際には単純なマンハッタン距離ではなく、壁を回避してたどり着く最短経路での手数を距離としています。なので、壁が一つもなければ、常にマンハッタン距離と等しくなります。


回答を選ぶ戦略

算出された各問題の答えの集合から実際に提出する回答を選ぶ処理は、貪欲なロジックで実装しています。つまり、既定の L/R/U/D 利用上限値をすべて下回るまで、L/R/U/D それぞれの利用が多い答えを捨てる仕組みとなっています。しかしながら、今回のソルバー/実行環境では、この機能が実行されることはありませんでした…


処理効率の最適化

上記の戦略に基づくソルバーをそこそこの性能の PC で実行して、40 点前後のスコアを 1~2 時間で獲得することができました。もう少し高いスコアを目指すために、これより先はひたすらアルゴリズム以外の最適化に手を尽くしました。


状態保存の空間効率向上

当初のソルバーでは、盤面上のパネルの配置状態を 1 つのパネルにつき 1 バイト消費するようにしていました。しかし実際には、最大の 6x6 パズルにおいて 1 パネルの配置状態を 6 ビットで表すことができます。このため、4 バイト(32 ビット)で 5 つのパネルを表現するように実装を改めました。これにより、6x6 = 36 バイト必要だった盤面の状態表現を、約 4/5 の 32 バイトで表現できるようになりました。

また盤面のパネル配置状態のみならず、付随的な複数の情報(双方向探索の探索向きや、手数、距離コスト)も、(C でいうところのビットフィールド的なアプローチで)1 つの 32 ビット数値で効率よく表現するようにしました。


ハッシュ値の計算効率化

パネルの配置状態をハッシュ表(HashMap)に記録して探索の重複チェックを実現していたので、上記の 4 バイトで 5 パネルを表すようにする改修に合わせて、ハッシュ値の計算を 1 パネルずつではなく 5 パネルまとめて計算するようにしています。また、一度計算したハッシュ値はキャッシュすることで、ハッシュ値の計算コストを低く抑えるようにしています。


ライフサイクルの短いオブジェクトを再利用する

オブジェクトの生成は Java にとってそれなりにコストのかかる処理なので、いったん生成してすぐに不要になってしまったオブジェクトを再利用する(フィールドだけごそっと入れ替える)仕組みを組み入れました。もともと immutable に実装したクラスを無理矢理こじ開けて mutable にしたりと、あまり気持ちのいいものではないですが。


ハッシュ表を自作する

Java クラスライブラリの HashMap は汎用的に作られているため、今回のソルバーとしては余計な機能が付いていたり 1 エントリあたりのヒープ消費に Map.Entry が加算されてあまりうれしくないので、HashMap を簡略化したものを開番地法で実装しました。これにより計算効率と若干の空間効率の向上が達成できます。


古臭い・妖しいコーディング

「for (int i = 0;...) が許されるのは JDK 1.4 までだよねー」とか言われかねなけど、for-each 文を使わなかったり、オブジェクトの等価判定に == 演算子を使ったり、メソッドのインライン展開を狙って final 修飾子をつけてみたりしました。効果のほどは定かではないですが。


JVM を 64 ビット化

32 ビットの JVM では、利用できるメモリ空間が小さいため、Java の環境を 64 ビットの JDK に差し替えました。これにより 8 GB の物理メモリ+ページファイルのサイズ分、ヒープを確保することができるようになりました。また、計算効率も 32 ビット版に比べて心なしかよくなったように思います。


そのほか試してみたこと


ヒューリスティック関数の(デ)チューニング

A* のヒューリスティック関数を前述のマンハッタン距離ベースのものから、パネルの位置によって重みを加えてみたものに変えてみたり、距離を +1 してみたりと、試行錯誤してみました。特に距離 + 1 のヒューリスティック関数は、通常のマンハッタン距離のものよりも早く答えを見つけ出せる(代わりに手数は多くなる…)など面白い結果が確認できたのですが、処理時間が遅くなるなどの理由で結局採用しませんでした。


Simplified Memory-bounded A* (SMA*) への差し替え

ヒープの大量消費がソルバーの悩みの種だったので、コアとなる探索アルゴリズムを SMA* に差し替えようと検討してみました。しかし、答えを出力するための履歴をどのように保持するべきかが把握できなかったのと時間的制約により、あえなく断念しました。


Java VM のパラメータチューニング

JVM を 64 ビット化してヒープをよりたくさん利用できるようになったものの、オブジェクトポインタも 4 バイト→ 8 バイトになっているようで、オブジェクトを大量に生成した場合にかなりの勢いでヒープを大量消費してしまう様子がうかがえました。JDK 6 のいつかのバージョンからか、オブジェクトポインタを圧縮できる仕組みが備わったようで、それを有効化(-XX:+UseCompressedOops)してみましたが、結果は変わらず。仕方がないので、ページファイルを利用してヒープ領域の拡大する方向に突き進みました。


やり残したこと


マルチコア化

ソルバーの調整については終始、計算効率を気にしながら行っていましたが、その割にマルチコア CPU を一切有効活用せず、シングルコアでひたすら頑張る構成にしてしまったのがちょっと残念でした。すべてのコアを活用できれば、2~3 割は速くなったはず…


人間的なアルゴリズムで解く

メモリの大量消費するような問題を解く場合、人間的なアプローチで問題を完全に解く、あるいは上・左半分など途中まで解く(以降は A* + 双方向で計算する)アルゴリズムを組み込めばよいのでは? と考えていたのですが、「壁」の存在によりこのアルゴリズムを一般化することができませんでした。


最終結果・感想

最終的に物理メモリ+ページファイルで 20G のヒープを構成して実行し、4832 問を 3 時間ちょっとで解けるまでになりました。メモリさえあれば、5000 問全問解くのも難しくはなさそうです。メモリさえあれば…。でも、この結果には満足しています。A* アリゴリズムとか、大学の講義で聞いただけで業務で使うことなんて今まで一度もありませんでしたが、実際に触れてみるとなかなか楽しいものです。機会があれば業務でも使ってみようかな? ないと思うけど。

2011-06-07

今となってはかなり古い部類に入る論文ですが、レコメンデーションの基礎を改めて勉強し直すために読んだので、そのメモを残しておきます。1

Amazon.com Recommendations: Item-to-Item Collaborative Filtering


この論文が議論の対象としているのは、(Amazon.com のような)数千万ユーザ・数百万点の商品(アイテム)という大規模なデータセットに対し、リアルタイム(遅くとも 500ms 以下)、オンライン 2 で、かつ高品質な推薦を行うという問題です。Amazon はこの問題をアイテムベースの協調フィルタリングで解決しています。

ユーザベースの協調フィルタリング


協調フィルタリングの詳細については こちらの資料 に譲るとして、端的にいうと「協調フィルタリング」というのは、アクティブユーザ(推薦対象のユーザ)に類似する他のユーザを、商品購入履歴や評点情報の近さから探し出し、そのユーザが購入している商品をアクティブユーザに推薦する、というものです。

古典的な GroupLens のユーザベース協調フィルタリングでは、時間計算量の制約から、オンラインでの推薦を提供できるのは中規模(数十万ユーザ、数万点の商品程度?)のデータセットまでとなっているようです。このユーザベースの協調フィルタリングの時間計算量は、ユーザ数を m、商品数を n とすると、最悪のケースで O(mn) となります。ただし、実際のデータセットにおいては、ユーザと商品の関係が疎であることが多いので、その場合には O(m + n) の時間計算量に近くなるそうです。どちらにせよ、Amazon ほどの大規模なデータセットにおいては、O(m + n) の時間計算量でさえもオンライン・リアルタイムでの推薦を難しくする要因となり得ます。

このユーザベースの協調フィルタリングを大規模データセットに適用する場合は、時間計算量を小さくする工夫が必要になります。この論文では以下のように、データの規模を減らすことで時間計算量を小さくする手法が挙げられています。
  • ユーザをランダムサンプリングして、全体のユーザ数を減らす
  • 購入量の少ないユーザを省く(類似度計算結果の精度が低く、推薦にあまり役立たないため)
  • とてもよく購入されている/ほとんど購入されていないアイテムを省く
ほかにも、商品の集合をそのカテゴリごとに分類し、その分類された商品の集合内で推薦処理を行う方法も挙げられています。しかしながら、いずれの手法を採用するにしても、推薦の品質・精度が低下してしまう問題がつきまとってしまいます。

クラスタモデルの手法


ユーザベースの協調フィルタリングでは、リクエストの都度、ユーザ間の類似度を計算して、アクティブユーザに類似するユーザを探していました。一方でクラスタモデルでは、ユーザ集合を類似するユーザ同士であらかじめクラスタリングしておきます。このクラスタリング処理は、推薦処理とは切り離してオフラインで計算することができます。推薦処理では、このユーザのクラスタを利用し、アクティブユーザがどのクラスタに属するかを判定したのちに、そのクラスタに属する他のユーザの情報を利用して推薦が行われます。

このクラスタモデル、計算時間の観点では優れた手法ではありますが、推薦品質については決して高くはないようです。推薦品質を向上させるためにはクラスタの数を増やす必要があり、クラスタ数を増やしてしまうと、オンラインでの計算量が増えてしまう、という問題を抱えています。

Amazon.com のアイテムベース (Item-to-Item) の協調フィルタリング 3


以上のように、大規模なデータセットに対して高品質・高精度で、かつパフォーマンスのよい推薦を実現するのは難しい問題と言えます。Amazon はこの問題に対し、アイテムベースの協調フィルタリングを利用することで解決を図っています。

Amazon のアイテムベース協調フィルタリングの一番の特徴は「アイテム間の類似度行列をオフラインで計算して、推薦に備えておく」ことです。アイテム間の類似度行列の計算は、最悪のケースで O(n^2 * m)、疎なデータセットでも O(nm) の時間計算量となりますが、オフラインで計算するのであればこの計算量は許容できる範囲になるのではないでしょうか。また、よく購入されている商品を購入したユーザをサンプリングしてアイテム間の類似度行列を計算することで、品質・精度の低下を小さくしつつ、時間計算量を削減できるようです。

推薦処理では、このアイテム間の類似度行列を利用します。その推薦処理の時間計算量は、ユーザ数や商品総数に依存せず、アクティブユーザの購入商品数、評点情報数にのみ依存します。そのため、大規模データセットであっても、オンラインでの推薦処理で充分な性能が出せるようになる、とのことです。

また、このアイテムベースの協調フィルタリングは、アクティブユーザの購入済みの商品が 2,3 個程度と僅かな状況であっても、質の良い推薦が実現できます(ユーザーベースの協調フィルタリングでは、類似するユーザーを探すためにそれなりの数の購入商品数を必要とするので、2,3 個程度の商品数では十分な推薦が実現できません)。

まとめ


大規模データセットに対して推薦をする場合、高いパフォーマンスと推薦品質・精度の両立は簡単ではありません。Amazon.com は、アイテムベースの協調フィルタリングを採用することで推薦品質・精度の問題を解決し、またその協調フィルタリングで利用するアイテム間類似度行列をオフライン計算することでパフォーマンスの問題を解決しています。

感想など


普段扱っているデータの規模が大きくても数十万ユーザ、数万アイテム数だというのに、この程度でヒイヒイ言っている自分が情けなくなりますね… 規模の大きいデータにもっと慣れねば!


1:個人的な解釈が多分に含まれているので、この記事を参考にすることがもしあれば、一度原文と照らし合わせてみることをお勧めします。
2:推薦すべき商品を事前に計算して準備しておくのではなく、リクエストが来たところで初めて推薦する商品を算出する方式。論文の記述から察するに、ショッピングカート内の商品から推薦する場合などにも利用されているらしい。
3:アクティブユーザに類似するユーザを探すのではなく、あるアイテムに類似する別のアイテムを探すタイプの協調フィルタリングを、ここでは「アイテムベースの協調フィルタリング」と呼んでいます。

2011-02-19

nokuno さんの記事「オープンソースのTrieライブラリまとめ」あたりを参考に、まず既存の Trie ライブラリ群がどのような API を提供しているのかを調査し、その上でこれから Trie を実装する場合に、どのような操作・API を提供すべきかを検討した結果のメモです。

記事にあるすべての Trie 実装を確認するのはしんどいので、代表的な感じのものを適当にピックアップしてみました。

  • Tx ... 岡野原さんによる簡潔データ構造を利用した Trie の実装。
    • prefixSearch() ... prefix search。Trie に格納されている文字列の中で、対象文字列の接頭辞としてもっとも長く一致する文字列を探し出す。common prefix search で列挙される文字列のうち、長さが最長のものと同じ。
    • commonPrefixSearch() ... common prefix search。Trie に格納されている文字列より、対象文字列の接頭辞にあたる文字列をすべて列挙する。結果は一括して求められる。
    • predictiveSearch() ... predictive search。Trie に格納されている文字列より、対象文字列が接頭辞となる文字列をすべて列挙する。結果は一括して求められる。
    • expandSearch() ... common prefix search + predictive search。Trie に格納されている文字列より、対象文字列を接頭辞とする文字列、または対象文字列の接頭辞にあたる文字列を列挙する。結果は一括して求められる。
  • UX ... Tx と同じく岡野原さんによるプロダクト。さらに簡潔。だいたい Tx と同じ API 構成。この命名は、"Tx" の1つ先(t -> u)を行く、という意味が込められているのかな?
    • prefixSearch() ... prefix search。
    • commonPrefixSearch() ... common prefix search。
    • predictiveSearch() ... predictive search。
  • sumire-tries ... やたさんによる、簡潔データ構造を含む各種 Trie の実装。Trie 木構造のノードレベルでの走査(traversal)ができるのが特徴。
    • TrieBase#find() ... exact match。Trie に格納されている文字列より、対象文字列に完全一致する文字列を探し出す。
    • TrieBase#follow() ... Trie・ノードの走査。指定されたノードから始まり、対象文字列に合致する Trie 上の経路(ノード)を辿る。
    • TrieBase#find_child() ... Trie・ノードの走査。あるノードより指定された文字を辿った先にある子ノードを求める。
    • TrieBase#child() ... Trie・ノードの走査。指定のノードの先にある子ノードのうち、最初の子ノードを求める。
    • TrieBase#sibling() ... Trie・ノードの走査。指定のノードの、次の兄弟ノードを求める。
    • class CompleterBase ... predictive search。Iterator パターンで、文字列を順次列挙する。
  • marisa-trie ... やたさんによる、簡潔データ構造を利用した Trie の実装。UX の手法をさらに発展させたものっぽい。
    • lookup() ... exact match。sumire-tries では find() でしたが、marisa-trie では同名メソッドは別の機能を提供しているようです。
    • find() ... common prefix search。一括して列挙する。
    • find_first()/find_last() ... prefix search。
    • find_callback() ... common prefix search。1つずつ、コールバック関数を呼び出して列挙する。
    • predict() ... predictive search。一括して列挙する。
    • predict_callback() ... predictive search。1つずつ、コールバック関数を呼び出して列挙する。
  • Darts ... MeCab 開発者の工藤さんによる Double Array Trie の実装。MeCab でも利用されています。
    • exactMatchSearch() ... exact match。
    • commonPrefixSearch() ... common prefix search。一括して列挙する。
  • Doar ... Igo/Gomoku の開発者 sile さんによる Double Array Trie の C++ 実装。
    • Searcher#search() ... exact match かな?
    • Searcher#common_prefix_search() ... common prefix search。1つずつ、コールバック関数を呼び出して列挙する。
    • Searcher#children() ... Trie・ノードの走査。子ノードを1つずつ、コールバック関数を呼び出して列挙する。
  • jada ... sile さんによる Double Array Trie の Java 実装。
    • Trie#search() ... exact match。
    • Trie#commonPrefixSearch() ... common prefix search。同メソッドを繰り返し呼び出して、1つずつ列挙する。

こんなところでしょうか。以上より「Trie を使った操作」は、
  • exact match
  • common prefix search
  • predictive search
  • prefix search
の4つが用意できるとよさそうです。少なくとも、上から3つは必須となりそうですね。

「Trie の走査を実現する走査」としては、ピックアップした実装ではあまり提供されていませんでしたが、
  • あるノードの直下の子ノードを列挙する
操作は必須となりそうです。

この結果を参考に、汎用的に使えそうな Trie の Java 実装について検討を進めてみます。