tsubosakaの日記

Topcoder系の記事はTopCoder部の方に書いていきます.
twitterアカウント: http://twitter.com/tsubosaka

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件の文章を取ってくる手法について、知ってる範囲でまとめてみました。

この辺の話は教科書だと

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

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

の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を使って列挙する形になります。