2013-03-16

Interleavingについて

情報検索において検索手法の結果を評価する方法の手法の一つにInterleavingという方法がある。最近その辺についてちょっと読んでいたのでまとめておく。

検索エンジンにおいては何らかのRanking Function(http://en.wikipedia.org/wiki/Ranking_function)を用いて、与えられたクエリに対する検索結果を並び替える。

例えば"餃子レシピ"というクエリでGoogleで今検索したところ

1. http://cookpad.com/recipe/316319 (☆ほっぺが落ちちゃう　餃子☆)
2. http://cookpad.com/category/836 (餃子・シュウマイレシピ 306品)
3. http://matome.naver.jp/odai/2133424266153597701 (絶品餃子！！肉汁がやばい究極のギョーザのレシピを厳選！#レシピ #ギョーザ)

みたいな順番ででる。このとき別の評価関数を使えば

1. http://cookpad.com/recipe/316319 (☆ほっぺが落ちちゃう　餃子☆)
2. http://matome.naver.jp/odai/2133424266153597701 (絶品餃子！！肉汁がやばい究極のギョーザのレシピを厳選！#レシピ #ギョーザ)
3. http://cookpad.com/category/836 (餃子・シュウマイレシピ 306品)

上のように並び替えられる可能性もある。

このときどちらがいい検索結果なのかを判定するという問題がでてくる。

一つは検索の品質についてのガイドラインをさだめ、人手によりプロの評価者が検索結果を評価するという方法がある。例えばGoogleでもガイドラインを公開している。

しかし人手による評価だとすべてのクエリに対応は難しく、またパーソナライズ検索のような個々人によって検索結果が変わるような場合対応するのが難しい。そのためオンラインで実際にテストを行って、よりクリックされる方を採用するという方法が一般的には行われる。(実際には人手による評価である程度チェックした後、オンラインでのテストが行われることが多い)

この時、一つの方法としてはA/Bテストがある。バケットごとに別々の評価関数で並び替えた結果を出して、バケットごとのCTRなどを計測してどちらがよいかを決定する。しかしこの場合だと新しいアルゴリズムを入れた時に結果が大きく変わってしまう可能性があり、場合によっては好ましくない。そのため二つの評価関数によって得られた二つのリストの結果を混ぜあわせて表示するInterleavingという手法がある。

手法について

手法についての以下の記述は文献[1]を参考にした。なお文献[1]はWSDM 2013のBest Paperとなっている。

Balanced Interleaving [4]

各リストの順位の高いものから取っていく。また同点の場合はどちらを先にとるかはランダムで決定する。
例えばリスト1の結果が(a,b,c)、リスト2の結果が(c,a,e)だった場合、リスト1から取っていく場合

まずリスト1の一番目のaをとる
次にリスト2の一番目のcをとる
最後にリスト1の二番目のbをとる
結果のリストは(a,c,b)となる

リスト2から取っていく場合

まずリスト2の一番目のcをとる
次にリスト1の一番目のaをとる
最後にリスト2の二番目のaはすでにとられてるのでリスト1の二番目のbをとる
結果のリストは(c,a,b)となる

しかし、この方法には問題があって例えばa,b,cランダムにどれかをクリックするユーザがいたとしたらどちらの結果においても(a,b)がクリックされるとリスト1がよいとみなされリスト1の結果のクリック数はリスト2のクリック数の2倍となる。このため次に挙げられるTeam Draftという方法がある。

Team Draft [3]

これはドラフトのように一回のとるときにコイン投げを行なって、勝ったほうが自分のリストの上にあるものをとっていくという手法である。リスト1の結果が(a,b,c)、リスト2の結果が(c,a,e)だった場合結果は4通りあり

まずリスト1の一番目のaをとる
次にリスト2の一番目のcをとる
最後にリスト1の二番目のbをとる
結果のリストは(a,c,b)となる

まずリスト1の一番目のaをとる
次にリスト2の一番目のcをとる
最後にリスト2の三番目のeをとる (aをは取られてるので)
結果のリストは(a,c,e)となる

リスト2から始める場合も同様にすると結果のリストは

(c,a,b)
(c,a,e)

となる。

しかしこの方法でも問題が発生して、例えばリスト1の結果が(a,b,A)、リスト2の結果が(b,A,a)でAの文章のみが良かった場合、リスト2の方がAを上位に持ってこれているが、Team Draftの結果だと

(a:1, b:2, A:1)
(a:1, b:2, A:2)
(b:2, a:1, A:1)
(b:2, a:1, A:2)

となっており、Aのみがクリックされるとどちらがよいかを結論付けることができない。

Probabilistic Interleving [2]

Team Draftとどうようコイントスをしてどちらのリストから優先するかを決めるが、ペアでとるのではなく一回一回コイントスを行う。このため極端な話、リスト1から全て持って来られることもありえる。また上からとってくるのではなくリストの中から確率的にどの文章をとるか決める(ただし上位のものが高い確率でとられるようにする)

上の二つのような問題は発生しないが、確率的にすべてのリストの組み合わせが発生しうるのでもとのリストの両方からかけ離れた結果が得られることがある。また文献[1]においては二つのリストの差がでるまでに多くのクエリで評価する必要があるという実験的結果が得られている。

Optimized Interleaving [1]

Interleavingに必要な要素を定式化して最適化問題としてInterleavingしたリストの表示確率を計算する手法。

確率的な方法となっているが、まず可能なリストとしてリストA,BがあったときにInterleavingしたリストLが必ずTeam Draftなどのように二つのリストの上からとってきたものになるような制約を入れる。すなわちA=(a_1,a_2),B=(b_1,b_2)だった場合可能なリストとしてはL=(a_1,a_2),(b_1,b_2),(a_1,b_1)の3通りとする。例えば(a_2,b_1)などは含まない。また各リストの出現確率をp_iとする。

そしてbalanced interleavingの例で出した、ランダムに文章をクリックするユーザに対しては期待値が0となるようなcredit functionを設定する(credit functionはLのi番目がクリックされたときにどっちのリストにどの程度配分するかを表す)。

この制約のもとで例えばsensitivityが最大になるように最適化問題を解く。sensitivityはi番目の文章がクリックされたらAが勝つ確率、Bが勝つ確率のエントロピーとかをつかってその期待値を計算する(たとえばどれがクリックされてもAが絶対勝つようなリストはエントロピーが0となる)

まとめ

オンラインテストにおいて二つのRanking functionを比較するためのInterleavingという手法について紹介した。
この方法はCIKM, WSDMとかで一本ぐらいは大体出てる気がするけど日本ではあまり知られてないので参考になると幸いです。

参考文献

[1] Optimized Interleving for online retrieval evaluation, WSDM 2013
[2] A probabilistic method for inferring preferences from clicks, CIKM 2011
[3] How does clickthrough data reflect retrieval quality?, CIKM 2008
[4] Evaluating retrieval performance using clickthrough data. Text Mining 2003

2012-10-03

[機械学習] A few useful things to know about machine learning

タイトルの論文はCommunication of the ACM, 2012のレビュー記事
ドラフトバージョンは下のリンクから読める。
http://homes.cs.washington.edu/~pedrod/papers/cacm12.pdf

割と面白かったのでいくつか内容を紹介

概要

機械学習システムはデータから自動でタスク(スパムフィルタ、レコメンドなど)をどうやって実行するかを見出すことができます。

しかしながら機械学習システムを成功させるには教科書を読んだだけではなかなか見つけづらいお約束事とかがあって、思うようには行かないことが多い。

本文献では機械学習の研究者および実務に携わる人間が知っておくべきである事柄を12個に要約しています。

一般化が重要

機械学習のゴールは訓練データにはないデータに対しても一般化して推定ができるという点になります。単に訓練データのみ分類できればよいならば事例を丸暗記することによって可能となります。しかしこの場合は訓練データにないデータに対してはランダムな性能しか得られない。

このため、識別機の利用時には訓練データとテストデータを分離することが重要となります。機械学習の初期ではこの二つを分離することはあまりやられてきませんでした。これは当時は線形判別みたいな表現力の低い学習機を利用していたので問題にはならなかった(例えば統計でよくでてくる身長に対して体重を予測する単回帰分析とかであればデータにフィットさせたとしてもそこまでデータに対して最適化できない)

データだけでは十分ではない

例えば二値分類問題において、100次元の2値の特徴量をもつデータが100万点存在したとして、取りうる値である2^100に対して2^100 - 10^6点に関するデータの情報が抜けている。もしこれらに対してのラベルがランダムに振られていたとしたらどんな機械学習アルゴリズムを使ったとしてもランダムな推定よりもよくなることはない(いわゆる"no free lunch"定理)

しかし、データは実際にはランダムにすべての可能な数学的関数からサンプリングされた関数から生成されているわけではなく、実際は類似したデータは類似したラベルを持つなどの性質や変数間の従属関係が存在する。

このため解きたい問題のドメインの知識をうまく利用することにより適切な学習方法を選択してやることができる。

学習の際にデータに関する知識がいることは驚くべきことではない、機械学習は魔法ではなく、無から有を得ることはできない。
機械学習は農業に似ていて、農家が種と肥料をやることにより作物を得るのと同様に、機械学習アルゴリズムはデータとそれに対する知識を合わせることによって学習器を作れる。

過学習について

単純な分類器はデータが少なくても、大きく予測を外さない。一方複雑な分類器はデータが大きくないと、予測を大きく外すことが多い。

Feature Engineeringが鍵になる

いくつかの機械学習プロジェクトは成功し、他は失敗する。この二つを分ける一番重要な点はどういう特徴量を使ったかによる。多くの独立かつ予測したい値と相関がある変数があれば学習はうまくいく、一方で複雑にからみあった変数から学習するのは非常に難しい。そしてたいていの場合生のデータは複雑なのでそこからどういう変数を取り出すかがカギとなっていく。

高次元においては直感はうまく働かない

このため、一見特徴量を増やせば増やすほど悪くてもその特徴量が使われなくなるだけだと思われるが実際には精度が悪くなったりする。

データ数を増やせば賢いアルゴリズムを使うよりもよくなる

たいていの場合データを増やせば増やすほど精度は高くなる。さらに精度が高いとされている複雑な学習機はデータが増えたときにスケールしないことが多いので、まずは単純な学習器を試してみることが必要。

さらに機械学習の論文では精度や計算量しか評価されないが、実問題では人間が理解しやすい学習結果を提示することにより、機械学習の専門家とドメインの専門家が協業しやすくなる。

複数のモデルを学習する

多くの研究では自分の好きな学習器を一つ選んで、その優位性を議論することが多いが、実際にはbaggingのような複数の学習器を作成してそれらで多数決をとったりする方がよい。

2012-02-12

[IR] 転置インデックスとtop-k query

転置インデックスから上位k件の文章を取ってくる手法について、知ってる範囲でまとめてみました。

転置インデックスとTop k-query

View more presentations from tsubosaka

この辺の話は教科書だと

Information Retrieval: Implementing and Evaluating Search Engines (MIT Press)

作者: Stefan Buettcher,Charles L. A. Clarke,Gordon V. Cormack
出版社/メーカー: The MIT Press
発売日: 2010/07/23
メディア: ハードカバー
購入: 2人クリック: 78回
この商品を含むブログ (8件) を見る

のChapter 5とかに疑似コードなども含め載っているので、参考になるかと思います。

2012-02-11

WikipediaのデータをLuceneのindexに入れるコード

プログラミング

以前書いたけどいつもjavaのXMLライブラリの使い方とか忘れるので備忘録用に上げておく

import java.io.File;

import javax.xml.parsers.SAXParser;
import javax.xml.parsers.SAXParserFactory;

import org.apache.lucene.analysis.Analyzer;
import org.apache.lucene.analysis.standard.StandardAnalyzer;
import org.apache.lucene.index.IndexWriter;
import org.apache.lucene.index.IndexWriterConfig;
import org.apache.lucene.store.Directory;
import org.apache.lucene.store.FSDirectory;
import org.apache.lucene.util.Version;


public class CreateIndex {
  static void addXMLFile(String file) throws Exception{
    SAXParserFactory spf = SAXParserFactory.newInstance();
    SAXParser parser = spf.newSAXParser();    
    File wikiFile = new File(file);
    if(!wikiFile.exists()){
      System.err.println(wikiFile +" not exist");
      return ;
    }
    Directory dir = FSDirectory.open(new File("enwiki-index"));
    Analyzer analyzer = new StandardAnalyzer(Version.LUCENE_35);
    IndexWriterConfig conf = new IndexWriterConfig(Version.LUCENE_35, analyzer);
    IndexWriter writer = new IndexWriter(dir , conf);
    WikiDataHandler wph = new WikiDataHandler(writer);
    parser.parse(wikiFile, 
        new WikiXMLHandler(wph));
    System.out.println("add " + wph.adddoc +" document");
    try{
      writer.close();      
    }catch (OutOfMemoryError e) {
      writer.close();
    }
  }
  public static void main(String[] args) throws Exception{
    addXMLFile(args[0]);
  }
}

import org.xml.sax.Attributes;

import org.xml.sax.SAXException;
import org.xml.sax.helpers.DefaultHandler;



public class WikiXMLHandler extends DefaultHandler{
  boolean isTitle;
  boolean isText;
  StringBuilder titleBuffer;
  StringBuilder textBuffer;
  WikiDataHandler wphandler;
  public WikiXMLHandler(WikiDataHandler h) {
    isTitle = false;
    isText = false;    
    titleBuffer = new StringBuilder();
    textBuffer = new StringBuilder();
    wphandler = h;
  }

  @Override
  public void characters(char[] ch, int start, int length) throws SAXException {
    String s = new String(ch ,start , length);
    if(isTitle){
      titleBuffer.append(s);
    }else if(isText){
      textBuffer.append(s);
    }
  }
  
  @Override
  public void startElement(String uri, String localName, String qName,
      Attributes attributes) throws SAXException {
    if(qName.equals("title")){
      isTitle = true;
      titleBuffer = new StringBuilder();
    }else if(qName.equals("text")){
      isText = true;
      textBuffer = new StringBuilder();
    }
  }
  
  @Override
  public void endElement(String uri, String localName, String qName)
      throws SAXException {
    if(qName.equals("title")){
      isTitle = false;
    }else if(qName.equals("text")){
      isText = false;
      String title = titleBuffer.toString();
      String text = textBuffer.toString();
      wphandler.handle(title, text);
    }
  }
}

import org.apache.lucene.document.Document;

import org.apache.lucene.document.Field;
import org.apache.lucene.document.Field.Index;
import org.apache.lucene.document.Field.Store;
import org.apache.lucene.index.IndexWriter;


public class WikiDataHandler {
  int adddoc = 0;
  IndexWriter writer;
  public WikiDataHandler(IndexWriter writer) {
    this.writer = writer;
  }
  private boolean isNotMainSpaces(String title){
    String[] prefixes = {
        "Category:",
        "File:",
        "Template:",
        "Talk:",
        "Wikipedia:",
        "User:",
        "User talk:",
        "Help:",
        "Special:",
        "MediaWiki:"
    };
    for(String prefix : prefixes){
      if(title.startsWith(prefix))return true;
    }
    return false;
  }
  private boolean isRedirectPage(String text){
    return text.toLowerCase().startsWith("#redirect");
  }
  public void handle(String title , String text){
    if(isNotMainSpaces(title))return ;
    if(isRedirectPage(text))return ;
    adddoc++;
    Document doc = new Document();
    doc.add(new Field("title", title, Store.YES, Index.NO));
    doc.add(new Field("content", text, Store.NO, Index.ANALYZED));
    try{
      writer.addDocument(doc);      
    }catch (Exception e) {
      e.printStackTrace();
    }
  }
}

2012-01-14

Lucene ソースコードリーディングメモ

今日はmixiでLucene ソースコードリーディングに参加して、Scorerの部分を読んでました。

Scorerについて

Scorerは与えられたクエリに対して文章をidの昇順で返すような抽象クラスです。
検索で使われるメインの部分は以下のようになっており、collectorに対してnextDoc()によって求まる適合した文章を渡すというのを繰り返しています。

  protected boolean score(Collector collector, int max, int firstDocID) throws IOException {
    collector.setScorer(this);
    int doc = firstDocID;
    while (doc < max) {
      collector.collect(doc);
      doc = nextDoc();
    }
    return doc != NO_MORE_DOCS;
  }

nextDoc()の実装例

DisjunctionSumScorerは複数のScorerが与えられたときminimumNrMatchers以上の個数のScorerに対して適合する文章番号を返します。

複数のScorerはScorerDocQueueというScorerのためのPriorityQueueによって管理されます。
これはScorerの文章id順にScorerを保持します。nextDoc()の実装は基本的にはadvanceAfterCurrentを呼ぶだけになっています。

advanceAfterCurrentの実装は以下のようになっています。

  protected boolean advanceAfterCurrent() throws IOException {
    do { // repeat until minimum nr of matchers
      currentDoc = scorerDocQueue.topDoc();
      currentScore = scorerDocQueue.topScore();
      nrMatchers = 1;
      do { // Until all subscorers are after currentDoc
        if (!scorerDocQueue.topNextAndAdjustElsePop()) {
          if (scorerDocQueue.size() == 0) {
            break; // nothing more to advance, check for last match.
          }
        }
        if (scorerDocQueue.topDoc() != currentDoc) {
          break; // All remaining subscorers are after currentDoc.
        }
        currentScore += scorerDocQueue.topScore();
        nrMatchers++;
      } while (true);
      
      if (nrMatchers >= minimumNrMatchers) {
        return true;
      } else if (scorerDocQueue.size() < minimumNrMatchers) {
        return false;
      }
    } while (true);
  }

ここでtopNextAndAdjustElsePopというのはpriorityQueueの先頭、すなわちidの最も小さいScorerの文章番号を進めて、priorityQueueの制約条件を維持します。もしScorerの次の文章が存在しない場合、priorityQueueからの除去も行います。

Scorerは他にも全てのScorerにマッチする文章のみ返すConjunctionScorer,Scorer A,BのうちAにはマッチするがBにはマッチしない文章のみ返すReqExclScorer, これらの組み合わせによりBooleanQueryを実現するBooleanScorer2, 通常の転置インデックスに近い動きをするTermScorerなどがあります。

実際類似検索を行うときには複数のTermScorerを閾値1のDisjunctionSumScorerを使って列挙する形になります。

2011-09-03

ACL 2011読み会で発表してきました

NLP 機械学習

木曜時点では発表する気がなかったのですが、金曜に人が足りなそうだったので急遽発表することに決定。
識別モデルを使って言語モデルの予測精度を上げるという話。

発表資料：

A scalable probablistic classifier for language modeling: ACL 2011 読み会

View more presentations from tsubosaka

他の発表については

http://d.hatena.ne.jp/nokuno/20110903/1315059435

を参考にされたい。

勉強会では機械翻訳、POSタギング、トピックモデル、ランキング学習、共参照、係り受け解析、スペル訂正、言語モデルと全員違う話をしていて面白かったです。

2011-08-20

Regularized Latent Semantic Indexing

機械学習論文

最近勉強会で発表する予定のものと仕事関係の論文しか読んでなかったのでこのブログにはあんまり書けなかったんだけど、久々に書いてみる。

紹介する論文はSIGIR 2011のLSIを語彙数が大きい時にも効率的に並列化できるようにしたという論文[1]。

論文概要

PLSIやLDAみたいなトピックモデルは情報検索においても性能向上で重要であるが、語彙数が多い時スケールしないという問題点がある(文章数に関しては効率的な実装が知られている。例えば[2])。このためよく行われるのが語彙数を1万とかに制限する方法ですが、情報検索への応用を考えるとこのアプローチは問題がある(文章分類やクラスタリングへの応用であればこれで問題ない)。

このため著者らはRLSIという方法を提案した。これにより160万文章、語彙数700万のデータセットに対して16台のマシンでトピック数500のとき1時間半で処理できた(おそらく1イテレーションの時間、トータルのイテレーション回数の記述は見つけられなかった)。

既存手法について

情報検索におけるトピックモデルの手法としては、まずLSI(潜在意味解析)がある。しかしこの方法では直交制約などがあるためSVD(特異値分解)を利用する必要があり、スケーラビリティに欠ける。また確率的な手法としてPLSI, LDAがあるが、これらは単語トピック確率行列を保持しておく必要があり単語数が大きいときにスケーラビリティに欠ける。

提案手法

今文章数をN、語彙数をM、トピック数をKと書く。このとき文章はM次元のベクトルdとして表される。このとき文章行列をD=[d_1,...,d_N]と書く。

また各トピックごとのM次元の単語ベクトルをuと書く(PLSIであれば各トピックにおける単語出現確率に相当)。単語トピック行列をU=[u_1,...,u_K]と書く。

ここで各文章ベクトルをu_iの線形和で近似する。すなわちd≒Σ v_k u_k。ここで文章nに関する係数ベクトルをv_nとし、トピック文章行列をV=[v_1, ... , v_N]と書く。

ここまでは既存手法も同様の定式化となっているがRLSIではこの先の制約条件が異なってくる。既存の手法であればuやvに関してLSIでは直交しているという制約を、PLSIやLDAであれば確率分布としての制約(非負かつ和が1)を入れている。

RLSIではu,vに関してL1,L2正則化を入れる。すなわち以下の目的関数を最小化する。

$\sum_{n=1}^N |d_n - Uv_n|^2_2 + \lambda_1 \sum_k |u_k|_1 + \lambda_2 \sum_n |v_n|_2^2$

ここでuに関してL1正則化を入れて、vに関してL2正則化を入れているのはトピック中の単語に関して可読性を高めることと情報検索への応用の際に実験的なパフォーマンスが向上するためである。

最適化手法

最適化に関してはNMFなどと同様にVを固定してUを最適化、Uを固定してVを最適化という処理を繰り返す。
更新式についてはVに関しては解析解がもとまり、Uに関してはcoordinate descentで最適化する。(詳細は[1]参照)

また並列化に関しては更新式の形が行列演算の繰り返しで書かれており、このような演算をmapreduceで効率化する方法はすでに知られている[3]。

さらに並列化時のプロセッサ数によらない部分をみるとLDAの並列化の場合は空間効率がO(MK)に対して、RLSIの場合はO(K^2)であり、語彙数が多くてもスケールする手法になっている。

他手法との関係

RLSIやPLSI,LSIにおいて最適化する式は以下のような一般の式でかける。
$\min_{(U,V)\in C} B(D || UV) + \lambda R(U,V)$

ここでCは制約条件、Bは何らかの距離尺度、Rは正則化項。LSIやPLSIは正則化項がなくて制約条件をつけた最適化を行うが、RLSIでは制約条件がなくて、代わりに正則化項が存在する。

またコンピュータビジョンの分野などでよく使われているSparse codingの手法はRLSIに近いが、スケーラビリティを考慮してない+応用先が異なる。

実験結果

文章検索においてBM25の値だけではなく、トピック空間での類似性も加味してランキングを行った時の精度(NDCG)を見た。また並列計算のフレームワークとしてはSCOPE[4]を用いた。

結果の要約としては

正則化の部分はUにL1,VにL2制約を入れたものがもっとも精度が高かった+解釈もしやすい
LSI,PLSI,LDAと比較するとRLSIが若干性能が高かった
大規模データ(単語数 7014881, 文章数 1562807, トピック数 500)に対してRLSIを適応して、MLR(LambdaRank[5])の特徴量に追加したところ有意な精度向上がみられた。

結論

トピックモデリングにおいてRLSIという、正則化項を使った手法を提案した。このような手法はComputer Visionとかでは類似のものがみられるが、トピックモデルに明確に適応したのは著者らが知るかぎり本論文が初である。

RLSIはMapredcueのような並列環境で効率的に実装でき、かつ既存のトピックモデルよりも情報検索に応用した時の精度が若干高いことを示した。

参考文献

[1] Regularized Latent Semantic Indexing, SIGIR 2011
[2] PLDA+: Parallel Latent Dirichlet Allocation with Data Placement and Pipeline Processing, TIST 2010
[3] Distributed Nonnegative Matrix Factorization for Web-Scale Dyadic Data Analysis on MapReduce, WWW 2010
[4] Scope: Easy and efficient parallel processing of massive data sets, VLDB 2008
[5] Learning to rank with nonsmooth cost functions, NIPS 2007