yoriyukiの日記 このページをアンテナに追加 RSSフィード

2012-04-29

Blogspotに移転 Blogspotに移転を含むブックマーク

特に大した理由はないのだけれど、Bloggerに移転することにした。

http://yoriyuki-jp.blogspot.jp

よろしくお願いします。

トラックバック - http://d.hatena.ne.jp/yoriyuki/20120429

2010-12-27

[コンピュータ][真字]IM飲み会2010 2010/12/26  [コンピュータ][真字]IM飲み会2010 2010/12/26を含むブックマーク

IM飲み会2010 2010/12/26

IM飲み会で取ったノートを公開する。間違いや公表して都合が悪いところなどがあればご連絡下さい。

ハッシュタグ #ime2010 ← 大きく出た。

(MSが)IMEにしたのはInstant Messengerがあるから。

Mac率高し。あとLenovo。Let's Noteは…

小町さん:言語処理学会2011で話すネタについて

奈良先端+Apple(ソフトウェアエンジニア入力メソッド開発)

京都テキストコーパス:毎日新聞

日本YAHOO勤続年数2年くらい

アメリカは1年くらい。給料はすぐに首になるので同じくらい?

医療情報系の比較

医療は実務研修重要修士→実務経験→博士

情報系ではそれが制度として存在しない。1DAYインターシップくらい2か月、9

か月の大学が出てきた。博士前期課程修士論文が書ければそのまま博士課程

に。

情報系での実務系の経験を積む必要あり。

豊橋技術科学大学で話す予定。自然言語処理における企業大学学生の関係

就活エリートの迷走」

3年で辞めるのは長い!

携帯端末のIME事情

iPadに50音キーボード

あかさたなの並びが普通と反対!

常に予測モードを使っている。シングルベストだけでは駄目。変な候補を出す

ユーザーが気持ち悪がる。

ソフトウェアキーボードなら随時変更可。

前の字でキーの認識範囲を変えている。←姑息

スペルチェックは単語単位やっている。文脈はまだできてない。

リソースが厳しい。

iPhone 3GS <=> iMac G4 (2002)

iPhone4 <=> iMac G5 (2004)

昔の小技が復権している。

携帯端末デスクトップで同じコードベースを使いたい

携帯端末:新しいことに挑戦できる

デスクトップ:レガシーコード辞書メンテ

☆ 国際化時代の入力メソッド

エンジンの多言語対応(中国語) - Appleでやろうとしている。日本人が来ない。

言語学習者支援(日本語母語にしていない人対応)

中国日記

NLP2011 日本語入力における自然言語処理

Lang-8

水本さん − Lang-8データを使った誤り訂正

甲南大学:チャンツ(リズム)の推定。単語列からHMMによりストレスの位置を推定する。

HRI:音声

NAIST:不自然言語処理

機械翻訳データとしてLang-8(間違った文と正しい文の対)を使う。

LANG-8:相互添削SNSサイト
誤り訂正における問題点

単語単位の訂正じゃない。→形態素解析ができない

文字単位で訂正

文字−文字訂正

文字−単語訂正

#機械学習翻訳をするのってそもそもどうするんだろう?言語モデル翻訳

#モデルがあるらしいが。

訓練データからいろいろゴミを除かなくてはいけない。添削でOKと答えている

時とか。

質疑応答

☆ 評価に関する問題

評価が難しい。50文選んで完全一致で評価している。

コメント:誤りがない文もテストデータに入れたほうがいい。←入れている。

評価尺度:Blue

Lang-8言語分布

ユーザー数:英語

文章:日本語

大規模データを用いた統計日本語校正

笠原さん

Mixi社長ではありません。

Word日本語校正はあまり良くない。道へ迷う

助詞の誤り、コロケーションの誤りが多い。

私はご飯を好きです

猫が吠える

手法

n-gramを使う。(トライグラム) Google n-gramを使う。

頻度の低いn-gramが出てきたら誤りとみなす。

http://cl.naist.jp/chantokun/

Noisy-channelモデル

負例のデータベースを使う。

argmax P(正) P(誤|正)

を最大化する。P(正) P(誤|正) は独立。

ALAGIN : コロケーションデータ

比較

Just Write

なつめ

Lingo Project

質疑応答

頻度の線引きは、その格助詞の出現頻度を反映している?→していない

名前。アプリケーションの名前は「ちゃ」から始める習慣

誤りの理由は?例文が出せたらよい。

メモリの使用量は? データは展開したら100G

系列ラベリングとして扱うよりは、木へのラベリングとして扱った方がよい。

対応する用言が離れた位置にあるときには?

助詞がNULLの時は?対応していない。

ロケーションも結果的にサポートしている。

西山さんとよもやま話

AZIK拡張ローマ字 SKKを使う人がよく使っている。

変換ログを用いた仮名漢字変換精度の向上

変換ログコーパスに使う。←よみと区切りが付いたコーパスとして扱う。

言語モデルはbigram

森さん2007 - 単語分割、読み推定とか

ユーザーモデル

何でも確定する人(雑な人) system

必ず修正する人(慎重な人) oracle

orcaleの場合にはかなり変換精度が向上する。

質疑応答

ETR:新聞、?

ダメになる例は?ある。

仮名漢字変換の古い論文を探してみた

徳永さん

Get Wild!を流すと何でも感動的に聞こえる

uim

ChaIME

趣味カレーを食べること。

目的:日本語入力歴史を知りたい

JW-10

研究1960年代に遡る。

検索は雑誌タイトルで検索するべし(ゆとり向けのアドバイス)

大学図書館サラリーマンむけでない。

国会図書館はすばらしい!研究目的ですといえばコピー可。

東大図書館卒業生は使えるがコピー出来ない。

プロシーディングは各著者の部分が一つとして考えられるので、論文が半分し

コピー出来ない。

国会図書館の使い方

OPACで知りたい本を調べて、閲覧を申し込む

カウンターに本をとりに行く

勝手コピーを取れない。複写依頼を書く

登録利用者カードを作れば、ネット上で文献複写依頼も可能。

☆ 見つかった論文から分かったこと

入力への応用は考えられていなかった。

カタカナで送られてきたデータ自動的に日本語に直す。

ラインエディタすらなかった時代。

入力は人で形態素に区切るのが前提。べた書きは不可能と書かれている。

☆ まとめ

インターネットで見つからない古い論文図書館でチェックしよう

Sekka誕生秘話

Kiyokaさん

better SKK開発への挑戦

デモ

アーキテクチャ
Sekka ←(curl) REST API - Sekka server - memcached
                              |
                          Tokyo Cabinet
                              |
			  SKKの辞書
表の動機

SKKを見直した。単文節で確定、文節区切りは間違わない。

SKKでモードをなくしたい。リアルタイムフィードバック曖昧辞書

裏の動機

Nendoのベンチマーク

GemsでRubyライブラリーを使うことにより生産性が向上する。

Nendo 90%,ruby 10%

変換

Kanji → 漢字

Modoモード

kanJi → 感じ

kanji → かんじ

カーソル直前のローマ字をCtrl-Jでいきなり確定

Ctrl-Jで候補選択に入る

辞書あいまい検索

Jaro-Winkler編集距離。最初の文字ほど間違いの判定が厳しい。

辞書のキーはローマ字表記ゆれもある閾値のものをすべて展開してキーとして

いれている。

辞書500M オンメモリ

マルチユーザー対応
質疑応答

あいまい検索はキーボード対応しているのか?してない。zshがそうしてい

る。どっかのスマートフォンとか。

前方一致検索-Key value store 最初の2文字だけ使っている?ボトルネックじゃ

ない。岡崎なおゆきさんのsimstream(?)を使うとよい。

小指が痛くなる問題:スティッキーシフトを使う。sekka.elで対応している。

SKK vs 最先端IME 論争

SKK陣営の意見

小脳がSKKに最適化されているのでこれでいいわ。

最先端IME陣営の意見

自然言語処理研究者がSKKを使うのは欺瞞だと思う。

INPUT METHOD 10大ニュース

田端さん

mozc vs anthy 10本勝負

辞書職人 vs Web検索インデックス

65byte/word vs 10bytes/word

C vs C++ OS依存のAPI Googleライブラリ

あちこちで動く vs デスクトップ

...

今年の10大ニュース

IM飲み会

2002年頃から

1.Mozcがオープンソースに(巨大なパイプラインの一部。それは公開できないか

ら誰か作ってほしい。)

2.Sekka登場

3.BLEU:性能評価のmetric wikipediaを見よ。複数の正解があるときにその違

いを数値化。複数の正解を用意するのが大変?

LCS:編集距離

4.コスト推定の重要さが知られる。語彙数を増やすとBLUEスコアが落ちる。

5.辞書職人統計的手法のギャップが鮮明になる

2chスレの雰囲気は-年前と変わらないね。

6.ソフトウェア配布形態の変化

ディストリビューター経由はオーバーヘッドがある

開発者と利用者が直結するスタイルに。app-store。自動アップデート

7.Chrome OSの開発が進む

IMEフレームワークはibus

8.XIIIMFとかXIMとか途絶

9.言語処理学会日本語入力セッション

10.いろいろ

Anthyメンテナンスが…

懇親会で出た話

LANG-8社長の喜さんから中国文化や起業にまつわる話を伺った。

国際熱核融合実験炉イータの裏話。

Sekkaをインストールするのはなかなか難しい。TokyoCabinetを(ライセンス

都合で)使っている問題

Androidの開発環境Ubuntu

2010-12-06

[][]相変わらず… 相変わらず…を含むブックマーク

もうかれこれ1月以上Coqやっている割には進んでいない。今度はAVLの平衡を保つ操作定義する関数balを定義しようとしてつまづいている。

近所でCoqやっている人がいればいいんだけどね。


Definition comp_height h1 h2 := 1 + max h1 h2.

Definition balanced_height h1 h2 : Prop := h1 = h2 \/ h1 = h2 + 1 \/ h1 = h2 - 1.

Inductive avl_tree_h : nat -> Set :=
  | Empty : avl_tree_h  0
  | Node  {h1 : nat} {h2 : nat} : balanced_height h1 h2 ->
    avl_tree_h h1 -> A -> avl_tree_h h2 -> avl_tree_h (comp_height h1 h2).

Definition avl_tree : Set := {h : nat & avl_tree_h h}.

Definition destruct_tree_spec (tuple : avl_tree * A * avl_tree) (t : avl_tree) : Prop. 
refine(fun tuple t =>
  let (head, r) := tuple in
  let (l, v) := head in
  exists x : balanced_height (height l) (height r),
  t = create l v r x
  ).
Defined.

Definition destruct_tree (tree : {t : avl_tree | is_non_Empty t}) 
  : {tuple : avl_tree * A * avl_tree | destruct_tree_spec tuple (projT1 tree)}.
intros.
destruct tree.
destruct x.
destruct a.
unfold is_non_Empty in i.
unfold is_Empty in i.
elim i.
trivial.
apply (exist _ ((inj a1), a2, (inj a3))).
unfold destruct_tree_spec.
apply (ex_intro _ b).
unfold projT1.
unfold sigT_of_sig.
unfold create.
f_equal.
Defined.

Definition destruct_tree_spec (tuple : avl_tree * A * avl_tree) (t : avl_tree) : Prop. 
refine(fun tuple t =>
  let (head, r) := tuple in
  let (l, v) := head in
  exists x : balanced_height (height l) (height r),
  t = create l v r x
  ).
Defined.

Definition destruct_tree (tree : {t : avl_tree | is_non_Empty t}) 
  : {tuple : avl_tree * A * avl_tree | destruct_tree_spec tuple (projT1 tree)}.
intros.
destruct tree.
destruct x.
destruct a.
unfold is_non_Empty in i.
unfold is_Empty in i.
elim i.
trivial.
apply (exist _ ((inj a1), a2, (inj a3))).
unfold destruct_tree_spec.
apply (ex_intro _ b).
unfold projT1.
unfold sigT_of_sig.
unfold create.
f_equal.
Defined.

Definition bal_hyp h1 h2 := (h1 - 2 <= h2) /\ (h1 + 2 >= h2).

Definition bal (l : avl_tree) (v : A) (r : avl_tree)
  (H : bal_hyp (height l) (height r)) : avl_tree.
refine (fun l v r H =>
  match le_dec (height r + 2) (height l) with
    | left _ => 
      match destruct_tree (existT _ l _) with
        | exist (pair (pair ll lv) lr) _ =>
        match le_dec (height lr) (height ll) with 
          | left _ =>
            create ll lv (create lr v r _) _
          | right _ =>
            match destruct_tree (existT _ lr _) with
              | exist (pair (pair lrl lrv) lrr) _ =>
              create (create ll lv lrl _) lrv (create lrr v r _) _ 
            end
        end
      end
    | right _ =>
      match le_dec (height l + 2) (height r) with
         | left _ =>
           match destruct_tree (existT _ r _) with
             | exist (pair (pair rl rv) rr) _ =>
               match le_dec (height rr) (height rl) with
                 | left _ => create (create l v rl _) rv rr _
                 | right _ =>
                   match destruct_tree (existT _ rl _) with
                     | exist (pair (pair rll rlv) rlr) _ =>
                         create (create l v rll _) rlv (create rlr rv rr _) _
                   end
               end    
           end             
        | right _ => create l v r _ 
      end
  end).

とやって生成されるゴールを証明すればOK…みたいに考えていたんだけど、どうも例えばllがlの部分木であるとか言った情報をゴールを証明する前提に付けてくれないので、どうやっても証明ができないのであった。

トラックバック - http://d.hatena.ne.jp/yoriyuki/20101206

2010-11-01

[][]CoqでAVL木の検証をするII CoqでAVL木の検証をするIIを含むブックマーク

相変わらず詰まっていたり。木の型に木の高さの情報を入れて依存型として定義したんだけど、そうすると稲葉さんに教えてもらったafter_inの定義をどう変えていいのか分からないのだった。after_in x y tを木tの中でノードyがxの後(右)に来ることを表す命題として定義したい。この性質が保たれることを使って色々な木の操作の正当性を証明したいので結構クリティカルな問題。

まあ安易にネットで聞くのはあまりよくないと思うけど…


Definition comp_height h1 h2 := 1 + max h1 h2.

Definition balanced_height h1 h2 : Prop := h1 = h2 \/ h1 = h2 + 1 \/ h1 = h2 - 1.

Inductive avl_tree : nat -> Set :=
  | Empty : avl_tree 0
  | Node : forall h1 h2 : nat, balanced_height h1 h2 ->
    avl_tree h1 -> A -> avl_tree h2 -> avl_tree (comp_height h1 h2).

…

Fixpoint memp {h : nat} (v : A) (t : avl_tree h) : Prop :=
match t with
  Empty => False
| Node _ _ _ l v0 r => memp v l \/ v = v0 \/ memp v r
end.

Inductive after_in (v u : A) (h : nat) (t : avl_tree h) : Prop :=
| ll : forall h1 l v0 h2 r b, (h = comp_height h1 h2) -> after_in v u h1 l -> 
  after_in v u h (Node h1 h2 b l v0 r)
| lc : forall h1 l v0 h2 r b, (h = comp_height h1 h2) -> memp v l -> u=v0 -> 
  after_in v u h (Node h1 h2 b l v0 r)
| lr : forall h1 l v0 h2 r b, (h = comp_height h1 h2) -> memp v l -> memp u r -> 
  after_in v u h (Node h1 h2 b l v0 r)
| cr : forall h1 l v0 h2 r b, (h = comp_height h1 h2) -> v=v0 -> memp u r -> 
  after_in v u h (Node h1 h2 b l v0 r)
| rr : forall h1 l v0 h2 r b, (h = comp_height h1 h2) -> after_in v u h2 r -> 
  after_in v u h (Node h1 h2 b l v0 r).

当然かも知れないけど、最後定義でhはcomp_height h1 h2じゃないって言われる。うん、どうしたらいいでしょう。

追記:2010/11/2

Fixpoint after_in {h : nat} (v u : A) (t : avl_tree h) : Prop :=
match t with
| Empty => False
| Node h1 h2 _ l v0 r =>
  after_in v u l \/
  (memp v l /\ v0 = u) \/
  (memp v l /\ memp u r) \/
  (v0 = v /\ memp u r) \/
  after_in v u r
end.

というやり方で解決した。良いやり方なのかどうかは分からないけど。その後

Definition left_branch' {h : nat} (t : avl_tree h) :=
  match t in avl_tree h 
    return (match t with Empty => unit | Node h1 _ _ _ _ _ => avl_tree h1 end) with
    Empty => tt
    | Node _ _ _ l _ _ => l
  end.

Definition left_branch {h : nat} (s : {t : avl_tree h | is_non_Empty t}) :=
  left_branch' (proj1_sig s).


Definition right_branch' {h : nat} (t : avl_tree h) :=
  match t in avl_tree h 
    return (match t with Empty => unit | Node _ h2 _ _ _ _ => avl_tree h2 end) with
    Empty => tt
    | Node _ _ _ _ _ r => r
  end.

Definition right_branch {h : nat} (s : {t : avl_tree h | is_non_Empty t}) :=
  right_branch' (proj1_sig s).
  
Definition root' {h : nat} (t : avl_tree h) :=
  match t in avl_tree h 
    return (match t with Empty => unit | Node _ _ _ _ _ _ => A end) with
    Empty => tt
    | Node _ _ _ _ v _ => v
  end.

Definition root {h : nat} (s : {t : avl_tree h | is_non_Empty t}) :=
  root' (proj1_sig s).

Definition create {h1 : nat} {h2 : nat} (e : balanced_height h1 h2) 
  (l : avl_tree h1) (v : A) (r : avl_tree h2) := Node h1 h2 e l v r.

Definition bal_hyp h1 h2 := (h1 - 2 <= h2) /\ (h1 + 2 >= h2).

Require Import Compare.

Definition bal {h1 : nat} {h2 : nat} (H : bal_hyp h1 h2) 
(l : avl_tree h1) (v : A) (r : avl_tree h2) : avl_tree (comp_height h1 h2).
refine(fun h1 h2 H l v r =>
if le_dec h1 (h2 + 2) then
  (let ll := left_branch (exist _ l _) in
  let lv := root (exist _ l _) in
  let lr := right_branch (exist _ l _) in
  if le_dec (height ll) (height lr) then
    create _ ll lv (create _ lr v r)
  else
    let lrl := left_branch (exist _ lr _) in
    let lrv := root (exist _ lr _) in
    let lrr := right_branch (exist _ lr _) in
      create _ (create _ ll lv lrl) lrv (create _ lrr v r))
else if le_dec h2 (h1 + 2) then
  (let rl := left_branch (exist _ r _) in
  let rv := root (exist _ r _) in
  let rr := right_branch (exist _ r _) in
  if le_dec (height rr) (height rl) then
    create _ (create _ l v rl) rv rr
  else
    let rll := left_branch (exist _ rl _) in
    let rlv := root (exist _ rl _) in
    let rlr := right_branch (exist _ rl _) in
      create _ (create _ l v rll) rlv (create _ rlr rv rr))
  else 
    create _ l v r
).

と木を平衡させる処理の定義に入って、最後のrefineのところですごく長い型エラーが出てきたけど、今日はひとまず終わりにする。

k.inabak.inaba 2010/11/02 23:31 Inductive after_in : forall (v u: A)(h: nat)(t: avl_tree h), Prop :=
| ll : forall v u h1 l v0 h2 r b, after_in v u h1 l ->
after_in v u _ (Node h1 h2 b l v0 r)
| lc : forall v u h1 l v0 h2 r b, memp v l -> u=v0 ->
after_in v u _ (Node h1 h2 b l v0 r)
| lr : forall v u h1 l v0 h2 r b, memp v l -> memp u r ->
after_in v u _ (Node h1 h2 b l v0 r)
| cr : forall v u h1 l v0 h2 r b, v=v0 -> memp u r ->
after_in v u _ (Node h1 h2 b l v0 r)
| rr : forall v u h1 l v0 h2 r b, after_in v u h2 r ->
after_in v u _ (Node h1 h2 b l v0 r).

あたりでしょうか。_ にして推論させていますが全て (comp_height h1h2) が入ります。

yoriyukiyoriyuki 2010/11/02 23:38 ありがとうございます。tのinductionを使う方法で自己解決してました。どちらがいいんでしょうね。

トラックバック - http://d.hatena.ne.jp/yoriyuki/20101101

2010-10-24

[][]Google 日本語入力 TechTalk 2010 ノート Google 日本語入力 TechTalk 2010 ノートを含むブックマーク

ノートをそのまま公開する。具合が悪い場合はご連絡下さい。

始め

会場ついた。プロジェクタTweetが表示されている(Tweet Search Stream)。

しかし説明用の漫画を作るとかお金あるなあ。

「IME開発をしようとする気持ちを新たにしてくださると嬉しい。」

ライトニングトークテーマは入力

入力じゃなくて人力だった?!でもOK

お知らせ

諸注意

写真撮影禁止

Google 日本語入力 イベント」と検索すれば出る

ソースコード:mozcで検索

Google C++ style guide ← よめ:例外処理禁止とか。Boostに対する扱いとか。

プレゼン資料は公開禁止。ノートはOK

Google DocumentのGoogle Presentationを使う。便利だよ!

Google 日本語入力ができるまで

小松さん

Google 日本語入力

Webから自動的に辞書作成

サジェスト機能

マルチプラットフォーム

開発経緯

工藤さんと小松さんの20%プロジェクトから

工藤

Mecab, AjaxIME <- Web 2.0時代, Zinnia

小松

PRIME

Tomoe

2005年ごろから

20%ルール由来

App Engine, GMail, Transit, QR code API, 弁当注文システム, 今日の受付システム

やりたいことをやったほうがいい

何故Google がIME

「もしかして」の大部分が既存のIMEの誤変換

どろん除

インしてみる

スーパーロボット大戦

いい入力はいい検索の第一歩

だって作りたいし

Mozc team

Anthy、WinAnthy、Skkime、AjaxIME、PRIME、SCIM-skkの開発者が参加。

プロジェクト立ち上げ

最初の半年はディスカッションのみ

週数回集まって議論

デザインを決める

ある時コードが一つもないことに気づく

週一回週的にコーディングする時間を設ける

デモ

libanrhy.so クローン

プロジェクトに昇格←ずっと20%ルールでやっていたわけではない。今は本業としている人もたくさん居る。

リリースまでの道のり I

社内でドッグフード←自分のものは自分で食べる

既存のIMEとの互換性

既存IMEからの移行コストを最小限に

既存のIMEのメジャーな機能を踏襲

キーバインドも既存のIMEを踏襲

サジェスト+豊富な語彙で勝負

リリースまでの道のりII

長い長いラストワンマイル

テスト!テスト!テスト!

テストコードが本コードの2,3倍

必要最小限の機能にとどめて安定性を向上。

リリース

リリースプロセス

ドッグフード

毎日のビルドを使ってみる(社内)

continuous build、

ユニットテストストレステスト

開発版(数週間で更新)

アップデートテストなど最低限のテストのみ

クラッシュレポートを活用

利用統計情報←文字自体は送っていない。安心して!

ベータ

数か月で更新

オープンソース

googol機能←?

IMEの機能を網羅

マルチプラットフォーム

研究にも活用してください。

質問

テスト不十分で出てない機能は→答えられない。

テストが十分であるかどうかの判断は? - Crash Report, Bug Tracking

UIのテスト手法 - いいやり方がない。レイヤーを切り分けてできるだけユニットテストに落とし込む。手で動かしてみるのもやっている。バグラッシュ(?)ドッグフード

かかった人月 言えません。2人でやってるわけでも、20%でやってるわけでもない。

ユニットテストビルドを自動化。ビルド時にユニットテスト エラー→最後に変更した人とレヴューした人にメール

Google日本語入力/Mozcno設計概要

工藤さん

空気のようなIME

マルチプラットフォーム

スピード

セキュリティ

安定性

既存のやり方はうまくいかない

IMEの複雑

複雑怪奇…書ききれない

従来のやり方

DLLとして実装、辞書は共有リソース

安定性が良くない。IMEがクラッシュすると全体がクラッシュする

アプリケーションはよくクラッシュする→辞書が壊れる。

セキュリティ

IMEはセキュリティーの高いコンテキストで実行されることがある

機能の分離

IMM DLLをできるだけ小さく

処理ごとに別のプロセスに分業

ありがちな機能分離

Canna,Wnn

多くの処理をクライアントで行う

ローマ字かな変換とか

クライアントクラッシュリスクはそれほど低減しない

仮名漢字変換エンジンとキーイベントハンドラではキーイベントハンドラの方がサイズが大きい!

Stateless化

クライアントはステートレス

Google 日本語入力の機能分離

IM DLL キーイベントプロキシ

描画

候補ウィンドウはGUIレンダラとして別プロセル

安定性の工夫

データファイルは.exeに埋め込み

言語モデルは全部バイナリ

辞書が壊れない

ファイルIOのエラーが起きない

古い辞書後方互換性を気にしなくていい

#良さそう

リブート不要の自動アップデート

古典的なIME:

動作中のDLLをアップデート出来ないので、再起動を要求される

新旧のDLLが共有データを共有するのはまずい。

Google IME:

変換エンジンをkillして再起動するだけ。DLLはミニマル

仮名漢字変換アルゴリズム

n文節最長一致法:

使っているのは?

コスト最小法:

Google IMEは最小コスト法。

最小コスト

Viterbi

コスト推定法

P(x) = C p(y) * p(x|y)

p(y) : 言語モデル, 品詞ベースクラス言語モデル

Web上の単語頻度から推定

p(x|y) : 読みモデル 漢字yをどう読むか

言語モデルができるまで

Mecab形態素解析言語モデル

ウェブINDEX->単漢字辞書Googleサジェスト

読みの推定

既存の辞書ipadicからEMアルゴリズムを使って単漢字辞書を作る

当て字に弱い

読み間違い

辞書の圧縮

Mozcの辞書はIPADicのスーパーセット

100万単語

LOUDS 9.5M


Key value store -> だめ

Common Prefix Search

Predictive Search:あるPrefixをもつ文字列

データ構造はLOUD:メモリ効率がよい。おそいけど。

副作用の低減

語彙が多いと精度が下がる

一般的な表現が特殊な表現に上書きされる

評価

機械的な評価

評価の難しさ

当たり前のことを間違えることの方がNG

平均的、機械的な制度はあまり当てにならない。

<- Bleu(spell ?) test, exact test (花岡さんによる)

自動回帰テスト

絶対に変換できないといけないとまずい例をたくさん作る

失敗すると出荷できない。

日本語入力の開発は総合格闘技
質疑

プロセス間通信

Linux - Unix domain socket

Windows - Named Pipe

Mac - Mach IPC

socketを使っていない理由はセキュリティー。

相手先が認証できる。PID, username.

ストレステスト:ランダム

レンダラ:クラッシュしたら?←レンダラーはステートレスなので再起動すればOK. Linuxでは公開されていないのでIBUSでやっているのでクラッシュするかも。

品詞体系 IPADIC

プレイバック機能。変換エンジンを殺し続けても大丈夫。4秒ごとにkillしてもユーザーは気づかない。

基本語彙:IPADICは人手で修正する。ランキングはいじっていない。

コードリーディング

ビルドシステム

Jun Mukaiさん

GYPを使う(Chromeのために開発された)

why GYP:

もともとSConsを使っていた。

なぜ移行したか

SCONS:

Pythonで書かれたビルドシステム

Python普通に書けるので何でもできる

凝ったことをやろうとすると大変なことになる

プラットフォームサポートが弱い

アプリケーションや.imeファイル(?)を作るのが厄介

GYP:

シンプルビルド構文

凝ったことはできない

GYP自体はビルドしない。いろんなビルドファイルを生成する。

プラットフォームサポートが厚い

ただのPythonのDict。条件分岐が文字列キモイ

dependencies

include .gypi

action

コマンド実行ができるので、Pythonスクリプトを実行できる。

Mozcの辞書生成はC++

build_mozc.pyがgypを呼ぶ。←面倒な部分をやる

フェーズビルド:

2フェーズ

build_tools:辞書生成ツールなど

build: 本体

build_mozc.py --onepassで一度にビルドできる。

Client

小松さん

クライアントローマ字変換しない

プロセス間通信

Protocol Bufferでシリアライズしたデータのやり取り

code.google.com/p/protobuf

データ構造をバイト列にシリアライズ

シリアライズ可能なデータ構造

C++、JavaPythonに。

後方互換性、フィールドを増やすのは簡単。

Mozcのプロトコル:

セッションの作成:各入力ボックスごとに

セッションidをUniqueに割り当てる

mozc.el: Emacs

mozc_emacs_helper.cc

Converter Layer

工藤さん

Segments Class:

文節列を表現

Segments = Segment[]

Segment = Candidate[] + meta information

Candidate: Key(yomi), Value(kaki)

ConverterInterface:

ImmutableComverter

ひらがな→漢字変換

いつも同じ結果、ステートレス

Imuutable Converter

virtual bool Convert(Segments *segments) const

segmentsを呼び出し側がセットするときに制約を与える。

Rewriter

後処理

Perdictor

予測変換

rewrite:

segmentsを適宜書き換える

#うーん、あまり感心しない設計だなあ。

品詞テーブル:

data/dictionary/id.def

番号は頻繁に更新

dictionary*.txt

よみ 左品詞ID 右品詞ID 生起コスト

同じ単語でも2つの品詞を持つことがある!←複合語

data/connection.txt

コスト= -500* log(p)

システム辞書に単語を追加したい→お勧めしない

適当な量のテキストを集める

既存単語の頻度と追加したい単語の頻度比を求める

  同じ品詞になるように

頻度比のlogを取ってたす

文節区切りルール:

助詞から名詞は文節境界

data/rules/segmenter.def

データジェネレーション:

id.def segmenter.def -> if-then rule (isBoundaryInternal)

compress! bit-array ← 2,3行で書ける長さに!

Rewriter

Converterの中に

RewriterInterface:

Rewrite <- 重要

Finish 学習

Sync たまに呼ばれる

Clear 使うことはない。入力履歴をクリアする

!すべての変換で呼ばれる!

スペースが押されないとrewriterは呼ばれません

サジェスト時にはrewriterは使われません。

トリガリングルールシンプルにしないと遅くなります。

御籤:

http://code.google.com/p/mozc/source/browse/trunk/src/rewriter/fortune_rewriter.cc

数値変換:

number_rewrite.cc

数値の変換は結構複雑

四万十川 -> 4010川?

Converterは変換の途中で数値をアラビア数字に変換している

変換ルールは手で書いてある。謎めいている。

Googol 10^100->Googol

顔文字:

単純

data/emoticon/emoticon.tsv

電卓:

必ず=で終わるときだけ

lemon parserを使ってパースと演算

候補を一番上に出す

Storage

花岡さん

辞書:

LookupPredictive

LookupPrefix

LookupExact 不使用

LookupReverse 不使用

dictionary/dictionary.cc

user_dictionary:

protocol_bufferのファイル

<user profile dir>/user_dictionary.db

system_dictionary:

binaryに埋め込まれる

data/dictionary*.txt

各種データストレージ:

existence filter:

bool Exists(uint64 hash)

変換とサジェストで結果を変えるときに使う

Bloomフィルタ

LRU storage:

Insert

lookup

FAQ

バグ、問題を見つけました:Issue Trackerへ

修正パッチを送りたい:とても時間がかかる。自然言語での報告、変更方法の方が助かります。改善したいです。

辞書、単語を追加したい:BSDライセンス/パブリックドメインで公開してください。例:沖縄辞書

〇〇で動きますか:C++/STL/POSIXなら。little endianマシンだけ

Mozcを改造したい:Rewriterがおすすめです

深く開発に参加したい:Googleは通年採用しております

質疑応答

顔文字辞書:人手で

文字コード:UTF-8、困ったこと。コンパイラーのデフォルトコードがShiftJISだったりする。ヴィとか全角チルド

速度の測定:converterはクエリにどのくらい時間がかかったかを返すので、それを使う。

機能の取捨選択:重要度、容易さ、開発者思い入れ

公開されているテスト:ユニットテストストレステストがMozcに入っている。

開発プラットフォーム:開発環境:クライアント側:その環境。それ以外:好きなOS。ビルドエラーは自動ビルドで検出。

LT - 入力全般

自分の発表で忙しくてあまりノートは取れませんでした。でもSTAKKで打ち間違いに対応しているというのは面白かった。あとでコードを確認したい。

ローマ字変換テーブル

入力

出力 → 確定した文字

次の入力 → 確定前の以前の出力

懇親会

知り合いでは稲葉さん、奥野さん、田畑さん、花岡さん、向井さんと会った。向井さんとはネットでは10年くらいの知り合いなのにリアルでは初めて会った。ネット世代の恐怖。

OCamlで釣れた人一名。

Trieなら簡単にあいまい検索できるはず:要検討

Google社内での言語事情とか。

Camomile 1.0へのロードマップOCamlメインにマージするにはどうすればいいか。

Rubyの多言語化は迷走している。松本さんの趣味?どうせUnicodeに全部なるんだから無駄な抵抗はやめればいいのに。Cruby以外はUnicodeになるんじゃないか。JRubyの方が普及しているかもしれない。せっかくVMにしたのに、Railsがevalしまくりなので速くならない。悲しい。

Google IMEベンチマーク方法。Bleu(spell?)テストとexactテスト、regresssionテストベンチマークと体感が食い違う -- 当たり前のことを間違えることの方が、めったに無いものをきちんと変換するより大事。変換結果は言語モデルベースになったコーパスの質にもよる。

Appleソフトウェアキーボードはいろいろつくりこんである。前の入力で次の入力の認識範囲を変更するとか。そのために上位層との切り分けができていなくてAPIが公開できないのかもしれない。

「方が」がGoogle IME 安定版で変換できない件。まとめて変換したほうが効率が良い。

Google Japanエンジニアの割合。移転前で半分くらい。

Google IMEは社内で重視されている。本業でやっている。(今は20%ruleじゃない)。

開発効率を上げる方法:アジャイルとかTDD。

奥野さんのPythonでの実装では、Viterbiで使うポインターの代わりに、配列のインデックスを使っている。

#あまり感心しないなあ。

感想、真字へのプランなど

いろいろとモチベーションをもらった。

Mozcの辞書は使えそう。フォーマットもIPADICよりも分かりやすい。

英文の認識

とりあえずの目標としてみる。

未知語生成の部分に組み込めないか?

文字bigramで生成する未知語のコストを計算する。Mozcの辞書トレーニング

すればよい?

かな<->ローマ字が一対一でないことが問題かも。

jmukjmuk 2010/10/25 02:49 一点、こまかい訂正ですが、「ヴ」はひらがなの「う」に濁点を念頭において話していたと思います。この文字はUnicodeにはあるのですが(U+3094)、JISには(確か)ありません。IMEに閉じていれば問題ないですが、IMEを使っているアプリケーションがUnicodeをちゃんとサポートしているとは限らないので、安易に「う」に濁点を使うと問題が発生することがある、という話なのです。

zakizaki 2010/10/25 08:05 googol機能は 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 が googol に変換されるというイースターエッグですね

yoriyukiyoriyuki 2010/10/25 19:56 「う」に濁点はUnicodeでひとつの文字として書けるんですね。いろいろそういう文字はありそうですね。

yoriyukiyoriyuki 2010/10/25 19:58 はい、Googgol機能はあとで説明がありました。ノート取るまでもないかなと思ったんで書いてないんですけど。

2010-10-22

[][]CoqでAvl木を検証する CoqでAvl木を検証するを含むブックマーク

相変わらず簡単なことでつまずいている。

Section AvlTree.

Hypothesis A : Set.

Inductive tree :Set :=
  | Empty : tree
  | Node : tree -> A -> tree -> nat -> tree.

Definition empty := Empty.

Definition singleton_tree x := Node Empty x Empty 1.

Definition is_empty x := match x with Empty => True | _ => False end.

Definition is_left_branch x y :=
  match y with
    | Empty => False
    | Node l v r _ => x = l
  end.

Definition is_right_branch x y :=
  match y with
    | Empty => False
    | Node l v r _ => x = r
  end.

Fixpoint memp v x :=
  match x with
    | Empty => False
    | Node l v0 r _ => memp v l \/ v = v0 \/ memp v r
  end.

Require Import Setoid.

Definition after_in v u (s : { x : tree | memp v x & memp u x} ) : Prop.
intros.
destruct s.
induction x.
inversion_clear m.

ここで、

1 subgoal
  
  A : Set
  v : A
  u : A
  x1 : tree
  a : A
  x2 : tree
  n : nat
  m : memp v (Node x1 a x2 n)
  m0 : memp u (Node x1 a x2 n)
  IHx1 : memp v x1 -> memp u x1 -> Prop
  IHx2 : memp v x2 -> memp u x2 -> Prop
  ============================
   Prop

となってそれ以上進まない。mempの定義を展開したいんだけど、inversionが効かないし、Cutで無理やりmemp v x1 \/ v = v0 \/ memp v x2を仮定として導入してみると、今度は∨の除去ができない。

やりたいことは、AVL木のノードuが木の中でvより後ろ(右)にある、ということを表す命題after_inを定義することなのだけれども。

k.inabak.inaba 2010/10/23 11:16 mempの証明から、命題after_inという値を作る計算になってしまっているので、このままだと無理なのではないでしょうか。mempをPropではなくSetにして、そのインスタンスが証明ではなく値となるようにすれば値から値への計算はできて

Fixpoint memp v x :=
match x with
| Empty => Empty_set
| Node l v0 r _ => (memp v l + (v = v0) + memp v r)%type
end.

Definition after_in v u (x: tree) (mv: memp v x) (mu: memp u x) : Prop.
intros.
induction x.
inversion mv.
unfold memp in mv,mu; fold memp in mv,mu.
destruct mv as [[mv|mv]|mv]; destruct mu as [[mu|mu]|mu].
exact (IHx1 mv mu). exact (True). exact (True).
exact (False). exact (False). exact (True).
exact (False). exact (False). exact (IHx2 mv mu).
Defined.

destructできます。
が、目的を私が勘違いしているかもしれないのですが、命題を定義するには、Definitionで展開するのではなくInductiveで作ることが多いように思います。

Inductive memp v : tree -> Prop :=
| memp_left : forall l v0 r h, memp v l -> memp v (Node l v0 r h)
| memp_here : forall l r h, memp v (Node l v r h)
| memp_right : forall l v0 r h, memp v r -> memp v (Node l v0 r h).

Inductive after_in v u : tree -> Prop :=
| ll : forall l v0 r h, after_in v u l -> after_in v u (Node l v0 r h)
| lc : forall l v0 r h, memp v l -> u=v0 -> after_in v u (Node l v0 r h)
| lr : forall l v0 r h, memp v l -> memp u r -> after_in v u (Node l v0 r h)
| cr : forall l v0 r h, v=v0 -> memp u r -> after_in v u (Node l v0 r h)
| rr : forall l v0 r h, after_in v u r -> after_in v u (Node l v0 r h).

yoriyukiyoriyuki 2010/10/25 22:55 そうですね、目的を書かいてないので分かりにくかったと思います。目的は、あるtreeが与えられたとき、ノードvがそのツリーの中でuより前にある、という命題を作りたかったのです。memp, ater_inはもちろん決定可能に出来るのですが、検証の過程で補題として使う予定なので、SetではなくPropとしたいのです。

inabaさんの例でうまく行きそうですが、treeの条件が型に書いていないところがちょっと気になります。あとで使いたいので。

トラックバック - http://d.hatena.ne.jp/yoriyuki/20101022

2010-10-17

[][]ホームページの公開とお蔵入りソフトウェアの再公開 ホームページの公開とお蔵入りソフトウェアの再公開を含むブックマーク

何だか眠れなかったので、Google Siteに自己紹介ページを作った。使い方が今ひとつ分かっていなくて、例えばファイルアップロードしてリンクするのどうしたらいいのだろう、みたいな感じなので変なことをしているかもしれないけど。

ついでに、今までお蔵入りしていたBrainScanSurrealアップロードした。

意見等伺えると幸い。

トラックバック - http://d.hatena.ne.jp/yoriyuki/20101017

2010-10-08

[][]Coq初めの一歩 Coq初めの一歩を含むブックマーク

最初苦労してしまったが、CoqUbuntuに導入して簡単な証明をしてみた。

導入したのはProof General-3.75とCoq 8.2r2の組み合わせ。最新版のProof General(開発版)はEmacs 23を要求するので、Ubuntu 10にアップグレードしようとしたけれど、キーボードが効かなくなるという問題があって*1Ubuntuをもとの8.04に戻して、Emacs21に対応しているProof Generalを入れた。最初Proof Generalの3.5を使ってたら、Coqの出力を読むところで固まる。そこでid:yoshihiro503さんのアドバイスに従って3.75にしてみたら、動いた!

とりあえずこんな感じ。結構難しかった。

Theorem Modus_ponens:
  forall (P: Prop), forall (Q: Prop), (P -> Q) -> P -> Q.
intros.
auto.
Qed.

Theorem BadSpeak: 
  2 + 2 = 4.
eauto.
Qed.

Section PartyLine.
  Hypothesis GoodSpeak : 2 + 2 = 5.

  Hypothesis P : Prop.

  Lemma AbsurdityLaw : False -> P.
  tauto.
  Qed.

  Lemma E : 2 + 2 = 4.
  eauto.
  Qed.

  Lemma F : 2 + 2 = 5 -> False.
  rewrite E.
  apply n_Sn.
  Qed.

  Theorem Absurd : P.
  cut False.
  tauto.
  apply F.
  apply GoodSpeak.
  Qed.

End PartyLine.

assumptionもexactもtacticとして認識してくれないので、autoで締めるというという間抜けなことに。しかもProof Generalのcoq以下のディレクトリにあるexample.vではassumptionが上手く動く。なぜ!?

あと、forall P:Prop. Pを証明したかったのだけど、ゴールを設定する時に構文エラーになってしまう。

まあとりあえず、党って怖いですね。

*1:Workaroundはネットに出ているけど、その通りしても上手くいかなかった。

トラックバック - http://d.hatena.ne.jp/yoriyuki/20101008

2010-09-22

[]Livedoor ClipエクスポートファイルEvernoteに取り込む Livedoor ClipのエクスポートファイルをEvernoteに取り込むを含むブックマーク

Livedoor ClipエクスポートファイルEvernoteに取り込むツールを作成した。

バイナリ版:LDC2Evernote(Binary)-20100922.zip 直

ソース版:LDC2Evernote-20100922.tar.gz 直

ただし、ソース版はAPI-keyを削除しているのでそのままでは利用できない。Evernoteサポートに連絡してAPIキーを発行してもらうか、私のところまで連絡して欲しい。

使い方:

バイナリ版で説明する。ソース版については、README.txtを参照して欲しい。

インストール

まず、パッケージを展開する。LCD2Evernote(Binary)というディレクトリができるので、そのフォルダを開ける。

f:id:yoriyuki:20100922214224p:image

まずこの中のvcredist_x86.exeを実行する。これにより、必要な実行時ライブラリインストールされる。

LDC2Evernote自体はインストールの必要はない。

実行

次にdistというサブディレクトリに移動し、LDC2Evernote.exeを実行する。

f:id:yoriyuki:20100922214223p:image

インポート先のノート名は手で入力する。インポート先のノート名は、他のノートとは別のノートにしておくのがおすすめ。そうしておくと、他のノートを汚さないので問題が起きても対処しやすいと思う。

clip the linked documentsをONにすると、ブックマークされたWebページをクリップしてEvernoteノートとしてインポートする。ただし、上手くいかないことも多い。このオプションONにすると、アップロードにかかる時間がかなり増える。また、データ量も多くなるので、アップロード量の制限に引っかかるかもしれない。

Startをクリックすると、アップロードが始まる。

f:id:yoriyuki:20100922214225p:image

連絡先

コメント等はyoriyuki.y+LDC2Evernote@gmail.comに送って欲しい。

トラックバック - http://d.hatena.ne.jp/yoriyuki/20100922

2010-07-04

[][]やさしいイタリア語 やさしいイタリア語を含むブックマーク

やっと勉強し終わった。この本を買ったのは、博士卒業したけど職はなくて、なんとなく職探しをする気力もなくして東京フリーターをしていた頃だった。職がないという話を聞いて、しばらくイタリアに来ないかという話が来て、買ってみたのだった。それから何度も勉強としようとしては挫折を繰り返していて、やっと真面目に取り組み始めたのが今年の春くらいで、週に2節ずつやってやっと終わらせた。この本は1節が会話とそれに出てくる文法事項の解説から成っているので、まず文法事項と会話の訳に目を通してから、シャドウイング(テキストは見ない)を繰り返して上手く言えるようになるまで練習するという方法で勉強していた。まあ、正しいやり方かどうかは分からないけど。この本は会話ベースできちんと文法も解説してあるので、なかなかいい本だと思う。ちょっと古くて、会話の中の通貨単位リラ(!)だったりするけど。

ところで、イタリア行きの話はどうなったかというと、予算の都合で延期になっているうちに、私が今の職場就職してしまい、結局だいぶ期間を短く(4ヶ月)して職場の許可をもらって、2006年の秋に行ってきた。

よく若い研究者海外で「武者修業」(武者に例えられるのもなあと思うけど)するようにと言われるけど、確かに就職や昇進で、海外から招聘されたという経歴は武器になると思う。*1では、研究者として何か新しい視野が開けたりするかというと、どうだろうか。自分場合、確かに1つ論文を書かせてもらったけど、アイディアをもらって書いたので、なんとなく自分研究とは思われず、その後続ける気があまりしなくて放ってある。もともとイタリア教授とはメールでずっとやり取りしていたので*2、必ずしも実際に行く必要はなかったかなとも思う。

ただ、もっと広く人間としての成長という点では、やっぱり行ってよかったかもしれない。とにかくいい思い出になったし、美しい景色もたくさん見れた。イタリアとの縁で友人も増えた。前よりも物怖じしなくなったし、外向的になった気もする。

まあ他の人へのアドバイス的なことはなくて、自分価値観で決めて欲しいと思うけど、自分経験をちょっとだけ書いてみた。役立ててもらえれば幸い。

*1:私の場合、正確には招聘ではなくて研究費の助成イタリア大学側が行う、ということで、交通費や滞在費をそこから出した。

*2:これは役に立った。自分研究者になれたのは教授にいきなりメールを送りつけたことがきっかけだと思う

onishionishi 2010/07/04 23:47 最近はイタリア語の本も増えましたね〜
こんど本屋さんでのぞいてみます、この本も。

yoriyukiyoriyuki 2010/07/05 13:42 次はイタリア語検定の4級を目指して勉強しようかなあと思っています。テキストは買ったんですが、やるんでしょうか。

トラックバック - http://d.hatena.ne.jp/yoriyuki/20100704