メニュー

技術ブログ

Denso IT Lab.社員による技術情報の紹介

Denso IT Laboratory researcher's blog sites

数式

RSS

ページトップへ

SIGIR2013

日曜日にあったSIGIR2013勉強会で Retrieval Models and Ranking I のセクションを担当しました.
全部はさすがに読めていませんが...


その他の論文紹介は担当者の皆さんが以下にアップされています.
http://www.kde.cs.tsukuba.ac.jp/dbreading/?SIGIR2013

このエントリーをはてなブックマークに追加

「第4回 データ構造と情報検索と言語処理勉強会」聴講

昨日、渋谷のVOYAGE GROUPさんのセミナールームで「第4回 データ構造と情報検索と言語処理勉強会」があり、初めて聴講しました。日頃、気になっているけど、自分で勉強する時間がない、という内容の発表がいくつもあり、とても参考になりました。

VOYAGE GROUPさんのオフィスのデザインは、非常に斬新で、楽しいムードを作っていて、創造性が高まりそうだと思いました。

今回、10件の発表がありました。全体の司会は、LINEでブログ開発をされているという@overlastさんがされていました。発表も予定されていましたが、マシントラブルの為、懇親会でのLTになったのですが、今回、懇親会には参加できなかったので、話を聴くことができず、残念でした。

1件目は、@torotokiさんが、Scalaの初歩とその自然言語処理ライブラリScalaNLPについて解説してくれました。Scalaは、JVM上で動く関数型言語ということで、個人的にJava好きの私にとっては、非常に興味を感じています。@torotokiさんは、高校生ということで、社会人の方々の前で、堂々と話をされていて凄いと思いました。

2件目は、@shuyoさんが、Active learning(能動学習)に関する入門を、Settlesさんの解説を元に、ベンチマークデータで実行した結果を使って解説してくれました。アノテーションは高コストであり、半教師付き学習が必要であるが、クラウドサービスでドメイン知識に必ずしも精通している訳ではないユーザが効果的に学習データ作成するのが難しい。そこで、能動学習が良いだろうという考え方とのことでした。教師データを作って欲しいデータのクエリ方法は色々とあるが、意外にランダム選択とあまり大差がないという印象でした。但し、教師データを Information density(シンプルにはデータの密度) が高い所から選択すると、効果大きいということでした。また、複数の識別器でアンサンブル学習することの寄与も大きいという感じでした。

3件目は、@maropuさんによる不動小数点列の圧縮という話題です。浮動小数点列の圧縮というのは、数値計算系では一般的らしいが、この分野ではあまり馴染みがないということでした。こういう話題を話す方を見ると、「職人」だな、という印象を持ちます。余談で、浮動小数点の積とかは可換ではない、という小話があり、面白いと思いました。ちなみに、私は前職で地図システム関係の仕事をしていたのですが、地図データでは、ラインストリングやポリゴンデータに、この手の圧縮手法を使っていたな、ということを思い出しました。

4件目は、@slaさんが、SIGKDDでのBest Paperになったという行列スケッチの話を紹介されました。この手法を使うことで、高次元のPCAなどの計算で、次元を非常に低減してから計算できるので、高速になるということでした。所謂、低ランク近似の話かと思いましたが、A*A^Tのような形の計算に限定されているようでした。実装が非常にシンプルで、これは自分も利用してみようと思いました。

5件目は、@Phylloさんが、WFSTの入門について解説されました。転置インデックスとかもWFSTで表現することができるということでした。WFSTは合成することが可能で、合成すると複数のWFSTの計算を一度に出来てしまうので、高速に処理できるようになるということでした。WFSTは、個人的にも今後、勉強したいと思っています。

6件目は、@s5yataさんのダブル配列の豆知識というお題でした。大学でもダブル配列を研究されていたそうですが、これまでに少なく見積もっても10回以上はダブル配列を実装した経験を持たれているということで、一体、どんな人生を歩むと、10回もダブル配列を実装するのか、とtwitteerで話題となっており、面白いと思いました。私は一度も自分で実装したことはありませんが、実装する必要がある人には目から鱗の話だったのだろうと思います。

7件目は、@kumagiさんによるJubatusでのK-NNを高速に処理するために、Locality sensitive hashingを利用する方法について解説されました。詳細はコンフィデンシャルということでしたので、省略します。

8件目は、@shuya_mさんが、口コミマーケティングで、K枚のチケットを効率良く分配するための問題で、劣モジュラ関数が出て来るという話をされました。Kempeさんという方の仕事がベースになっているようでした。この問題での目的関数が劣モジュラ関数になっているとのことでした。ポイントは劣モジュラー関数では、貪欲法でも63%以上の精度(スコアの値が最適値の0.63倍以上)で最適解が求まるということでした。劣モジュラー関数で目的関数が書けていると非常に便利ですね。

9件目は、@just_do_nextさんによるsnowflakeというtwitter社が開発したID生成器(OSSとして公開)を元にID生成のテクニックについて解説されました。ID生成で、良くあるのが数値カウントアップであるが、この方法はスケールしない。一方、UUID RFC4122 の 128bit は大き過ぎる。そこで、snowflakeでは、64bitのlongで表現し、タイムスタンプ(41bit。これで69年は大丈夫らしい)・マシンId・シーケンス番号から生成するとのことでした。このようなID生成の利点は、idだけから時間でソートできること、整数値の圧縮手法を利用可能などがあり、欠点としてはOS時刻のズレに弱い、Thrift経由で生成しないといけない(分かる!)ということでした。@just_do_nextさんご自身は、shakeflakeを開発されているということでした。

10件目は、@komiya_atsushiさんによるレコメンドにおける類似度計算の傾向と対策という話題でした。アイテムベースレコメンデーションで、類似度計算を空間的時間的に最適化したいということでした。ここでも、商品属性と購買ログから作られる特徴ベクトルに対するK近傍探索が使われていました。類似度には、Jaccard係数を使う場合が考えられていました。この計算は、比較的重く、工夫が必要で、(1)ナイーブな方法(bit列化、popcountで効率化)、(2)マージアルゴリズム的にベクトルを走査、(3)転置インデックス、(4)バスケット分析(アソシエーション分析)、(おまけ)b-bit min-wise hashing(近似的な特徴ベクトルに落として計算)という手法を紹介されました。MovieLensのデータ(10M)でそれぞれの方法を比較され、転置インデックス、バスケット分析が速いということでした。ナイーブ法も実装の単純さを考えるとまあまあということでした。

このように、聴講した内容とまとめてみると、濃い内容の話ばかりであったと改めて思いました。ありがとうございます。講師陣の方々、運営の方々、ご苦労様でした。

このエントリーをはてなブックマークに追加

ICDE2013勉強会参加報告

DB及びIR系の研究者で構成される勉強会(DBREADING)においてICDE2013勉強会が開催されたので、参加、発表してきました。

  • ICDE勉強会 [http://www.kde.cs.tsukuba.ac.jp/dbreading/?ICDE2013]
  • ICDE2013 [http://www.icde2013.org/]

■学会の概要
まず、ICDEに関して簡単に説明させていただくと、ICDEとはデータベース系のトップカンファレンスのうちの一つであり、かなり実装寄りの学会とされています。また、産業系の論文も数多く投稿されるのがこの学会の特徴です。
論文の採択率はかなり低く例年20%程度とかなりハイレベルな競争が繰り広げられています。なお、今年度の論文採択率は以下の通りとのことです。

  • 研究論文95 / 443 = 21.4%
  • インダストリアル論文 8 / 20 = 40.0%
  • デモ 27 / 69 = 39.1%

今年は例年と比較して、Spatial Databases系の論文が多く投稿されたことが特徴的でした。また、最近の傾向通り、分散処理系のデータベースの精度向上、信頼性向上に関する研究は多くの発表があった一方で数年前のホットトピックであったxml系の研究は縮小気味の様子です。
なお、今年度のBest Paper Awardは

  • Crowdsourced Enumeration Queries(クラウドソーシングによる解答における母集団の推定に生物統計学の固有種数推定を応用)
  • T‐Share: A Large‐Scale Dynamic Taxi Ridesharing Service(タクシーのライドシェアに関する論文。タクシーのリアルタイムに計算するため時空間索引を事前計算)

でした。

■紹介論文
勉強会ではセッション「Social Media II」で発表された論文の紹介をしてきました。

 

 紹介した論文の内容は以下の通りです。

  1. A Unified Model for Stable and Temporal Topic Detection from Social Media Data
    ソーシャルメディアにおけるコンテンツが一時的なトピックかそれとも恒久的なトピックかを考慮した上でトピック判定を実施
    【内容】
    twitter等のユーザからの発信されるメディアについては、いつも言及されているような話題、例えば犬やペット等の定番の話題の他に実世界のイベント、例えば有名人の死去や選挙等、実時間に左右されるようなものがあるとのこと。これらを考慮した上でのトピック分類モデルを作成した、というのが本論文のコントリビューションです。
    【感想】
    提案されているモデルが結構簡単な割に効果が高い、というのが正直な感想です。あと、行動推定タスク等において、イリーガルな行動が入るようなケースにおいての応用ができそう。
  2. Crowdsourced Enumeration Queries (Best Paper)
    クラウドソーシングの検索タスクに対する回答集合数(母集団)の推定.
    生物統計学における固有種数の推定手法を応用(CHAO92)
    【概要】
    クラウドソースを利用した検索タスク、例えば、世の中にあるアイスクリームの味の全てを集めてくる、ある地域の地名を全て集める等のタスクを実行しようとした場合を考えると、
    通常のデータベースにおける検索においては、データベースの中にあるデータが全て、であると仮定することができることから、該当する結果の数は容易に見積もる事ができます。
    一方で、クラウドソースを利用した検索タスクにおいては、母集団がwebやクラウドワーカーの知識の中に存在することになることになり、該当する結果の数は推定することが大変難しいのですが、
    同課題に対して、生物群集学における個体数の推定手法(CHAO92)を応用した手法を提案。具体的には、クラウドタスクにおけるストーキング(すべての解を一人でやってしまうようなワーカ)への対策を実施した手法であるStreaker-tolerant Estimatorを提案しています。
  3. 【感想】
    論文の内容はICDEでベストペーパーを取ったということもあり大変おもしろい。
    疑問としては、そもそも個体数の推定手法は、CHAO92が提案されて以降、CHAO92の課題(サンプル数が少ない場合、母集団の推定数がかなり大きめの値になってしまう、)等の欠点を解決するために、いろいろ新しい方法が提案されているとのこと(e.g. ACE等)。
    同課題はクラウドタスクでも共通する課題であることから、なぜに他の手法を使わずCHAO92を適用したのかがよくわからなかった。
    あと、今回の手法は、種(解答)数の推定であり、種の分布は一切考慮していない。当然生物分類学においては、種の分布に対する推定手法も存在し、またクラウドタスクにおいても、回答数の予測に対するニーズも存在することから、今後同課題に対する研究も進むのかなあ、と感もありました。
  4. On Incentive-based Tagging
    tag情報の品質をインセンティブをワーカー与えることによって向上させる。
    【概要】
    urlや写真等に付与されているタグを解析して、品質の悪いタグやタグが付与されていないものを優先的にタグ付与することによって全体の品質を向上することができました、という論文。
    【感想】
    クラウドタスクにおけるタスク割り当て戦略、に関する論文。最近はやり。クラウドタスクにおけるタスク割り当て戦略に関する研究は当然必要だろうな、とは思うんだけど、ただ、この論文の課題設定と解決手法は微妙。。そんなん当たり前じゃん、というのが正直な感想。

■その他気になった論文

  1. T-Share: A Large-Scale Dynamic Taxi Ridesharing Service
    タクシーのRideShareのための動的クエリとスケージューリングのためのアルゴリズムの提案です。新しい利用客がクエリしたとき,既に割り当てられたスケジュールを破らずに,最低限の距離の追加でそのクエリを満たすタクシーを発見する。高速化処理のため、事前計算した時空間インデックスの利用しています。
  2. CPU and Cache Efficient Management of Memory-Resident Databases
    主記憶DBのPartially Decomposed Storage Modelにおけるデータアクセス手法において、JITを利用することによって高速化できました、という論文です。
このエントリーをはてなブックマークに追加