2009-04-23 Thu

読めなかった沖縄の市町村名と地名

沖縄の地名は読むのが難しいですよね、ということで、どのくらい読めるのか少し試してみました。

以下のページを見て、読めるかどうか確かめてみました。

- 沖縄の市町村名と地名
-- http://www.asahi-net.or.jp/~qk3m-knk/oki-zatu01.htm

■ 僕が読めなかった市町村名と地名

宜野湾市ぎのわんし
平良市ひららし
粟国村あぐにそん
伊平屋村いへやそん
大宜味村おおぎみそん
北大東村きただいとうそん
北中城村きたなかぐすくそん
金武町きんちょう
具志頭村ぐしかみそん
城辺町ぐすくべちょう
国頭村くにがみそん
東風平町こちんだちょう
玉城村たまぐすくそん
北谷町ちゃたんちょう
渡名喜村となきそん
豊見城市とみぐすく市
中城村なかぐすくそん
南風原町はえばるちょう
読谷村よみたんそん
仲村渠なかんだかり
西武門にしんじょう
奥武山おおのやま
奥武島おおじま
勢理客じっちゃく
平安座へんざ
喜屋武きゃん
瑞慶覧ずけらん
我部祖河がぶそか
御殿敷おどんじき
越来ごえく

いやぁ、かなりの確率で読めませんね。
「城」を「ぐすく」って読めないために「城」が出る地名は全滅です。

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-04-23 Thu

ポメラでログ

今日からブログをポメラで書き始めました。

ポメラ

買ったポメラの色はホワイト。
ここ1週間くらい、僕は1日3回くらいポメラについて検索しており、明らかに完全にポメラに取り憑かれていたので買ってしまうことにしました。

楽天で送料と手数料合わせて15900円くらいで買いました。

ポメラって電池が付属していないことに気がつき驚愕。
あわてて購入しました。

僕はエネループを持っていないので、電池を買いまくる予感。
もったいないからエネループを買わなきゃな。

ポメラみんなでパチパチ

早速ランチを食べるときに持っていって暇つぶし。

■関連リンク

KINGJIM デジタルメモ「ポメラ」 DM10シロ パールホワイト

[Amazonで詳細を見る]


楽天で「ポメラ」を調べる。

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-03-25 Wed

コーヒーを飲んでいますか?僕は飲んでますよ。

だからなんだよ、と思う人も多いかもしれませんが、
コーヒーを飲んでいるために、悩むこともあるわけです。

最近、コーヒーメーカーのサーバー(ガラスの器)を
盛大に粉砕したために、日中コーヒーを飲んでいません。

それと関係しているのかわかりませんが、
先週末から「何故か落ち着かない」ときとか
「何故か集中できない」ときなどにコーヒーを飲むと

「気分が落ち着くことが多い」

ことに気が付きました。

「もしかしてカフェイン依存症なのかな?」と思い、
Googleで検索してみたらこんな結果が、、、

- コーヒー(カフェイン)依存症 - Yahoo!知恵袋
-- http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1310975373

一日に3杯〜4杯程度なら大丈夫かと思います。

コーヒーを最後に摂取してから 12時間以上経った時の症状で依存症かどうかの判断をするようです。

1. 体がだるかったり、頭がぼんやりする
2. 不安になったり、気持ちが落ち込んだりする
3. 悪心や嘔吐が起こる

この内、どれか1つでも見られたらカフェイン依存の可能性があります。
カフェインを最後に摂取した後、12〜24時間後にこれらの症状が出現します。
症状のピークーは1〜2日後で、1週間程度で症状は収まります。


;:゙;`;・(゚ε゚ )ブッ!!

2つくらい当てはまる。。

そういえばカフェインって緑茶にも含まれていますよね。

ということは、
「食後に緑茶を飲まないと、なんだか落ち着かない」
と思っている世の中の日本茶が大好きなお年寄りも、
須らくカフェイン依存症なんじゃないかと思ったり。。

「なんだか」とか「なんとなく」の裏側って怖いなぁ。

関連リンク


- らばQ:普段飲むドリンクにどれくらいカフェインが入ってるか
-- http://labaq.com/archives/50842085.html

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-03-24 Tue

文字列の扱いをCでやるか、C++でやるか

文字列の扱いをCでやるか、C++でやるか、で悩んでいます。

今まではCで書いてたのですが、少し悩んで大丈夫な状態なので悩みんぐ。。
このままガリガリ書くのと、ライブラリに任せるのどっちが良いかな。

うーーん。悩ましい。どっちも一長一短で美学の問題な気もする。。。

他人のコードを眺めて悩もうかな。。。

[2009-03-25]:追記
@debugordieさんから、「俺ならglib使う」と教えていただきました。
glibかっ!! 早速使ってみますー。

[2009-03-25]:さらに追記
glib使ってみたけど、ちょっとリッチすぎるので、
やっぱり自前で構造体を使って書くことにしました。

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-03-24 Tue

外はWBC一色

今日のお昼に外を歩いたら、ちょっと異常な光景を見ることができました。

何がおかしいって、目の前から歩いてくる人の半分くらいが、
携帯電話のワンセグ放送を見ながら歩いてくるんです。

みんなどんだけWBCが好きなんだwwww

電気屋のテレビの前も人だかりです。

WBC

うーん、日本勝ってくれないかなーー。

[2009-03-24]:追記
勝ちましたーーー!!!

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-03-23 Mon

アルゴリズムデザイン 読書メモ2-2

アルゴリズムデザインを読んでるのですが、
先週に引き続き読書メモがあるので、それを貼っておきます。

アルゴリズムデザイン: Jon Kleinberg, Eva Tardos

[Amazonで詳細を見る]


以下、メモ。

** リストと配列によつ安定マッチングアルゴリズムの実装

本書のアルゴリズム記述 = ハイレベル形式

ハイレベル形式アルゴリズムの漸近的な計算時間を解析する方法
=> 実装してみるしかない
=> というわけではない

考慮すべきはデータ構造
=> ステップ数をいかに減らせるか

** GSアルゴリズムは反復数だけでなくステップ数もO(n^2)

効率よくGSアルゴリズムを実装できるデータ構造
= 配列(array)かリスト(list)

安定マッチングで解決すべき問題1
=> 好意順リストの表現方法

安定マッチングで解決すべき問題2
=> マッチングの管理方法(自由、婚約状態の把握)

データ構造の選択はアルゴリズム設計者任せ

選ぶべきデータ構造
1、アルゴリズムに対して効率が良い
2、実装がより楽

データに前処理をしてデータ構造に近づけることもある。

** 配列とリスト
n個のリストを表現する最も簡単な方法
= 長さnの配列Aのi番目の領域A[i]に、リストのi番目の要素を記憶する

配列Aの性質
1, リスト中のi番目の要素を調べるコスト
= A[i]に直接アクセスすればO(1)

2, 特定の要素eがリスト中にあるか調べるコスト
= 配列A中の要素の順序情報を使えない場合はO(n)
= 配列A中の要素の順序情報を活用できる(ID順とか)場合は、2分探索できるのでO(log n)

でも安定マッチングは、リストの要素が刻々と変化する
=> 要素が動的に変化すリストを配列で表現するのは非効率

そこで連結リスト(linked list)。

連結リスト
- 基本単位はノード
- 各ノードに集合の要素が記憶される
- 各ノードは次のノードを指すポインタを持つ
- 先頭から終端までポインタをすべてたどるとリストの要素を検索できる
- 検索にかかる時間はリスト長に比例する

連結リストは、直前のノードを指すポインタのフィールドも持つようにすれば、
二重連結リスト(doubly linked list)になる

連結リストの更新
- 削除(deletion)
- 挿入(insertion)

連結リストLの性質
1, リストLのi番目の要素を調べるコスト
= 先頭から辿る必要があるので、O(i)かかる

2, 特定の要素eがリスト中にあるか調べるコスト
= これもO(n)

配列とリスト間の変換にかかる時間
=> O(n)

安定マッチングの実装

好意順リストの実装
- 男性による女性の好意順リスト:n人分の要素nのリスト
- 女性による男性の好意順リスト:n人分の要素nのリスト
=> 記憶領域はO(n^2)

自由な身の男性を管理する
=> 連結リスト

各男性が次に婚約を申し込む女性
=> 並列で管理する
=> 婚約を申し込んだら進むカウンタ

各女性の状態(自由、婚約している男性がいる)を管理
=> 配列

各女性が、各男性を何番目に好きかを管理する
=> 2重配列
=> (w, m)と(w, m')をそれぞれO(1)で求める方法は配列

** よく現れる計算時間
多くの問題には可能解の集合がある。
=> 多くの問題には自然な探索空間(search space)がある

全探索よりも効率の良いアルゴリズムを探そう!

問題解決時に検討すべきこと
1、計算時間の限界
2、探索空間のサイズの限界

全探索から考え、その後で、改良を加えるアプローチをとる。

** 線形時間(linear time)
- 各要素に対して定数の量の仕事しかしない : O(n)の仕事量

オンラインアルゴリズム
データストリームアルゴリズム
=> データが流れてきて通過するまでの時間に仕事を行わなければいけない

** O(n logn)時間
たとえば、マージソート。

多くのアルゴリズムの計算時間がO(n log n)になる理由
=> ソートに一番時間がかかるアルゴリズムが多いから


** 2乗時間

2次元空間上の最近点の探索

入れ子のループ

** 3乗時間

集合の要素と集合の要素の比較

** O(n^k)時間

グラフの独立集合を探す
=> k点の集合それぞれについて、他の集合と比較する必要がある

** 多項式時間を超えて

O(2^n)とかO(n!)

NP-完全問題なクラス

例、巡回セールスマン

** 線形未満時間
2分探索とか

** 優先順位付きキュー

最も良く用いられる、洗練されたデータ構造の一つ

以下つづく


今後も気が向いたら公開する予定。

「アルゴリズムデザイン 読書メモ」関連エントリ


- アルゴリズムデザイン 読書メモ2-2
- アルゴリズムデザイン 読書メモ2-1
- アルゴリズムデザイン 読書メモ1-2
- アルゴリズムデザイン 読書メモ1-1

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-03-23 Mon

サントリー白州蒸溜所のブログパーツ

先日、サントリーの白州蒸留所まで工場見学にいってきました。

その白州蒸留所のブログパーツが公開された、ということでご紹介します。

白州蒸溜所の魅力、ハイボールのおいしさを、より多くの方々に知っていただきたく、ブログパーツを作成しました!

- http://yamazaki-d.blog.suntory.co.jp/001793.html

さっそく貼ってみましょう。



なるほど、

様々な白州にまつわる画像が次々に表示されるので白州好きにはたまりませんんね。

白州のブログパーツ

セミナーレポートは、僕も書いているので気が向いたら以下も見てみてください。

「サントリー白州蒸留所の見学」関連エントリ


- 1、朝の移動
- 2、昼食は紅マスの自家製薫製ちらし寿司
- 3、白州蒸留所ってどんなとこ?
- 4、お酒が飲めない方に「天然水工場」と「野鳥の森」
- 5、「ウィスキー博物館」には展望台があって素敵司
- 6、いよいよ「蒸留所見学」へ
- 7、仕込槽内と発酵槽の様子を観察
- 8、発酵槽内と蒸留釜の様子を観察
- 9、蒸留釜エリアの様子を観察
- 10、リチャー場でおおはしゃぎ
- 11、貯蔵庫
- 12、シングルモルト楽しみ方講座:ハイボールからはじめよう
- 13、セミナーに興味がある人は

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-03-22 Sun

今日はブログ書いて、寝て、しかしてない

今日は朝に散歩した以外は、本当に一日家の中にいました。

ブログ書いて、ご飯食べて、寝て、ブログ書いて、ご飯食べて、寝て、ご飯食べて、ブログ書いてます。

やることはコツコツやらないとね、という教訓になりました。

よく寝たので体が休まって良かったことにします。

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-03-17 Tue

何も考えずにブログ書きたい、と思う今日この頃

ここのところ、ブログにアップできていないけど、
テキストはガリガリ書いているんです。

今週の3連休は何にも考えないで、ひたすらブログを書きたいです。

あとは、自宅サーバを組み立てたり、
ブログをレンタルサーバに移動したり、
試そうと思ったこと試したり、
あ、そうそう、読みたい本もあったなぁ。

来年度に向けて、身の回りを少し整頓しよう。

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-03-16 Mon

計算理論の基礎

おもむろに「計算理論の基礎」を買いました。

アルゴリズムデザインにも出て来た計算の複雑性に関する言及が、
ガッツリとされているっぽいので楽しみです。

ちなみに、新しい方は3分冊で面倒くさいので旧版を古本で注文しました。

計算理論の基礎: マイケル シプサ

[Amazonで詳細を見る]


今から届くのが楽しみです。

問題の「アルゴリズムデザイン」は2章の真ん中くらいまで読み進みました。
先はめちゃめちゃ長いですが、ゆるりと進みたいと思います。

今週は金曜日が祝日なので勉強会はお休みですので、
来週くらいには解答付き演習まで終わると思います。
下書き状態のノートを、メモ程度まで仕上げなくては。

アルゴリズムデザイン: Jon Kleinberg, Eva Tardos

[Amazonで詳細を見る]


それにしても、アルゴリズムデザインは日本語の言及が無さ過ぎて
毎週欠かさず泣いてます。誰かボスけて。

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-03-10 Tue

アルゴリズムデザイン 読書メモ2-1

アルゴリズムデザインを読んでるのですが、
先週に引き続き読書メモがあるので、それを貼っておきます。

アルゴリズムデザイン: Jon Kleinberg, Eva Tardos

[Amazonで詳細を見る]


以下、メモ。

■第2章:アルゴリズム解析の基礎事項
- 概念の本質の具体化手法
- 入力データと計算量の関係を見積もる数学的枠組み
- 基本的なアルゴリズムの計算上界
-- GSアルゴリズムの実装
-- 多くの異なる計算時間を概観
-- アルゴリズムの特徴を整理、分類する。
- 有用なデータ構造例
-- 優先度付きキュー
-- ヒープ

●クイックソートとヒープソート
どっちの方がより良いかな。。

■計算容易性
本書の目的 = 計算問題に対する効率の良いアルゴリズムの発見

本書特有のアプローチ
1、設計原理を特定し、きちんと記述する
- 基本的な事項から取り上げつつ、冗長でないように

2、取り上げる問題の多くが離散的な性質を持つ
- 目標:可能な組み合わせの巨大空間から、指定された条件を満たす解を効率よく発見

3、計算時間(running time)と、領域量(space)に着目する。
- より速く、より小さく

■効率性の定義

欲しい定義
1、実行環境や入力インスタンスに依存しない
- 単に「速さ」に着目するなら、計算機の進歩を待てば良い
2、入力サイズが増加した時の値が予測できる
- 入力サイズが巨大になったときも効率を予測できるかどうか

学んだこと
- where : どこで?
- how well : どのようにうまく?


■最悪の場合の計算時間と全探索

最悪の場合の解析(worst-case analysis)
- アルゴリズムの実際の効率を捉えるのに適当

平均の場合の解析(average-case analysis)
- しばしば泥沼にはまる
-- ランダムな入力インスタンスの出現範囲を表現するのは困難
-- ランダムな入力をどのように生成するべきか。。。

⇒本書では、計算時間について最悪の場合の解析を考える

安定マッチング問題
単純には「n × nの組み合わせについて、すべての完全マッチングを列挙し、それぞれが安定かを調べる必要があった」
⇒探索空間(search space)が巨大であった

好意順リストの概念を取り入れたら!?
⇒高々「長さnの2n個のリストの量」= 2n^2という入力サイズに、まぁぁ比例する計算量
⇒全探索(brute-force search)しなくて済んだ

注目!
- この「入力サイズNに比例する」という結論を解析レベル(analysis level)で得た

本書では、つまりは全探索より本質的に良い手法を考えたい

学んだこと
- 本質的に良い性能とは何か
⇒もっと注意深く考察し、計算時間の数量化を試みよう

■効率性の定義としての多項式時間
自然な組み合わせ問題の計算量
- 入力サイズNの指数関数で増加する傾向

⇒入力サイズNの定数C倍だけ増加する傾向のアルゴリズムが欲しい

★多項式の計算時間(polynomial running time)
以下の条件を満たすような計算時間
- 定数 : c > 0, d > 0
- すべての入力インスタンスのサイズ : N
- 計算時間 : cN^d個の計算ステップで押さえられる

このような計算時間をもつアルゴリズムを
多項式時間アルゴリズム(polynomial-time algorithm)という。

- 計算時間 : cN^dのときに入力データサイズが4Nになったら?
⇒c(2N)^d = c(2^d * N^d)
このとき、c*2^dは定数だから結局データサイズに、まぁあ比例してるといえる。

表2.1 = 入力インスタンスのサイズに対する計算時間

学んだこと
- それぞれの問題は固有のレベルの計算容易性を持つ
- 効率的な解は、ある時とない時がある

■増加の漸近的オーダー
最悪の計算時間を考える時に、あんまり細かく計算時間を計算する意味は無い。
- 例、ステップ数で計算時間を算出
⇒高水準言語で見積もって、低水準言語で実行すると、ステップ数が変わる

O:漸近的上界(asymptonic upper bound)
- 計算時間T(n)がO(f(n))

Ω:漸近的下界(asymptonic lower bound)
- 計算時間T(n)がΩ(f(n))

Θ:漸近的にタイトな限界(asymptonic tight bound)
- 計算時間T(n)がO(f(n))かつΩ(f(n))

以下つづく


今後も気が向いたら公開する予定。

「アルゴリズムデザイン 読書メモ」関連エントリ


- アルゴリズムデザイン 読書メモ2-2
- アルゴリズムデザイン 読書メモ2-1
- アルゴリズムデザイン 読書メモ1-2
- アルゴリズムデザイン 読書メモ1-1

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-03-05 Thu

NLP2009 言語処理学会第15会年次大会 3日目

以下、メモ。後で編集しなおします。

** 語義曖昧性解消
用例対の類似度が0になってしまう場合、
検索エンジンのスニペットを使ったりして、
素性空間を拡張してみれば、間接的に類似度が取れそう。
でも、それが気持ち悪ければ、LSIとかで拡張した空間を圧縮すれば良いのかな。

表層をもとにした類似度がうまく計れない場合には、
相手の要素が居て初めて計量可能になるような
類似度の尺度を使う必要があるだろう。
シソーラス上の距離とかね。

** 商品説明から
検索キーワードを自分で探さなきゃいけないとか、
サイトから提供される語とか、はあんま使えない。

商品の特徴を表すシードリストを取得する。
統計的手法でノイズを取り除くのだ。(おおお、すげえ

具体物は、検索結果をしぼりこみすぎてしまう。
ブランド名は、ノイズになってしまいがち。
商品カテゴリは、絞り込む際に役立つ。

関連語とは、
1、商品の特徴を表す
2、該当する商品が多数存在する。
3、検索語と同時に検索に用いたとき役立つ。

入力:URL
出力:関連語リスト

URLからクエリを取り出す、検索条件、ジャンル名
形態素解析で商品説明文から頻度付きの候補と取り出す。
検索語と同じジャンルで、候補を検索する。
候補から(ジャンル名、ヒット数)のリストを取得する。

関連語候補から、ジャンル、頻度が離れすぎてるものをどける。

検索クエリ関連語と、関連語検索クエリ、の両方を検索する。
よりヒット数の多い方を候補とし、共起スコアを算出する。

検索回数が多すぎる気がするなぁ。

ぶっちゃけ、クエリリストから同じようなふるい分けをすれば良いかも。
URL中お、検索条件を加味するのが面白いと思う。

この手法では、メーカー名は抽出できなかったらしい。
ふーん。

上位、下位の下位は取れやすいが、
ブランド名や属性(材質とか)は取りにくいようである。

取得した候補に、カテゴリの多義性があると
関連語の候補として取得しにくいのである。
ということは単純な頻度ではなく、
検索APIを使った類似度計算をしないといけないのかもね。

** 単語用例の語義に基づくクラスタリング
グラフ構造のクラスタリングをする

グラフ:同じ文で出現した単語をルール(係り受けとか、単純な出現、Window幅以内)でつなぐ。

グラフを次元縮訳する際に、表層から得られる概念を使ってる。

ソフト、ハードの両クラスタリングを試している。

クラスタリングする際に、表層を概念に抽象化することで
空間を圧縮するとよいだろうね。

** 文書クラスタリングを対象とした、Weighted Kernel K-meansの初期設定方法
文書集合をトピックに従って分割する作業は、
人手でやるのが膨大なため大変であるよ。

k-meansは
クラスタリングの結果が初期値に依存する
 少しでも良くなるように、ランダムな初期値で複数回おこなうんだけどね
非線形な分離境界を持つデータでは良い結果を得ることが出来ない。

カーネルk-means
非線形な分離境界を持つデータ用のk-means
高次元に写像し、カーネルトリックでカーネル関数を使った高次元の内積計算を簡単に行なう。

kernel k-meansもweighted kernel k-meansも初期値依存。
ただ、weightedの場合計算が膨大になる、

KKZ

スペクトラルクラスタリングは固有値を求めてクラスタリング。
でも、固有値計算はめんどう。
weighted kernel k-meansならうまくいくよ。とのこと。

エントロピー、正解がどれほど起こりにくいのか

** 固有表現間の関係を獲得
ブートストラップによる半教師あり獲得

分かち書きやクエリログではなく、
日本語の長い文からブートストラップするMonaka

シード(例えば3単語)
シード要素前後の文字n-gramを取得する。
左# #右
これをクエリにして検索して、
# #で挟まれている部分を獲得するような制約を加えた。
獲得したインスタンスをまた投げる。

上位だけ見ると形態素解析なし、正しく獲得できた。

ブートストラップは意味ドリフト。
Espressoもmonakaも不可避。

定式化が不十分であり、パラメタ調整が難しい。

グラフカーネルを使ったMonaka。。。重そうだな。

右側文脈の類似度 = 書誌結合、と見なせる
左 = 共引用と見なせる。

これは、おもしろい気がするなぁ。


** 共起語分布の言語間差異
同じトピックのブログ
を比較するよ。
クエリは日本語。
日本語ブログを検索。
クエリを英訳。英語ブログを検索。

トピックの選出はWikipedia使った。
トピックの関連語は、Wikipediaから取り出した。

機械翻訳が間違っていた場合に英語側の表現を取得できないんじゃね?
っっっっっっっほ

外国人の指摘
日本語で一つの言い方があるけど、英語は複数の訳を持つことが多い。
英語は日本人以外は沢山使ってるよ。

** 大規模コーパスを用いた分布類似度
大規模コーパスを利用すると言語処理の精度が向上する。

用法が多数ある助詞を考慮すると精度が下がる。。

JUMAN使ってる

** 日中漢字の対応関係の自動獲得自動獲得
Unicode空間では文字が全部同一の空間。

日中漢字は、それぞれ文字の違いと意味の違いの組み合わせがある。

Unicode対応付け
変換テーブルによる対応

意味が同じだが表記の異なる文字の対応付けを取得したい。

翻訳手法を使って変換を行なう。

もともとの翻訳例の組をそろえる。
変換確率を学習する。

GIZA++をつかっているらしい。

手法を単一で適用しているが、併用した方が良いだろう。

** トピック変化点検出
トピックモデル
単語間の帯域的な依存関係をトピックとしてモデル化
PLSI,LDADMとかをつかう。

ヒストリ長が重要

LDAの概要
各潜在トピックの生成確率をC次元のディリクレ分布に従う確率変数とする。
トピックの広がりや、トピック間の共起関係を検出できる。

ヒストリ長が固定のときのトピック適用
話題が変化があったところを推定、
そこから後ろだけを使う。
つまり固定長だと範囲から外れてしまう前側の範囲を計算に使える。

形態素列から切れ目を探す。
順に切れ目の前後の類似度を算出し、
前後類似度が最も上がる部分を検出する。

複数LDAの統合
複数のモデルで推定したuni-gram確率を平均すると、性能が向上する。

これを、ヒストリ長の最大化を計る。

** 固有名詞間関係
明示的な関係、暗黙的な関係の2つを区別せず抽出

抽出されたX, Yについて、明示的な関係Rを特定する。
特定できなかった場合には、暗黙的関係を特定しにいく。

構造学習で問題を解く方法がある。
Aの姉のBが優勝
から姉>優勝の構造を学習する。


語彙的情報
人と人は
姉 > 優勝じゃやない??

関係を在ら和しやすい名詞とは
XのRはYだ。

関係表現R、

関係名詞(一項名詞、相対名詞)
基準Xと、指示対象Yそれぞれと、Rの関係を見る。

「AのB」
AのBのBが関係名詞の場合には、
カテゴリが集中する。
つまりエントロピーのより低い名詞が関係名詞。

ブログにX, Y, Rを付与し、BACTを使う。
ふむ。。

正解の関係表現中に、正解データ中でより多かった動詞を選択してしまう。
ふーん、BACT使うと、そうなるのね。。

** 手がかり表現

「で」は多義性をもつ
「で」は並列した事象を表現可能

機械学習により、原因表現と結果表現が
因果関係をもっているかどうかを判定する。

「で」の前後の文に出現する助詞、が、
並列構文の判断に効くという直感がある。

文が因果関係を持たない場合に、
手がかり語の直前に出現する語には特徴がある

** タンパク質相互作用
タンパク質相互作用:PPI

文にあらわれる2タンパク質間の相互作用抽出。
与えられたタンパク質が、作用してるか、作用してないか、の2値分類。

LLLeruerueru
Bioinferバイオインファー
AIMedエーアイメド

転移学習
Transfer SVM

ソフトマージンTrAdaBoost

全経路グラフカーネル

ASOlearningとdomein adaptationとの差
aso semi-supervisedでラベルを使わない
 ラベルは同じ、というように見ている
転移学習は転移先でも元でもラベルがついている。

liblinier

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-03-05 Thu

emacs 22.3を自前でコンパイル

すぐCPU使用率が高まるので、自前でコンパイルしてみました。
特にオプション指定しないでも十分かと思い、そのままコンパイル。

以下から一番新しそうなパッケージを取得して、解凍しました。

- ftp://ftp.gnu.org/gnu/emacs/ の一覧
-- ftp://ftp.gnu.org/gnu/emacs/

./configure --prefix=/usr/local/emacs22.3
make
make install


うまくいきました。
Emacsって大体コンパイルうまくいきますよね。すばらしい。

.zshrcにaliasを追加します。

alias emacs=/usr/local/emacs22.3/bin/emacs


最後に、.zshrcの更新を反映します。

source ~/.zshrc


Debian etchのaptで入るemacsだと100%になるけど、
9%くらいになったやりーー。

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-03-04 Wed

NLP2009 言語処理学会第15会年次大会 2日目

以下メモ。後で書き直します。

** p: 2日目
** 「に」の深層格
名詞属性付与と動詞属性付与から、深層格を推定してしまう。

名詞属性
 辞書見出しから、末尾処理から、それいがいから
動詞属性
 辞書見出しから、から、から

深層格の出し方
 「に」の深層格の属性を出すルール表をつくった!

疑問
「に」の深層格を応用すると?

言い換え
 私は彼に車を貰った→私は彼から車を貰った

 に、を言い換えると、英訳の質が変わる

課題
 慣用句に弱い「水に流す」

** 意味役割付与
述語項構造解析の一種
 各項には意味役割と呼ばれるタグが付与される
機械翻訳などの応用に役立つ、とされる

意味役割は、意味フレームを基に、
そのフレーム固有の役割として定義される。

フレームの数は少なくない
Propbank :
FrameNet :

多くなると、付与コストが高まる。
まとめなきゃ。



一般化手法として、別のタグにまとめる手法があるが、
分類精度に影響があることが報告されている。

意味役割はきれいに別れておらず、
異なる役割が圧縮された状態なのではないか。

4つの観点から意味役割を考え、それらをまとめてみる。

** 述語項構造解析
述語の基本形対して、(主格(ガ格)、体格(ヲ格)、与格(ニ格))を与える。
解析ルールを直感的につくる。かつ、精度向上をめざす。

NAISTテキストコーパスを使った
毎日新聞95のニュース記事と社説が対象。
3つの各に対して、解答が付与されている。

仮説
 項はある制約のもとで、対象の述語に最も近い位置にある名詞である

文内格推定とゼロ代名詞同定につかえる、らしい。

** 指示連帯詞
この、その、あのが、指示詞に付いている場合の
先行詞同定と

先行詞同定
 トーナメントモデルを使う。
 
 調査1、この、その、あのは分ける必要があるか

指示関係分類
 指定指示と代行指示の分類。
 分類に従い、

課題
 先行詞が述語な場合がある
 生茶では絶対に勝てない。今回もそのジンクスは破れなかった。

 (NP(Pred X)Y)のような統語構造をもつ(X, Y)の対を獲得しておき、述語照応の手がかりとして理由する。

 指示代名詞が無い場合は、いまのところ考えてない。

** LFG解析を利用した意味解析
意味解析にはレベルがある

** BCCWJを用いた語義曖昧性解消タスク
代表性のある語義曖昧性解消タスク

意味解析技術のひとつ、文脈に出現した単語の意味を決定する。
例、ネタ → 新聞記事などの材料、手品の仕掛け、証拠、食物
問題、時事ネタ、のネタってどんな意味でしょうーか

Semeval-2が2010に開催される予定だ

現代日本語書き言葉均衡コーパス。
特徴
 様々なジャンルのテキストからなり、代表性がある
 世の中のテキストを代表したコーパスを作りたい

BCCWJのコアデータに対して、
 岩波国語辞典の区分に基づき、人手で語義を付与
 語義中の該当の語義が見当たらない場合、。。

WSD評価型タスク
特徴
 1、代表制のある語尾タグ付きコーパスを用いたタスク
  代表制 = 複数のジャンルのサブコーパスの集合
  サブコーパスごとに出現する語義の頻度分布が違う場合がある。
  あるジャンルのテキスト中の用例を対象に語義曖昧性解消するときに、そのサブコーパスを使うべきなのか、。。
  これは、DomainAdaptationが必要なの

 2、辞書中に語義がない用例も対象とする
  ネタみたいに見えるけど = ネタが辞書中の語義とは違う意味を持っている


課題設定
 Webページみろ
 岩波国語辞典を使おう

ニュ力
 対象語がマークされたテキスト文書
 文書はBCCWJから
 文書にはジャンルのラベルが付いている

出力
 対象の語義が辞書にあるとき、辞書ID
  ないときは、「new sense」を返す

WSD
新語義の発見

配布データ
GSKを通じて配布、データを配布

夏に、訓練データセットと、スコアラ、入出力フォーマット

** 比喩判定
名詞Aのような名詞B、の比喩性判定モデル

名詞のように

対比される名詞が、前、後ろ、出現しない、のどれかをする。

名詞のように、の後ろに続く用言を使う。

今回は「名詞のように形容詞+名詞」のはたらきを調査する

でも、そもそも「名詞のように」とか「名詞のように形容詞」とかはすごくすくないのである。ちょwwwっw

比喩表現辞典からも、13文しか取り出せない。
 なんでかと思ったら、先頭の1000文しか見ていないからwwwwww

なんとかなんないのか。

形容詞が比喩に与える影響
 焦点をしぼる(分かりやすくなる
 意外性を弱める(比喩性を弱める

形容詞によって、意外性が強まったり弱まったりという視点があるのである。

名詞と形容詞の結びつきをWebで測定することができれば、
意外性のある比喩や、意外性の薄い比喩をだせる?
 出せなかった、、、とか、まじかよ。

** ロジスティック回帰
一番前にきてしまったっっっw

岡野原さんのサイトに論文

背景:クラスタリング
何らかの基準でデータを似た者通しに分類したい

クラスタリングの課題
 クラスタの意味がわからない
  ラベル?
 距離基準が分からない
  違う尺度の方が良いかもしれないじゃないか

従来分類に使われていたロジスティック回帰を使う
距離:log損失関数
任意の特徴を利用可能 & 確率情報を可能

訓練データを利用して最尤推定する。
ークラスタリングではxだけあたえられた
重みwと出力yも最適化で決める

バケツの数kは最初に決めるよ

制約を加えないと、1つのバケツに入ってしまう。ので、
入らないように制約をかける、っていう、無理矢理な感じが良い。

バランスをとるように、クラスタ間の距離がなるべく小さくなるように。
重みとラベルを交互に求めるようにする

----

最適化の際にL1せいそくか

L1正則化
重みをペナルティに使うと
100万個のうち、よく効いている1000個くらいがのこる

計算量がへるよね!

----

文書中の全部分文字列を特徴
極大部分文字列を使う

文書のBOW表現
文書を出現情報で作られた特徴ベクトルにするのは強力

でも、
1、形態素分割とかは形態素解析器依存のエラーが含まれる
2、文書を特徴づける単位と、単語単位が違う可能性がある。

そこで、文書中に出現する全ての部分文字列を特徴として利用する。

長さや頻度で制限は一切しない
部分文字列を全部文書分類に使う研究を岡野原さんがやってる。


出現場所が異なる2回以上出現する部分文字列の種類数は文書長より

Suffixを作る。

入力データをつなげた文字列を考え、
文書の極大文字列列挙に変換する
これを文の変わりに使う。。。

いやあ、すごいなぁ。

MMCに勝てなかったが確率値が出せない。
とりあえず、自分でもこの手法を試さない手はないよなぁ。

どんなものでもシグモイド関数を使えば0.1に落とせる。
しかし、ロジスティック関数をすれば、
ピーキーにならないので、確率値として使いやすい。

極大文字列を必ず使ったほうが良いのか。
 ゴミがめちゃくちゃ含まれるので、
 特徴値の設定がポイント。

ラベルが出力される確率をされる最大化する、っていうのは最尤推定じゃね?

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-03-02 Mon

NLP2009 言語処理学会第15会年次大会 1日目

メモなので後で書き直す。

** p: 本会議1日目 [日記]:
** 小規模な用語リストを利用した画像読影レポートからの用語抽出
Weakly(semi) Supervised Learningで問題
7つの素性で、7つの意味タグを付与
節分割、係り受け、機能語の削除、
ブートストラップの素性セットと、閾値は自動で求める。
繰り返し回数は人間が決める。

結果は初期seedの質と量に依存する。
事前に作成した素性セットの中から、最適なものを選んでくれる。

性能はSupervisedの方が良いにきまってる。
CRFはコンテキストにタグ付けされたデータが十分にあるなら有効。
でも、今回は辞書しか正解にもっていないためSVMで。
今の分類実験はマルチクラスではなく、2値分類で結果を出している。
|Cではなく、|Pにしたらどうなるかは、今後考える。とのこと。

** Character Based Thai Named Entity Recognnition
統語ルールで事前にエラーになりそうな系列を接続する前処理をお濃なる。
liner CRFを使った。素性は前処理を行なったあとのchar-ngram。
ようするに、くっ付けなきゃいけない部分を事前にくっつける発想がいい。
Window Siseが3の時、1,2,3word gramを素性にする。

NERモデルで、文字n-gramを使うと8割り越え。
oracleは、97%くらい
WSモデルでは、NERモデルと同程度。

このような手法には、技術的に顕著な新規性はないが、
タイ語の固有名詞抽出において解決できなかったシラブルの
抽出などの問題を解決できている、という話なんですが。

** 生起確率をもちいた人名判定
外国人名対訳の自動編纂をしたところ、
その誤りの大半は人名以外であった。
人名以外を除去できれば、対訳作成の性能は向上する。
人名っぽい表記条件でフィルタリング
FirstNameとLastName、それぞれの人名っぽさを判定する。
 辞書とサンプルの分布をみて、辞書の方により含まれていると、
 よりFirst、Lastっぽい、尤度が高まる

榊原らの外国人名対訳辞書、というものがある。
サンプルはWikipedia。

FirstNameとLastNameの-1クラスは重要(鈴木佐藤は変、とか分かる。

でも、問題がひとつあるので、解決した。***
区間補正ってのをやる。

両方人名だと+2、片方だと+1、片方が-1、両方が-1=-2

HeiNER辞書ってのがある。

辞書を使う人は人名しか入力しないから問題ないんじゃね?
という話だけど、

検索の実用上は良いんだけど、佐藤先生は
辞書を編纂する立場からすると、辞書を名乗るのに精度9割だと微妙。
しかも再現率は重要。語彙が少ないと困るよね。
より正しい辞書をつくるべきだという持論を展開した。

入力されたクエリの判定をして辞書を切り替えられる場合、とか、
表記だけではなく、読みを使って検索する時のことを考えると、
精度の良い辞書を作ることは重要なんですよね。

これスパム判定に使えるかも

** 固有表現の経年変化と頑健な抽出
調査データはIREXコーパスと毎日新聞記事。
使ったデータには年代にバラつきがある。最新コーパスではない。

固有表現のタグづけには、固有表現の曖昧性、という問題がある。
組織名と地名。国名は全部地名。
新宿西交番は、自首する先だったので、組織名にした。
あいまいさは抽出したデータの1割。

時間、割合、金額表現は、圧倒的に少ない。

固有表現の種類数は年々増加している。

出現傾向が変わっても頑健な抽出ができる学習器。
タグ無しコーパスの低頻度語の周辺語ベクトルを使い、
良く似た分布の別の高頻度葉を選び、素性を抱き合わせる。

タグ無しデータっつうか。

ビル名辞書中からの組織名抽出とかできるな。

** スプログの調査と
スプログの調査。
スプログは閲覧可能、削除済みのブログ。
全ブログのおそらく40%。ぐええ。

アフィリエイト型。特にコンテンツが無い。
ワードサラダ型。自動生成。いろんな情報源から情報を収集。最近は数の増加が伸びていない。
引用型。ニュースサイトからそのままペースト。
工夫した引用型。引用記事のテンプレートにタイトルを挿入する。

引用型はスプログの半数。全体の20%。

では引用ブログを見つけることを目的にしちゃうよ。

類似した記事の定義。
2つの記事の文が30%似てたら類似。
かつ、内容語が80%一致だったら。

全ての分の組み合わせに類似度を計算する。
O(n^2)でつらい。

転置indexを使ってみよう。
単語^t文、文、文。
これを使えば、文テーブルを埋めることができる。

けど、文を単語の頻度の昇順で並べる、
類似度の閾値を用いた枝狩りをする。
上位n語を削ると、DFの高い語は削れる(上位0.1%削るだけでずいぶん良い

実験は、ある時間の投稿された記事集合、
特定のクエリを含む記事集合の2つに適用した。


ワードサラダはエントロピーで判定できるけど
メールはほぼ同じ文面

課題は、ストリーム処理。

まじめな引用ももらさない。
差分の文の意見性や、同じ人間の書く他の記事を見れば良いんじゃね?

他のサイトへの誘導
郵送したいサイトのセお
げとまえ

** 構文木の再起構造
文圧縮の操作として、上位の要素をより下位の要素によって置換することで
圧縮できる。これがあたらしい。
文削除による手法も併用


圧縮分コーパスって言うのがある。

e置換するノード以下がすべて除去されるか、という素性
を加えた。

文圧縮の多様性を考慮。
圧縮文を複数作成し、それらをランキングする。

提案手法は除去すべき無い部分木の誤り除去率が極めて低い。
文法性を極めて良く残している。

削除の有効性を知る、うえではデータ量を増やした方が良い。

再起構造が出現する言語には使用できる。
英語以外の言語には適用できない。

** 施設は位置問題による文書要約のモデル化
AEDがある。AEDは高価。
2つのAEDを町内のどこに配置すると効果的だろうか。
これが施設配置問題。最適化問題の1つ。
同じトピックに対する文書のクラスタを集める。
文書クラスタからどのように文を選択するベキか。

ここで、文から文へのエッジを引く。
エッジは有向きで、子孫ノードは、
祖先ノードがあることで推論できる、と考える。

このような時に、子孫ノードは祖先ノードに割り当てる、ことができる
とすると、これはまさに施設配置問題である。

目的関数、max 各割当の良さeij、実際割り当てたかzij
制約
 選択したかどうか、割当先が選択されていることを保証
 制限長、作成する要約文の長さ制約
 文はかならずどこかに割り当てられる、ことを保証する
 選択文は自分に割り当てる
係数
 各文の長さ;た空くgiven
 制限長:given
 文間係数:

  文から文への推論関係が成り立っていれば、良い割当。

各文の重要さは異なるので、文間係数として文の重要さを表す利得が必要。

重要さ
 文の位置の逆数、文と文書クラスタとの類似度の、重み付き和

あとは整数計画問題のソルバーに投げるだけ。
うひー。

文クラスタリングが類似文を選ぶのに対し、提案は選択文が含意する文を選ぶ
グループ数の決定が不要である
グループ化の選択も逐次ではなく同時におこなう。

おお?これ、他の問題にも使えるんじゃね?

利得は必要である。
非対称な文間係数は必要である。
peer65よりも良いスコアで要約している。

提案モデルの拡張
推論関係のスコアにstate-of the-artを使いたい。
文官のカーネル関数を用いたい。
要約の高速化
2文が1文を推論することもできる

資料ではβをしたけど、とりやめた
部分緩和

誤りを直したページは、たかむら/nlp2009rev.pdf

文間関係の考慮に、接続詞を使うことも考えるべきでは。

PageRankを使った要約と似てない?
PageRankがつながっている文書は重要、という考え方をしているのではなく

エンテイルメント、って

施設配置問題はNP完全なので、近似手法考えることは有用。

--

** 不要文書除去

単語頻度と文書内で最初に出現した位置の利用、より多く前で出ると重要

意味的つながりを考慮した要約作成をする際に、
コスト面や新語の対応についての問題をPLSIで解決する。

より多い文と関連性のある文は重要。
HITS
単語頻度からコサイン類似度を求め、
グラフに対してHITS。
前向きグラフがHub、後ろ向きがAuth

タイトル分とのコサイン類似度ベースグラフPageRank
タイトル文と類似度が高い文を接続していく

要約作成数は6文くらいでサチる。


これらを集約


116に電話。

** 1日目

形態素解析辞書とコーパスがある
辞書に未登録の単語をコーパスから抽出する
活用語は語幹を抽出。
固有名詞は名詞として抽出。

未知語文字列の抽出
 効率
  計算コストの削減
 網羅性
未知語かどうかの検証

力任せは、網羅性は高いが非効率
形態素解析器を利用、効率は良いが、解析エラーの影響でとりこぼす。(既知の単語と未知語の組み合わせになってしまう

前弁別的文字列と後弁別的文字列にはさまれたもの
コーパスに登録されている単語をもとに、さがす。

Online passive aggressive algorithm

コーパス中で頻出する候補を探す。
候補のn-gramも素性にいれる。

** 
新語辞典を作成したい。


活用語尾を観察して十分観察されたら、辞書に加える
活用語尾の定義はあいまい。
最長後続ひらがな列を活用する。
各品詞、各活用型の特徴ひらがな(あまり見られない)列の認定

** p: 語彙獲得のための
テキストから未知語を獲得する。
基本語彙辞書と、自動獲得辞書を用意する。

うざい =>ウ ざい

解決策:異表記ゆれ情報の活用

未知語処理
- 辞書に基づくヒューリスティクス
 かたかな連続を1候補に/
 ひらがな、漢字は1文字ごとに列挙

でも、長いひらがな文字列は解析できない
ようつべ、とか

でも、こういうのは過分割を解決できない。

かぐや姫 → 家具や姫

---

手法
システマティックな誤りを含むN-Gram
仮説
形態素の異表記は同じように振る舞う。

表記揺れの利用:定式化
前向きbi-gramのチェック

** p: 文字誤り
文字単位の誤り
人手の入力や、文字認識に含まれる。

訂正したい!

分野適用能力
 
 	未知語対応能力
 
全誤り種類を扱う能力
 	 置換、削除、挿入、融合、分類

いままでもいろんな研究がある。
けど、文字数の多い日本語に向いてなかった。

--
確率的な文字誤り訂正システムの構築
分野適用が可能である
 ノイジーチャンネル(雑音のある通信路)モデルを使う。
  正しい文Wと、誤りを含む文Oの関係をモデル化

言語モデル確率P
 単語単位のtrigram
未知語モデル
 辞書外の単語候補の尤もらしさを判断する
  未知語、ポワソン

モデルは、数量、かたかな、ローマ字など4つに分けた。

混同モデルP(O|W)

文字混同モデル
 文字誤り傾向は入力方法に依存する
  オCR(図形的)と人手(同音異表記)は別

並列コーパスから学習可能だが大きいコーパスが必要なのだ。

あので


ODR誤り訂正システム

図形的特徴
拡張外郭方向寄与度を用いる

誤りの種類は5種類に分けられる、、、これをLUIGIでやる

実装は重み付き有限状態トランスデューザー




シャグマー



投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-03-01 Sun

NLP2009 言語処理学会第15会年次大会 チュートリアル

メモだから後で書き直す。

** p: NLP2009のチュートリアル、自然言語処理のための知識獲得 [日記]:

教師あり学習には意味知識研究にうまく動かない
- データの作成、コーパスが疎。
- クラスが多すぎる。
- 意味の依存性。


知識獲得に必要な作業
- 言語パターンの的確な発見と収集
- 収集したパターンの名寄せ
- NEの抽出と分類
-- クラスが増えると機械学習では解けない。。

MUC : マック

MUCでは固有のタスクごとに知識を作り直していた。

WSD
意味曖昧性解消。
名詞1動詞名詞2のような文脈で、名詞1が変わると
文全体の意味合いが変わる。

Domain
動詞hitsの意味が名詞2が変わることによって変わる。

Script知識

Semantic Knowledge
- Thing
- Name
- Event

と、要素のマトリクスを作ると
Semantic Knowledge Matrixを作ることができる。

そのまま集めるだけでも面白いよ。
MindNet
- 窓を開ける、という表現が沢山あれば論理が得られる
80個のパターンを集め、パターンから論理への変換ルールで変換
見て面白い

Knext

Knowledge Discovery from Semi-structured data
Wikipedia + WordNet

Tables on web

Active Learning
基本はSupervised。
大量のコーパスを作るのは難しい。
少量のコーパスでうまいことやりたい。
集団について信頼度の一番悪いものについて、
人手で判断することにより、人手の効果を最大化する。

Crowds Clowds?

Mechanical Turk
チープに労働力を探す。

Mechanical Turkは80%の回答者がアメリカ人。
さらに3人の素人の合意は、プロより正確だった。

人手の知識が沢山ある。活用しよう。

Tool!

N-gram search engine
いままではGoogleだったけど、Wikipediaでやろうかな。

N-gramサーチの*に制約を加えてサーチ。
制約を加えると質が良くなるので、加えたい。
かつ早く。とか。
制約を加えている時点で早く検索できるんじゃないかな。

SEMANTIC KNOWLEDGE DISCOVERYのビデオがあるよ。

- Symposium on Semantic Knowledge Discovery, Organization and Use
-- http://nlp.cs.nyu.edu/sk-symposium/

Text Entailment(Ido dagan) vs Paraphrase(Bill Dolan) 

意味知識

Knowledge Discovery
more and more discovery
Domain and/or content dependency
How to handle the scale
Format of knowledge

This effort relates many NLP activities
Comunity effort is needed

知識の作成者と使用者が互いにwin-winとなる場を作ろう。

特殊用途のミニマルな辞書を受け付けて、
その辞書の検索をしてあげるAPIって面白いかもね。

** p: NLP2009のチュートリアル、情報可視化の基礎技術 [日記]:

様々な可視化手法がある
- ネットワーク構造
- 統計グラフ
- 包含関係

科学的可視化Scientific Visualization
みえないもの

可視化の肝
- 直感的に理解できる表示
-- 例、行列に対するグラフ(関連性が分かる
-- 例、数値テーブルのグラフ化(相対性が分かる
- 簡便なインタラクション
-- 直接操作
--- direct manipulation

シュナイダーマンの真言
- 全体を見る前に、拡大や間引きをおこない、見たいところを詳しく眺める

可視化のなかみ
生データ-> 生データから価値が高い情報を抽出 -> 可視化 -> View

Step1 Data Transformation
- Dynamic Queruy(
Brushing and Linking
- 二つの
属性を同時に表示

一風変わった例
Cheroff の顔グラフ:

Step3 : View Tranceformation
手法
- Overview + Detail
沢山のデータを扱うことに適している。
複数のOverview
実装も簡単

- Forcus + Context
ウィンドウの有効利用
全体から部分へのスムーズな遷移
でも、歪んだり、操作が大変だったり。

- ネットワーク表示の可視化
2次元上の可視化。グラフ。
-- バネ埋め込み
-- シンプルで計算量も少なめ

3次元上の可視化。ツリー
-- ツリーマップ
-- 滑らかな3D表現
-- 2Dよりだくさんの情報が扱える

ConeTree : 選択したノードが前に来る
TreeMap : 要素を四角の入れ子にする
InformationCube : 3次元的な入れ子、うげ。

ブラウザの支援
- 2D(Link Driver)
- 2.5D(Data Mountain) :一見3次元だけど高さが無い
- 3D(InfoLead)

Web標識 : あの情報はこっちっていう標識
Metro Map Metaphor : 路線図のメタファー

検索支援のための可視化
KartOO : 関連キーワードと検索結果が、ぐしゃっと出てくる。
Grokker : 検索結果をクラスタ化、円をクリックするたびに詳細に潜り込む
GeoLink : 情報を位置にマッピング
GoogleMap : 現代の情報と地図のマッピング
Grads : 情報推薦。ユーザフィードバックを受けてユーザに与える情報を変える。そのときに、消える動きと、出る動きをハッキリと出している。忍者の技的メタファー。

コミュニケーション支援
仮想空間による現実世界の忠実な再現
SecondLife : 一時期盛り上がったけど。。。
DigitalCity京都 : くそ懐かし
alis : ドリコムのGoogleMap にバターを足したもの

コミュニティ支援のため
Community Organizer : 発言により周囲の人が来たり去ったり
Community Board : メンバー間の関係を可視化しようと頑張ってる

アニメーションの利用
TbVP(Time based Visual Prezentation): 時間軸にそって再生可能な情報を可視化
RSVP(Rapid Serial Visual Presentation) : 特徴的なものをパパパパっと

テキストと可視化
テキストで可視化
- 最初のクエリは手動であたえる。その後は直接操作。

- 探索的データ分析(EDA)
ユーザは欲しい物を知ってるけど、探し方はしらない。どうしよう。
可視化表現を見ることによって欲しい物が分かる、という考え方。

探索(探索と可視化で知識を外在化し、配置する)と
振り返り(外在化された知識を見る)を実現できる。


テキストの内容を可視化
- テキスト同士の関係を可視化
割愛

- 動向情報の可視化
質問の解釈
- 質問の解釈
- 表現の許容範囲
グラフとテキストの横断
データの加工手法
などなど、いろんな課題がある。

----

可視化は同じ仕組みを使っていても、見せ方が変わると別物である。
てっとり早くわかりやすさを得る際には、アニメーションが重要である。

ユーザから入力された言語を解釈することにすると、
UIが煩雑にならず、機能拡張によるユーザに無用なストレスがない。

テキストをインターフェイスに可視化をする際には
要約、といきなりいうのは。。と思ったら
MuSTは要約の部分タスクの消化をしようとしていた。

個人的に自由文と戦うは、ちょっとずれている気がする。

「竹内結子の恋人」みたいなクエリを解釈できるように、
裏側にパーザーを持つのはユーザの利便性を向上すると思う。
でも「竹内結子は最近再婚したのかしてないのか分からないけど、してるとしたら誰ですか?」みたいなクエリを解釈しようと頑張る間に、
他のことをやってユーザの利便性を向上することが出来ると思う。

特にスモールな課題解決に対する定石を固められるために使える
データ作り「も」、MuSTにしていただけると嬉しいと感じた。
複雑なコーパスは質も下がるでしょうし。。。


** p: NLP2009のチュートリアル、ウェブサービスを利用した自然言語処理 [日記]:
言語処理学会第15回年次大会(NLP2009)のチュートリアルに来ています。

- 言語処理学会第15回年次大会(NLP2009)
-- http://nlp2009.anlp.jp/#venue

- 類似文字列検索
例、Yahooビューティー
資生堂 -> a資生堂 = 足制動になってしまう。

- 関連語
例、Yahooタレント名鑑
人物の競演関係から関連タレントリストを抽出。

- 文書分類
例、コンテントマッチAPI
URLに対して商品のカテゴリを割り当てる。
URL中の文章と、事前に学習した分布を比較する。

- 概要
ウェブ検索などのAPIを自然言語処理に活用するためのレシピ。
デモ中心。研究紹介というよりヒント。

- ウェブサービスとは
-- 例、URLにアクセスするとXMLが返ってくる
-- YahooではRESTを使うことが多い。扱いが簡単だから。

- ウェブサービスを使うメリット
「ウェブ全体のデータに、手早く手法を適用する。」

のと、

「ローカルの限られた範囲のデータに、本格的に手法を適用する。」

の、どっちが最適か、ということを議論してメリットがあれば使う。

パイロット版やちょっとおためし、に特におすすめ。

- YDNの紹介
アクセスにはIDとIPに対して制限が与えられる。
大量アクセスする際には別々のIPになるようにしよう。

- 検索オプション
検索オプションの指定は重要。
site、inurl、intitleで検索結果を絞るのは割と重要。

- Tips : 単語の頻度を調べたい
result=1にすると無駄が少なく、高速に調査できる。
XMLはパースしない。正規表現で頻度ゲット!

- 例、Native Chacker
入力にあった、前置詞や助詞を入れ替えたクエリを生成し、
入れ替えた際のヒット数に意味を見いだす。

- Tips: TFIDF的なものを算出する
Yahooの全文書数を、TFIDFを算出する際の文書数Nに使う。

- 例、コピペ検索
単語集合から低頻度名詞を探す。
複数の低頻度名詞をAND検索する。

- Tips :関連ワードを探す
ワードセットを用意し、AとBを取り出す。
A、B、AかつBの3回の検索結果を使い、
それらのヒット数から関連度を算出する。
シンプソン係数とかが使える。

- 例、サイト指定と組み合わせることで、
 とあるサイトがAとBのどちらに詳しいのかを調べたり、
 AさんとBさんのどちらの関連が深いのかを調べたり、。

- Tips : スニペット中の単語頻度を求めよう
スニペットを形態素解析してカウントすれば良い

- 例、タームベクターを計算しよう
クエリに対するスニペット中の形態素頻度を算出する。

- 閑話休題

EReK (English Sentence Search)
  http://erek.ta2o.net/

JReK - Japanese Sentence Search
  http://jrek.ta2o.net/

- 「AやB」というパターンを使う方法
言語パターンを使うことで、2つの語の関係に言及している記事を探す。


- 例、バーサス語を探す
「Aや」で検索しBを見つける。
「Bや」の候補にAが見つかれば、AとBはバーサス関係。とする

- 例、似たものワードを探す
あらかじめ用意したワードセットに対して、
「AやB」で検索する。
「や」や「とか」が精度良い。でも再現率低目。
 
# 関連語を探す言語パターンを評価し、精度を重みにしている。
## 参考文献多数

- ワード間の関係
「関係は分かった!でも、なに関係?」という説明を探したい。

例、IS-A関係
言語パターン「AはBの一種」を使う。
クエリ「"Aは" and "の一種"」で検索する。
得られたスニペットから「AはBの一種」を探しBを取り出す。

# 少し遠回りしたIS-A関係はとるのが大変

- 属性の抽出

例、クエリ「人名 身長 cm」

- カテゴリ分類
各Yahooカテゴリ下に見つかるスニペットとの類似度を算出する。

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-02-21 Sat

「未踏」の2008年度上期 田中・石川PM 合同成果報告会にLuxの発表を聞きにいった

未踏の合同成果報告会でした。最後の報告会っすね。
僕はLuxの発表を聞くためだけに来ました。

背景
 探す、という行為の効率向上が課題
  情報多いし
 オープンソースの重要性

- - - 

Lux
 2008年3月から開発、5月に公開、7月から未踏に専念
 未踏では高速化、データベース、分散インデックスの開発

- - -

特徴
 使いやすさ、機能は、他の全文検索エンジンに劣る部分もある
 性能、分散・スケールアウト性、拡張性は、他の検索エンジンより有利と評価。
- - - 

1、高速化
 高速なデータベース
  Lux IO
 圧縮された転置インデックス
  検索速度を重視した圧縮
- - -
  
2、拡張性
 抽象化
  各層での変更が、多層に影響を及ぼさない構造
 再利用性
  共通部分をフレームワーク
   サーバーデーモンの共通部分(pthreadのサーバ部分、
   クライアントも同じ。
  外部ライブラリの利用
   STL
   libevent
   Google Protocol Buffer

- - -

Strage Interface
Strage Structure Interface 
Strage Structure (論理構造:転置index、ハッシュとか)
Strage Engine Interface 
Strage Engine (Lux IOとか、QDBMとか)

- - -

3、スケーラビリティ
 分散インデックス
  スケールアウトのため
   ドキュメントベースで分散
    全ホストへの問い合せ
  マシンの追加で扱える文書数が、ほぼ線形になるように

- - -

Indexer
Engine -> Strage
Searcher

分散indexのサーチは、dispatcher daemonが全部のindexを見る。

- - -

評価
HEとLuceneはindexにかかる時間、だいぶかかる
SennaとLuxは500万件(6.5G)くらいの文書を追加するときに線形に時間増加
Luxのindexは9Gくらいになった

- - -

単体構成の検索
PageCache無しの場合、
Luxと同じく、線形に劣化するSennaよりだいぶ早い。

PageCacheを使った場合には
Sennaよりも、ちょいと早い。

Luxのindexとsearchが文書数の増加に対して線形に劣化することが分かった。

- - -

複数構成でも、
レスポンスタイムは線形に増加するし、
スループットにも通信時間やIOのオーバーヘッドの悪影響はなかった。

- - -

現状
 Lux
  Sourceforgeに。
  フォーラムもある。
 Lux IO
  これもSourceforge
  各種言語のバインディングを作ってくれている

- - -  

今後の課題
 使ってもらう事が重要。導入先探し。
 開発者を募集している。
 
- - -

今後
 ツールの充実
  使いやすさ向上
 機能やハードウェアを時代に合わせて変化
  SSDが流行って来てるしー、とか

- - -  

質問
 Q、分散機能を使うのは簡単?

  A、Serverのconfigを、各サーバに配布して起動すれば、
  各サーバは担当機能を立ち上げる。
  
  ---

  Q、以前作っていた検索エンジンとの差は?

 A、以前開発に携わっていたのは、
 オンメモリにindexを乗せる検索エンジン。
 
  100台くらいマシンがないと無理。
 そこでディスクベースにした。
 100台くらい無くても1億件の文書を扱える。


山田さん、とりぜあえず、お疲れさまです!!(まだ期間はあるけど。。)

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-02-17 Tue

アルゴリズムデザイン 読書メモ1-2

アルゴリズムデザインを読んでるのですが、
先週に引き続き読書メモがあるので、それを貼っておきます。

アルゴリズムデザイン: Jon Kleinberg, Eva Tardos

[Amazonで詳細を見る]


以下、メモ。

■G-Sアルゴリズム
日本語の助詞が絶対におかしかったり、
言葉が足りないために意味が一意にならない部分を補った。

すべての男性m∈Mとすべての女性m∈Wは自由な身であると仮定する。
Whileすべての女性にはプロポーズしていない自由の身の男性mがいる
 そのような男性mを選ぶ
 wをmの好意順リストでmがまだプロポーズしていない女性の中で、最も好きな女性とする
 mがwプロポーズする
 If wが自由な身である then
  (m, w)は婚約する
 Else
  wは現在m'と婚約しているとする
  If wは、mよりm'が好きである then
   mは自由な身で在り続ける
  Else
   (wはm'よりmが好きである)
   (m, w)は婚約する
   m'は自由な身になる
  Endif
 Endif
Endwhile
婚約のペアの集合Sを返す。


■解答付き演習1の設定
n人の男性と、n人の女性がいる。

各男性は全女性の好意順リストをもち、
各女性は全男性の好意順リストをもっている。

また、2n人の集合は「良い人」と「悪い人」に分けることができる。
良い人は、男女共にk人ずついるとする。

このとき、誰もが悪い人よりも良い人と結婚しようとする。
そのため好意順リストでは必ず良い人が悪い人より先に来る。

とする。

■解答付き演習1の問い
いずれの安定マッチでも、良い男性は良い女性と結婚することになる、ことを示せ。

■「!」:解答付き演習1の解答法のポイント
命題が真で無いと仮定し、その仮定の矛盾点を示す。

■解答付き演習1の解答
「いずれの安定マッチでも、良い男性は良い女性と結婚することになる」が真ではない時として、
「いずれの安定マッチでも、良い男性は良い女性と結婚することになるとは限らない」という状況を仮定できる。

このような仮定が真である場合には、
「良い男性と悪い女性の組」と「悪い男性と良い女性の組」が
少なくとも一組づつ、存在することになる。

このとき、少なくともこれらの組の間には不安定性があると言える。

なぜなら、「良い男性が良い女性と組になりたい」と考えており、
「良い女性が良い男性と組になりたい」と考えており、
良い男性と良い女性のニーズが合致してしまうからである。

最終的にいずれの安定マッチングも、良い人同士が組になり、悪い人同士が組になる。

ゆえに、「いずれの安定マッチでも、良い男性は良い女性と結婚することになるとは限らない」
という仮定は偽であり、仮定は成立しない。
したがって、命題は正しいと言える。

■記号「∈」と「⊆」
前者は、左辺の要素が、右辺の集合の元であることを表す。
後者は、左辺の集合が、右辺の週報の部分週報であることを表す。

■解答付き演習2の設定
禁止されている男女ペアの集合Fがあるとする。
つまりn人の男性の集合Mと、n人の女性の集合Wにおいて、
結婚が許されないペアの集合「F ⊆ M×W」が存在するということである。

各男性mは、すべての(m, w)!∈Fである女性の好意順リストをもち、
各女性wは、すべての(m, w)!∈Fであ男性の好意順リストをもっている。

■解答付き演習2の設定における安定マッチング
以下が、いずれも真ではないときに、一般に安定であると呼ばれる。
ただし、以下の定義では、安定マッチチングが必ず完全マッチングになるとは言えない。

1、これまでと同じ不安定性
(m, w')!∈Fであり、「mはwよりw'が好き」かつ「w'はm'よりmが好き」であるような
2つのペア(m, w)と(m', w')がS(= M×W)に存在する

2、既婚女性と独身男性の不倫の可能性による不安定性
(m', w)!∈Fであり、m'はSのどのペアにも含まれず、
かつwはmよりm'が好きであるようなペア(m, w)∈Fと、m'が存在する。

3、既婚男声と独身女性の不倫の可能性による不安定性
2の反対。省略。

4、未婚の男女の結婚可能性による不安定性
(m, w)!∈Fであるが、Sのどのペアにも含まれないような、
男性mと女性wが存在する。
# 禁止されてなければ結婚するし

■解答付き演習2の問い
どのような好意順リスト、および、禁止ペア集合に対しても、安定マッチングはいつも存在するか?

■「!」:解答付き演習2の解答法のポイント
以下のいずれかで解答を導く

1、任意の好意順リスト、および、任意の禁止ペア集合に対し安定マッチングを求めるアルゴリズムを提案
- より単純な条件を満たすアルゴリズムを動作させ、うまく動いていない部分を変更する。

2、「安定マッチングが存在しないような好意順リスト、および、禁止ペア集合」の反例を与える

■解答付き演習2の解答
1、アルゴリズムの提案

単純な条件を満たすG-Sアルゴリズムを動作させてみる。
すると、「Whileまだ全ての女性にプロポーズしていない未婚の男性mがいる」
というWhileループの条件がうまくいかない。

実際には、「全ての女性」ではなく「すべての(m, w)!∈Fである女性」である必要がある。

そこで、「Whileまだ『すべての(m, w)!∈Fである女性』にプロポーズしていない未婚の男性mがいる」
というように制約を厳しくしてみる。

この場合でも、
G-Sアルゴリズムの定義(1.1)(1.2)(1.3)はそのまま成立する。
また、このような拡張をおこなうと、得られるペアの集合は、
完全マッチングであるとは必ずしも言えない。
そのため、(1.4)以降は検証できない。

従って、本アルゴリズムは「出力が安定マッチングになる」
というところまで言えれば十分だと言える。

付け加えた制約によって、出力が安定マッチングになるかは
「解答付き演習2の設定における安定マッチング」で示した、
4種類の不安定性がいずれも成立しないことを示せば良い。

1、(m, w')!∈Fであり、「mはwよりw'が好き」かつ「w'はm'よりmが好き」であるような
2つのペア(m, w)と(m', w')がS(= M×W)に存在するとき、
アルゴリズム的にはmがwより先にw'にプロポーズしたが断られたことになる。
さらに、「wはm'よりも好きなm」のプロポーズを断ったことになる。
これはアルゴリズムに矛盾するので、この不安定性はない。


2、既婚女性と独身男性の不倫の可能性による不安定性
(m', w)!∈Fであり、m'はSのどのペアにも含まれず、
かつwはmよりm'が好きであるようなペア(m, w)!∈Fと、m'が存在するとすると、
未婚の男性m'がいて、そのm'は(m', w)!∈Fであるwにプロポーズしたが断られ、
かつ、「wはmより好きなm'」のプロポーズを断ったことになる。

3、既婚男声と独身女性の不倫の可能性による不安定性
2を裏返せば良い。省略。

4、未婚の男女の結婚可能性による不安定性
(m, w)!∈Fであるが、Sのどのペアにも含まれないような、
男性mと女性wが存在する場合、アルゴリズム的には
男性mが女性wに告白してしまい、その瞬間wは婚約することになるので、
未婚ではいられない、ゆえに、このような不安定性はない。

■演習問題1
以下の命題は正しいか。正しければ理由を述べ、間違っていれば反例を与えよ。

「安定マッチング問題のどのインスタンス」に対しても、mがwの好意順リストで最高位であり、
かつwもmの好意順リストで最高位であるペア(m, w)を含むような安定マッチングが存在する。

■演習問題1の解答
今回は、「「安定マッチング問題のどのインスタンス」にも、必ずペア(m, w)を含むような安定マッチングが存在する、わけではない」ことを示す例を出す。

m1 : [w2, w1]
m2 : [w1, w2]
w1 : [m1, m2]
w2 : [m2, m1]

このような好意順リストをもつ男女間の安定マッチング問題は、
GSアルゴリズムに従うと、男女が両思いにはならないので、
命題に矛盾する例の一つと言える。

ということで、反例を与えることができた。

■演習問題2
以下の命題は正しいか。正しければ理由を述べ、間違っていれば反例を与えよ。

mがwの好意順リストで最高位であり、かつ、wもmの好意順リストでで最高位である
「安定マッチング問題のインスタンス」に対して、全ての安定マッチングSはペア(m, w)を含む。

■演習問題2の解答

このような「安定マッチング問題のインスタンス」は、
GSアルゴリズムに従って操作してあげるとペア(m, w)ができる。

mからwにアプローチしても、wからmにアプローチしても、
アプローチされた側は、自分の好意順リストの最高位の候補から
告白たのだからそれを受け入れっぱなしになる。

よって、命題は正しいなぁと分かる。

■演習問題3
問題文が長いので省略。

1、任意のテレビ番組の集合と付随する任意の評価点の集合に対して、
安定なスケジュール対を求めるアルゴリズムを与えよ。

2、安定なスケジュール対が存在しないテレビ番組の集合と付随する
任意の評価点の集合の例を与えよ。

■演習問題3の解答

23ページの上から4行目に「以下の2つのいずれかを示せ」と書いてあるので、
(b)の「安定なスケジュール対が存在しないテレビ番組の集合と付随する評価点の集合の例を与えよ」をやってみる。

以下のような評価点の順になっているような集合を考える。

p1 > q1 > p2 > q2

そうすると、p社は「p1 > q1」と「p2 > q2」にしようとするし、
Q社は「p1 > q2」と「p2 < q1」にしようとして、収束しない。

ということで(b)を示せたんじゃないかな。

以下つづく。


「アルゴリズムデザイン 読書メモ」関連エントリ


- アルゴリズムデザイン 読書メモ2-2
- アルゴリズムデザイン 読書メモ2-1
- アルゴリズムデザイン 読書メモ1-2
- アルゴリズムデザイン 読書メモ1-1

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-02-16 Mon

地獄谷温泉

昨日、一日スキーをして、余裕があれば今日も行こうとしたのですが、
寝て起きたら上半身が疲労は取れてませんでした。

なので、行ったことがない地獄谷へ行くことにしました。

地獄谷に一番近い入り口は、地獄谷まで「歩いて20分」の距離にある駐車場にあるコレ。

軽く吹雪いているなか、こんな感じの山道を延々と歩きます。
山道は大人が4人並んで歩けない幅で、かなり狭いです。

地面は凍っており、足を滑らせると谷に落ちてしまいます。
極寒のなか修行をしている気分で緊張しまくり。

手足が冷えきってガクガクしたころに、道が開けて地獄谷に到着。
ここからさらに5分歩いて地獄谷の猿パークまで歩きます。

猿パークの入り口側では温泉が吹き出ており、硫黄の匂いでむせ返っています。

入場料500円を払って中へGO。

おおおお、猿、猿、猿、猿だらけや!


一番奥には、猿の姿を撮影している観光客が沢山います。


この異様な光景を見られただけで大満足です。
寒い中歩いて来た甲斐がありました。


一応、猿に15cmまで近づいて撮影してみました。
猿、怖ぇぇぇ。話とか通じないもんね。


かなり驚いたのが、公苑にいた観光客の持ってるカメラ!
本体もレンズも、僕の目が確かならすごく高額なものばかり。
みんなきっと良い写真が撮れてるんだろうなぁ。


僕は、標準レンズを使っていたんだけど、
どうも締まりが悪いというか、確かに取れるんだけど、
今日はかなりモンヤリとした写真が撮れるので嫌だったです。
もう少し上手に撮れる気がするので、まだ標準レンズで頑張るっす。

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-02-15 Sun

六本木・赤坂でランチ価格は、スキー場並み

スキー場のランチは高い、高い、と言いますよね。

だいたい、こんな感じの値段なんですけど。

この値段を見ているときに、ふと、

「だいたい六本木と一緒だ。」

ということに気がつきました。

六本木・赤坂のランチの高さは一部で有名です。
でも、具体的にどれくらいか実感は湧きにくいものです

「お昼代がスキー場並」と伝えると、
スキー場に行ったことがある人には分かりやすく良いと思います。

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |