Infrastructure 2

研究

というわけで，Infrastructure 2 に出た．聴衆は10-20人！人気ナーイ．4つも Session がある Social Network にでも行っているのかな．二つ目は MS のインターンでやった話だと言っていた（一つ目も多分そう）．

  • A Pattern Tree-based Approach to Learning URL Normalization Rules
  • 0-Cost Semisupervised Bot Detection for Search Engines
  • CETR - Content Extraction via Tag Ratios

一つ目の発表は，同一内容のページ (duplicated URLs) を見つけるタスクを URL の情報のみで解いたという話．普通にやる場合，内容をハッシュ値にして比較したりするのだけど，計算が重いので URL の比較でサラリと解く．具体的には，URL のパターンの包含関係を木構造で表現して，duplicate nodes を検出するというアプローチをとる．パターンを詳細化する場合には，より頻出する key (URL の / で segment された各要素を key とみなす) を一段ずつ詳細化する．部分木全体で対応をとるので計算の削減と圧縮率の向上が見込める．細かいヒューリスティクスが色々とあるので見た目ほど綺麗な手法ではないようだ．質問では，ホストが違っても重複を検出出来るのかという話や（できる），パターン木の更新はどれぐらいの頻度でやるのかという話（3ヶ月ぐらい）が出ていた．
二つ目は，search engine で query を投げまくる bot をどうやって検出するか，という話で，肝は，Captcha に対する反応をみて教師データを作る（正解-> 人間; 無反応-> bot）という点と，教師データの偏り (bias) をBayesian network structure learning の文脈で unlabeled data を用いることで回避するという点の二つ．素性は一定時間のクリック率や，クエリ頻度や IP の偏りなどで，教師データのみを用いて決定木で分類器を使う場合に比べて，二倍以上の精度が出るとの報告．手法の詳細までは完全には理解できなかった．
三つ目は，HTML 文書から内容部を抜き出す手法の提案．手法は非常にシンプルで，HTML 文書の各行でテキストの文字数 (x) とタグの数 (y) で比率 (text-to-tag ratio, TTR) をとって（y = 0 のときは x, y > 0 のときは x / y），そのヒストグラムからテキスト部を抜き出すというもの．単純な閾値ベースの手法と，k-means (k=3 で原点に一番近いクラスタを非内容部とする), さらに前後の数行からの変化量を考慮した二次元空間のクラスタリングを試して，最後の手法が一番良かったと報告している（が，最初の閾値の手法でも既存手法より全然高精度）．既存手法では VIPS などがあるのだが，提案手法は超シンプルな上最高精度を達成しているので使い勝手は良さそうだ．質問は，他の手法と組合せたりしないのか？とか，タグの構造等は考慮しないのか？などがあった．査読結果では，一人は "too simple"，もう一人は "really simple" というコメントだったそう．この手の手法のデファクトスタンダードになるかもしれない．
Web 系の基礎技術では，simple かつ scalability, robustness が高いというのが重要だなと実感．