2012-08-08
WTIM 2: テキスト入力ワークショップが開催されます
2012年12月8日〜15日に開催されるCOLING 2012のワークショップとして、テキスト入力ワークショップ（Workshop on Advances in Text Input Methods; WTIM）が開催されます。告知サイト（英語）が公開されましたので、翻訳を行いました。
Second Workshop on Advances in Text Input Methods (WTIM 2) - Microsoft Research
概要
テキスト入力の技術は新しい時代に入りました。母国語の文字を直接タイプして入力できない地域では、コンピュータやモバイルデバイスを利用する人が急増しています。またキーボード以外の方法、例えば音声認識や手書き認識によってテキストを入力することも徐々に一般的になってきました。キーボードを利用する場合でも、数年前とは違った方法で行われます。適応的なソフトウェアキーボード、予測入力、スペル訂正はテキスト入力技術の最近の挑戦における僅かな例でしかありません。この挑戦は今やグローバルでユビキタスなものであり、言語やデバイスや状況を問わず、人々は新しい時代のテキスト入力技術を使わずに入力をしたいとは思いません。
多くのテキスト入力における挑戦は、共通のNLPの問題に直面しています。例えば、質の高い辞書が必要とされていますが、それをどう構築・維持するかはまったく自明ではありません。辞書はまた何らかのデータ構造に格納されますが、その最適な設計は利用方法に依存します。予測入力とスペル訂正はとても賢くなければ非常に迷惑なものになるでしょう。多くのアプリケーションにおいて、ユーザの入力には多くのノイズが含まれます（音声認識や小さなスクリーンでのタイピングを想像してください）。そのため入力メソッドはそのようなノイズに対して頑健でなければなりません。最後に、ユーザ入力体験の定量的な解析に必要な標準のデータセットや評価基準は今のところ存在していませんん。
このワークショップの目的は、世界中のテキスト入力技術に関わる研究者と開発者を集め、異なるアプリケーション・デバイス・モード・そして言語をまたがって新しい技術や研究で得た知見・問題点などを共有することです。私たちはこのワークショップを通してこの分野全体への理解が深まり、そしてそれぞれの応用分野において技術革新が促進されることを願っています。
このワークショップはIJCNLP 2011と共催で開催された第1回テキスト入力ワークショップ（WTIM 1）に続くものです。前回のワークショップにおける多くの反響を受け、私たちはWTIM 2を開催することに決めました。WTIM 2はWTIM 1と同じく世界中の入力メソッドに関わる開発者や研究者を一堂に会し、新技術や新発見、異なる応用やデバイスや言語を超えた問題点を共有することを目的としています。このワークショップがこの分野のさらなる理解とそれぞれのアプリケーション分野における技術革新を推進することを願います。
トピック
私たちはテキスト入力をカバーする広い範囲のトピックや言語における参加を歓迎します。興味のあるトピックは以下を含みます（ただしこれらに限定はされません）。
- 発音による入力：ローマ字を元にしない言語における変換に基づくアプローチ
- ソフトウェアキーボードや制約の大きいハードウェアにおける入力：携帯電話、ゲーム機、タブレットのための入力システム
- 新しい入力モードについての調査：音声、手書き文字、ジェスチャーによるテキスト入力
- 予測入力技術：自動補完や次の単語の予測、スペル訂正
- ユーザーのフィードバックやコミュニティに特有のデータ：ユーザーの理解や、より良い入力体験のための利用
- モデル：統計的な入力メソッドの研究と実践
- 評価：テキスト入力におけるユーザ体験を計測する尺度
- 商用の入力エンジン開発における諸問題：データ圧縮、クラウドベースのIME、ユーザーインターフェース設計
スケジュール
- 2012/9/30 (11:59pm Samoa time, UTC-11)：論文投稿締切
- 2012/10/31 論文採択通知
- 2012/11/15 カメラレディ（最終稿）の締切日
- 2012/12/8,9,15 ワークショップ当日（この日程のうち1日開催。詳しくは審議中）
投稿方法
本ワークショップ（WTIM 2）への論文投稿は * 2012年9月30日まで * にPDFで以下のURLから提出してください
The 24th International Conference on Computational Linguistics
投稿の方法はCOLINGの論文募集のページに従ってください。
LatexとWordのスタイルファイルが提供されています。
http://www.coling2012-iitb.org/doc/coling-latex.zip
http://www.coling2012-iitb.org/doc/coling-word.zip
形式はA5で、ロングペーパーは本文14ページ、ショートペーパーは本文6ページまでとなっています。
ちなみに、今回は私はオーガナイザとして名を連ねさせていただいています。前回はPC委員として査読を担当させていただきましたが、前回のオーガナイザだった鈴木久美さんから3月の言語処理学会のときにお話をいただきました。大役ですが頑張りたいと思いますので、よろしくお願いいたします。
テキスト入力のワークショップがあります #IJCNLP2011 - nokunoの日記
※この翻訳は非公式なものであり、正確な情報は公式サイトをご覧ください。
2012-04-09
NIPS2011読み会で発表しました #nipsreading
Fast and Accurate K-means for Large Datasets by @nokuno
Iterative Learning for Reliable Crowdsourcing Systems @shuyo
Why The Brain Separates Face Recognition From Object Recognition @takmin
Linear submodular bandits and their application to diversified retrieval @tsubosaka
The Kernel Beta Process by Mochihachi-san
- Latent Feature Model
- Indean Buffet Process
- Beta Process: Posterior?
- Bernoulli Process= IBT
HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent @sleepy_yoshi
Reconstructing Patterns of Information Discussion from Incomplete Observations @smly
2012-04-07
WSDM2012勉強会で発表しました #wsdm2012
@nokuno Finding Your Friends and Following Them to Where You Are(Best Paper)
@tsubosaka Finding the right consumer : Optimizing for conversion in display advertising campaigns
@y_benjo Overcoming browser cookie churn with clustering
Overcoming browser cookie churn with clustering in wsdm2012 reading
@smly When Will It Happen? – Relationship Prediction in Heterogeneous Information Networks他
Speaker Deck - Share Presentations without the Mess
@john_a_dreams Correlating financial time series with micro-blogging activity
WSDM2012勉強会 - Correlating Financial Time Series with Micro-Blogging...
@sleepy_yoshi
WSDM2012読み会: Learning to Rank with Multi-Aspect Relevance for Verti...
2012-03-31
x86/x64最適化勉強会3に参加・発表してきました #x86opti
というわけでバイナリアンに混じって発表してきました．
nokuno C++でMicro Thread / Fiber / Coroutineを実装してみた 〜 espを強引に入れ替える〜
久しぶりにゲーム開発の話をしました．楽しかった！
takehiro_t 分岐予測時代のswitch-case
if文は頻度の低いものから検査するほうが速い場合がある？
青木和麻呂 暗号実装最適化 − 暗号実装屋の不毛な戦い
Camellia暗号の開発者 @NTT
- LEA命令を使った最適化
- GCD（最大公約数）の最適化
herumi quick search algorithmとstrstr
- Quick Search: Simplified and Improved Boyer-Moore Algorithm
- テーブル不要，pcmpistri命令で高速化！
sinya8282 AVX2時代の正規表現マッチング 〜半群でぐんぐん！〜
w_o GCCの-mtuneは何やってるか(仮)
感想：闇の軍団怖い
2012-02-26
第9回自然言語処理勉強会＠東京を開催しました #TokyoNLP
TokyoNLPも第9回となり，息の長い勉強会になってきました．今回は飛び入りでLT発表枠もできて，アドリブ感あふれる回になったと思います．
座席表 by @synbooさん
第9回TokyoNLPの座席表 - sekicoco [セキココ]
Jubatusの分散レコメンデーション by @unnonounoさん
- 自己紹介
- Jubatusの紹介
- Jubatusの統計処理
- 正確な平均は「合計」と「個数」を内部状態として持っておけばオンラインで更新できる
- レコメンデーションとは？
- 近傍探索：類似度（コサイン類似度やJaccard係数など）の大きい k 件を返す
- 転置インデックス：疎行列と疎ベクトルの内積を高速・効率的に計算できる
- LSH (Locality Sensitive Hashing)：コサイン類似度に比例する確率でヒット
- MinHash：Jaccard係数に比例する確率でヒット
- 重み付きMinHash：重み付きJaccard係数
- アンカーグラフ：k-meansで求めたアンカーを介して類似度を計算
- Jubatusでの実装
- オンライン化：新しいデータの追加，変更，検索
- 分散化：Consistent Hashingで分散
- 転置インデックス：mixiのタイミングで差分を通知
- LSH：ハッシュ関数は不変なので，分散化は容易
- アンカーグラフの分散？→オリジナルデータを持たないと無理！
- まとめ
- Jubatusの紹介：MIX操作によるゆるい同期計算モデル
- レコメンドの手法
- Jubatusの実装
- 質疑応答
CountMinスケッチを実装してみた by @s5yataさん
groonga - Count-Min Sketch のライブラリを公開しました
Count-Min Sketch Library - Madoka
- 自己紹介
- 矢田晋
- 未来検索ブラジル
- 辞書検索ライブラリ：marisa-trie
- なぜ数えるのか？：文字，単語，N-gram，共起，…の頻度を数える
- メモリが足りなくなった場合の対処法
- 低頻度のアイテムを捨てる（カウントベース）
- ハッシュで頻度を数える（スケッチベース）
- 初めてのCount Min Sketch
- ハッシュ表：キー（アイテム）とバリュー（頻度）のペアの集合
- キーを持たない，ハッシュ表を複数持つ
- 最小の値を持つハッシュ表を使う
- パラメータ：depth, width
- トレードオフ：効率優先←→精度優先
- 誤差は増える方にしか出ない
- 続・初めてのCount Min Sketch
- 実装してみたら「つかえねーよこんなもん」
- メモリ使用量を固定できるのが強み
- マルチスレッド非対応（そもそも近似だし…）
- 欠点：アイテムを取り出せない
- 誤差を小さくする手法
- Conservative Update：最小値だけをインクリメントする（常に大きい方の誤差にならない）
- Lossy Conservative Update：低頻度アイテムの推定値を下げる
- Approximate Counting: 確率的にインクリメント
- Hierarchical CM Sketch: 低頻度，中頻度，高頻度のスケッチを用意する
- プログラミング CountMin Sketch
- ハッシュ関数：Murmur hashを使った（128ビット）
- パラメータ：depth >= 3 が実用的，width はユースケース次第
- Conservative Updateはそのまま採用，他は改良
- Lossy Conservative Updateはオプションとして提供
- Approximate Counting: 固定小数点数を採用（指数5ビット仮数14ビット）
- 余ったビットを使ってインクリメント禁止フラグを入れた
- 分岐なしで確率的インクリメント
- Hierarchical CM Sketch：パラメータが複雑，オプションとして提供
- 他の機能
- 内積を推定できる（スケッチを素性として使える）
- 分散してカウントおいて後で合成できる
- 拡大はできないが縮小はできる（割り切れる場合のみ）
- 評価してください
- Zipfの法則に従うアイテム列を自動生成
- 異なり数は1M，総数は14M
@conditionalさんによる紹介資料
Approximate Scalable Bounded Space Sketch for Large Data NLP
日本語入力を支える技術とMCMCについての基礎的な実験 @tkngさん
Amazon.co.jp： 日本語入力を支える技術 ~変わり続けるコンピュータと言葉の世界 (WEB+DB PRESS plus): 徳永 拓之: 本
- 日本語入力を支える技術について
- 制作の裏側を話します
- 社内セミナーで日本語入力の話をしたら技評の編集さんの目に止まった
- セミナーがGoogle日本語入力の公開と同日だった
- 2010年，IME関連の書籍を書かないかというお誘い（Web+DBに雑誌記事を書いた時の担当）
- モチベーション：日本語入力，機械学習，データ構造について書きたかった
- 執筆中：平日2時間，休日8時間のペース
- 2年間で22万字程度，細かい推敲で100万字くらい
- 書いてる最中を振り返って：辛かった，いいことは何もない
- 書き上がってからは：「もう書かなくていい」ことが嬉しい，買ったよっていう一言が嬉しい
- 執筆の道具：gitで原稿を管理，PDFを生成してページ数をカウント，校正ではdocdiff
- MCMCについて
- 確率とは
- サンプリングとは
- サイコロからのサンプリング→すぐに分かる
- 正規分布からのサンプリング→意外と難しい
- 棄却サンプリング：一様分布を棄却してつくる（提案分布は省略）
- MCMC
- 適当な初期値からランダムにちょっとずつ移動
- 移動先と移動元の確率比に応じて棄却する
- 確率が高くなる方向へは無条件で移動，確率が低い方向へはたまに移動
- 最初の方のサンプルは捨てるといい（burn-in）
- Rubyによる実際のコードで説明
- 他の手法
- メトロポリス法：今回紹介したもの
- メトロポリス・ヘイスティング法：移動に関して非対称な分布を使う
- ギブスサンプラー：多次元の分布をある次元（パラメータ）ごとにサンプリング
- Collapsed Gibbs Sampler: パラメータを積分消去して隠れ状態だけをサンプリング
- 実験結果
- MCMCで1次元の正規分布のサンプリング，ヒストグラムで可視化
- 100,000くらいで釣鐘型っぽくなる
- 考察
- 高次元のデータから効率的にサンプリングできる
- ベイズの定理と組み合わせると，パラメータをサンプリングできる
- データが与えられた元での確率の高いパラメータをサンプリングできる
- 参考文献：計算統計2
LT
- 人間言語判定・カタルーニャ語編 by @shuyo さん
- SIGIRにおけるLearning to Rank論文紹介 by @sleepy_yoshi さん
- Semi-Supervised Active Learning by @niam さん
- lang-8を使おう！ by @tomo_wbさん
- DSIRNLP #3へのお誘い by @overlastさん
- Erlangでminhashしてみた by @ajiyoshi さん
Introduction to Machine Transliteration by @nokuno
2012-02-19
第9回自然言語処理勉強会を開催します #TokyoNLP
下記要項に従い，次回TokyoNLPを2月25日（土）に開催します．参加される方はご登録をお願いします．
概要
自然言語処理（Natural Language Processing, NLP)に関する勉強会です。
理論と実践の両面から深く学び、発表と議論を通じて共有していくことを目的としています。
発表内容
第9回の発表内容です。今回もいつも通り濃い内容となっておりますので、気合を入れて勉強しましょう！
| 発表者 | 発表タイトル |
|---|---|
| ippei_ukaiさん | 機械翻訳ー自動評価と最適化、まとめ |
| unnonounoさん | Jubatusの新機能 〜リアルタイム分散レコメンデーション〜 |
| s5yataさん | Count-Min Sketch を実装してみた |
| tkngさん | 日本語入力を支える技術についてとMCMCについての基礎的な実験 |
| nokuno | Introduction to Machine Transliteration（仮） |
会場は渋谷のVOYAGE GROUPさんです．@ajiyoshiさん，いつもありがとうございます！
懇親会では@tkngさんによるIME本サイン会を行います．興味のある方はぜひお越しください．
Amazon.co.jp： 日本語入力を支える技術 ~変わり続けるコンピュータと言葉の世界 (WEB+DB PRESS plus): 徳永 拓之: 本
よろしくお願いします．
2012-02-08
「日本語入力を支える技術」本日発売！ #ステマ
id:tkngさんによる「日本語入力を支える技術」が本日2月8日に発売となりましたので，宣伝させて頂きます．
Amazon.co.jp： 日本語入力を支える技術 ~変わり続けるコンピュータと言葉の世界 (WEB+DB PRESS plus): 徳永 拓之: 本
今見たら，Amazonのコンピュータのベストセラーランキングで2位でした！ おめでとうございます！
追記：後日1位を獲得したようです．
ちなみにステマじゃないよ！ 堂々と宣伝って言ってるよ！ レビューしたからといって1円ももらってないけどね！
なお，まだ正式な告知はしていませんが，2月25日（土）に開催される第9回自然言語処理勉強会（TokyoNLP）ではid:tkngさんのサイン会が行われる予定です．興味の有る方は，書籍をお持ちになってお越しください．
2012-02-03
極大部分文字列の復習
極大部分文字列について復習しました．
極大部分文字列を使った twitter 言語判定(中谷 NLP2012) - Mi manca qualche giovedi`?
岡野原さんによる元論文はこちら．
http://www-tsujii.is.s.u-tokyo.ac.jp/~hillbig/papers/nl187_okanohara.pdf
極大部分文字列の定義については，id:n_shuyoさんのTokyoNLPでの発表資料で，論文と同様の説明がサンプル付きでされています．
#TokyoNLP で「∞-gram を使った短文言語判定」を発表しました - Mi manca qualche giovedi`?
ここでは，
- 部分文字列の間に，包含関係に基づく半順序関係を導入する
- この半順序関係における極大元を極大部分文字列と定義する
という定義の仕方をしていて非常にエレガントで分かりやすい…のですが，情報系が専門の人は「半順序」「極大元」あたりの用語を大学で習わなかった人もいるかもしれません（というか私がそうでした）．
半順序と極大元の定義に関してはWikipediaが分かりやすいのでオススメです．
今回の場合，部分文字列の間に包含関係がある場合は順序関係を定義できますが，包含関係がない場合は順序関係を定義できない（しない）ため，半順序となります．一般に半順序関係を持った集合では，その要素（元）より大きな要素が存在しないような要素が複数存在する可能性があり，これを極大元と呼びます．全順序（すべての要素間で順序関係が定義できる）だと極大元＝最大元で1つしかないわけですが，半順序だと極大元と最大元は必ずしも一致しない（極大元の集合に最大元が含まれる）ことに注意が必要です．
さて，半順序関係はループを持たないため，有向非循環グラフ（DAG）として図示することができ，これをハッセ図と呼びます．
極大部分文字列においてもハッセ図を描いたら分かりやすくなるんじゃないかと思い，描いてみました．
例として abrakadabra という文字列の半順序関係は以下のハッセ図で表され，各部分グラフの一番上の頂点が極大部分文字列となります．
この場合の極大部分文字列は {a, abra, abracadabra} となります．
頻度1の極大部分文字列は文字列全体となり，文書分類では特殊文字で連結した文字列を使うため素性として使われることはありません．また，拡張接尾辞配で抽出できるのも出現回数が2回以上の極大部分文字列となります．
id:n_shuyo さんのNLP2012論文を添削させていただいたりしていて，論文はこれでいいけど発表は図で例示できるといいなあと思って作ってみました．変なところがあったら教えて頂ければ幸いです．
追記：ab→abraのような，2文字スキップするリンクも必要でしたね．
2012-02-02
mixi Engineers' Seminar #3 に参加しました #mixi_engineers
mixi Engineers’ Seminar #3 : ATND
機械学習の基礎と評判分析 by 高村大也
- 自己紹介
- 東工大のすずかけ台キャンパスにいます！
- 「すずかけ台には良い教授がたくさんいる」はポジティブと評判分析
- 著書：Amazon.co.jp： 言語処理のための機械学習入門 (自然言語処理シリーズ): 高村 大也, 奥村 学: 本
- 概要
- コンテンツを入手→前処理→分類器→出力
- 前処理：形態素解析→品詞フィルタ，ストップワード削除
- 「すずかけ台には良い教授がたくさんいる」→すずかけ台 良い 教授 たくさん
- 分類器
- ポジティブかネガティブか
- ナイーブベイズ分類器
- 確率的生成モデル
- 140文字制限は無視
- ツイートの長さを決める（単語数）
- ポジティブかネガティブか決める
- 単語を選ぶ作業を長さ分だけ繰り返す
- P(ツイート，ポジ) > P(ツイート，ネガ) ならポジティブ，逆ならネガティブ
- パラメータを決める
- 訓練データから推定
- 尤度関数が最大になるようにパラメータを決定
- 最尤推定ではゼロ頻度問題が発生するので，スムージングが必要
- 加算スムージングはディリクレ分布を事前分布とするMAP推定の一種
- 対数線形モデル
- 色々な素性を取り込みたい（長さ，ユーザIDなど）
- 線形分類器（SVMなど）
- 指数関数で正に変形してから割合を取る
- より汎用的な素性関数による表現を使う
- パラメータを決める
- 対数線形モデルで識別学習を行なう
- 閉形式で求まらないのでSGDなどを使う
- ナイーブベイズと対数線形モデルを比べると，後者は訓練は遅いが分類精度は良い
- 正則化項の説明はスキップ
- 条件付き確率場(CRF)
- 同じ極性の連続するツイートを抽出したい
- ポジネガの列のあらゆる組合せについて足し合わせるには指数オーダーの計算量が必要
- 計算量を減らすために，隣り合った2ツイートのみから素性関数を設計する
- 隣り合ったツイートだけでも，同じ極性が連続しやすいという特性は表現できる
- CRFの応用：形態素解析，固有名詞抽出
- 中川モデル
- Dependency Tree-based Sentiment Classification using CRFs with Hidden Variables
- HLT-ACL 2010
- NICTの評判分析システムWISDOMに搭載
- 二重否定（よくなくないわけではない，など）をうまく捉えたモデル
- 係り受け解析：「人々の，利益が，減る，ことを，すずかけ台の，言語処理技術が，防いだ」
- 前向き後ろ向きアルゴリズムは使えない→確率伝搬法で解決
- 周辺化を行って隠れ変数を消去
- 評判分析とその他の話題
- 訓練データの作成をサボる方法：ドメイン適応，能動学習
- ポジネガ判定だけでなく意見全体を概観：クラスタリング，評判要約
推薦システムのアルゴリズム by 神嶋さん
資料：http://www.kamishima.net/archive/recsys.pdf
- 推薦システムの概要
- 動機：「100万人の顧客がいたら，100万人の店舗を作れ」by ジェフ・ベゾス（Amazon CEO）
- 手法：協調フィルタリング v.s. 内容ベース
- 問題設定：明示的 v.s. 暗黙的評価
- メモリベース法
- user-user similarity
- item-item similarity
- ステマに弱いのでメモリベース法が有利
- モデルベース法
- 行列分解：勾配降下法で損失関数を最小化
- 確率モデル
- 履歴条件型：ベイジアンネットで因子を簡略化
- 共起型：pLSA，潜在変数
- Google News Personalization
- 推薦システム研究の話題
- ソーシャルグラフによる推薦
- サクラ攻撃対策
- プライバシー対策
- バンディット問題
- 推薦理由の提示
- セレンディピティ（新規性）・ダイバーシティ（多様性）
Big Data Analysis at mixi by 石川有
- たんぽぽグループ解析チーム
- 解析ツール：HadoopとR
2012-01-31
第3回入門ソーシャルデータ勉強会に参加しました #social_data
第3回入門ソーシャルデータ勉強会に参加しました．
第3回「入門 ソーシャルデータ」真面目に勉強する会 @神泉(渋谷) : ATND
IT勉強会カレンダーをきっかけにこの勉強会を知り，自分の監訳した本が読まれていて嬉しく思いました．
入門 ソーシャルデータ ―データマイニング、分析、可視化のテクニック
また，始まる前に同じビルの同じフロアでスタートアップのシェアオフィスであるBOATを見学しました．
BOAT by VOYAGE GROUP - 渋谷のフリーシェアオフィス
BOATでは，未踏時代の知り合いの斎藤さんが共同創業者をやっているgrowbuttonというサービスの会社とお話をしました．
いわゆるイイネ！ボタン系のサービスですが，FacebookのLikeボタンなどと違い，ボタンを押すごとに1ドルをそのサイトに寄付することができるというサービスで，とても面白いと思いました．
以下，勉強会のメモです．今回は3章 古き良きメールボックスをやりました．
http://zaffra.com/static/matthew/enron.mbox.json.gz
- enronデータセットのダウンロード
- mbox形式からjson形式へ変換
- CouchDBを利用した頻度分析
- 自分のメールデータの分析
演習時間中はTopCoder SRM 531に参戦してました．すみません＞＜