Information Retrievalの発表資料 by naoya
Name Last modified Size Description Parent Directory - iir_01.ppt 05-Feb-2008 19:22 274K iir_02_1.ppt 18-Feb-2008 10:42 66K iir_02_2.ppt 08-Mar-2008 16:23 361K iir_03_1.ppt 08-Mar-2008 16:23 508K iir_04.ppt 27-Apr-2008 10:18 1.2M iir_05.ppt 17-May-2008 22:34 707K iir_06.ppt 08-Jun-2008 23:34 799K iir_07.ppt 22-Jun-2008 23:13 627K iir_08.ppt 05-Jul-2008 23:04 863K iir_09.ppt 21-Jul-2008 2
ダイクストラ法（最短経路問題）
ダイクストラ法 (Dijkstra's Algorithm) は最短経路問題を効率的に解くグラフ理論におけるアルゴリズムです。 スタートノードからゴールノードまでの最短距離とその経路を求めることができます。 アルゴリズム 以下のグラフを例にダイクストラのアルゴリズムを解説します。 円がノード，線がエッジで，sがスタートノード，gがゴールノードを表しています。 エッジの近くに書かれている数字はそのエッジを通るのに必要なコスト（たいてい距離または時間）です。 ここではエッジに向きが存在しない（＝どちらからでも通れる）無向グラフだとして扱っていますが， ダイクストラ法の場合はそれほど無向グラフと有向グラフを区別して考える必要はありません。 ダイクストラ法はDP（動的計画法）的なアルゴリズムです。 つまり，「手近で明らかなことから順次確定していき，その確定した情報をもとにさらに遠くまで確定していく
人工無能の作り方
書いた人 INA 人工無能とは？ 人間っぽく話すプログラムのこと。会話を理解しているというよりは、なんかそれっぽいことを話すだけのものが多い。 今回は「日本語のようなものを話す人工無能」を作ってみたので、その簡単な仕組みと工夫した点について少し書いてみることにする。 動機 うちのサークルのメンバーがよく集まってるチャット。とてもマニアックな どうしようもない 会話が繰り広げられているわけだが、ちょっと物足りない。 そうだ！ 萌キャラがいないじゃないか！ 「ないなら作ればいいじゃない？」 材料 MeCab 形態素解析エンジン 難しいことは知らなくても問題ない。 「私は変な人ではない」 ↓ 私 名詞,代名詞,一般,*,*,*,私,ワタシ,ワタシ は 助詞,係助詞,*,*,*,*,は,ハ,ワ 変 名詞,形容動詞語幹,*,*,*,*,変,ヘン,ヘン な 助動詞,*,*,*,特殊・ダ,体言接続,だ,
大規模データ処理のための行列の低ランク近似 -- SVD から用例ベースの行列分解まで -- - 武蔵野日記
id:naoya さんのLatent Semantic Indexing の記事に触発されて、ここ1週間ほどちょくちょく見ている行列の近似計算手法について書いてみる。ここでやりたいのは単語-文書行列(どの単語がどの文書に出てきたかの共起行列)や購入者-アイテム行列(どの人がどの本を買ったかとか、推薦エンジンで使う行列)、ページ-リンク行列(どのページからどのページにリンクが出ているか、もしくはリンクをもらっているか。PageRank などページのランキングの計算に使う)、といったような行列を計算するとき、大規模行列だと計算量・記憶スペースともに膨大なので、事前にある程度計算しておけるのであれば、できるだけ小さくしておきたい(そして可能ならば精度も上げたい)、という手法である。 行列の圧縮には元の行列を A (m行n列)とすると A = USV^T というように3つに分解することが多いが、も
Latent Semantic Indexing - naoyaのはてなダイアリー
情報検索におけるベクトル空間モデルでは、文書をベクトルとみなして線形空間でそれを扱います。この文書ベクトルは、文書に含まれる単語の出現頻度などを成分に取ります。結果、以下のような単語文書行列 (term document matrix) が得られます。 d1 d2 d3 d4 Apple 3 0 0 0 Linux 0 1 0 1 MacOSX 2 0 0 0 Perl 0 1 0 0 Ruby 0 1 0 3 この単語文書行列に対して内積による類似度などの計算を行って、情報要求に適合する文書を探すのがベクトル空間モデルによる検索モデルです。 見ての通り、単語文書行列の次元数は索引語の総数です。文書が増えれば増えるほど次元は増加する傾向にあります。例えば索引語が100万語あって検索対象の文書が 1,000万件あると、100万次元 * 1,000万という大きさの行列を扱うことになりますが、単
新はてなブックマークでも使われてるComplement Naive Bayesを解説するよ - 射撃しつつ前転 改
新はてブ正式リリース記念ということで。もうリリースから何週間も経っちゃったけど。 新はてなブックマークではブックマークエントリをカテゴリへと自動で分類しているが、このカテゴリ分類に使われているアルゴリズムはComplement Naive Bayesらしい。今日はこのアルゴリズムについて紹介してみる。 Complement Naive Bayesは2003年のICMLでJ. Rennieらが提案した手法である。ICMLというのは、機械学習に関する（たぶん）最難関の学会で、採択率はここ数年は30%を切っている。2003は119/371で、32.1%の採択率だったようだ。 Complement Naive Bayesの位置づけは 実装が簡単 学習時間が短い 性能もそこそこよい という感じで、2003年段階にあっても、絶対的な性能ではSVMに負けていた。しかし、学習が早いというのは実アプリケーシ
はてなブックマーク全文検索機能の裏側
そろそろ落ち着いて来たころ合いなので、はてなブックマーク全文検索機能の裏側について書いてみることにします。 PFI側は、8月ぐらいからバイトに来てもらっているid:nobu-qと、id:kzkの2人がメインになって進めました(参考: 制作スタッフ)。数学的な所は他のメンバーに色々と助言をしてもらいました。 はてな側は主にid:naoyaさんを中心に、こちらの希望や要求を聞いて頂きました。開発期間は大体1〜2か月ぐらいで、9月の上旬に一度id:naoyaさんにオフィスに来て頂いて合宿をしました。その他の開発はSkypeのチャットで連絡を取りながら進めてました。インフラ面ではid:stanakaさん、契約面ではid:jkondoさん、id:kossyさんにお世話になりました。 全文検索エンジンSedue 今回の検索エンジンはSedue(セデュー)という製品をベースにして構築しています。Sedu
情報検索ことはじめ〜教科書編〜 - シリコンの谷のゾンビ
2011-01-18追記 教科書編その2 にて2011年版のIR教科書を紹介しています 情報検索(IR)の勉強を本格的に始めて8ヶ月．大体どんな分野があって，どんなことを勉強すればいいのかわかってきた（と思う）．この気持ちを忘れないうちにメモしておこう．以下，若輩があーだこーだ言ってるだけなので，間違いや他に情報があれば，ぜひコメントをお願いします． # ここで述べている情報検索とは，コンピュータサイエンスの一分野としての情報検索です．図書館情報学の側面は一切扱っていません，あしからず． というわけでまず教科書編． 本腰を入れて勉強する場合，基礎づくりのためには教科書選びがいちばん重要だと思っている．自分の知っている限り，情報検索における教科書の選択肢はそれほど広くはない．以下に紹介する本は，情報検索を学ぶ上で「買い」の本．これらを読めば，最新の論文を読めるだけの土台はできるし，専門家と議
第 7 回アルゴリズムイントロダクション輪講会資料: Days on the Moon
すでにニュースでも伝えられている通り、12 月 1 日に第 7 回アルゴリズムイントロダクション輪講会がありました。今回の担当は私だったので、その発表資料を公開します。 中央値と順序統計量 (その 1) 予定 順序統計量とは 選択問題とは 最小値と最大値 平均線形時間選択アルゴリズム 中央値と順序統計量 (その 2) 最悪線形時間選択アルゴリズム 3 つずつのグループに分割した場合 7 つずつのグループに分割した場合 参考文献 中央値と順序統計量 (補足) 4 つずつのグループに分割した場合 6 つずつのグループに分割した場合 Lazy-Select Randomized-Partition スタッフロール 「どうせ後から Web で公開するんだから、PDF とか見るのに手間がかかるものは使ってられないよね。やっぱ時代は XML 複合文書でしょ!」と、数式を表現するのに MathML を使
CRCとハミング符号
今回は，データを伝送した際に生じるビット誤りを検出したり訂正したりする方式について取り上げる。テクニカルエンジニア試験でよく出題されるのは，パリティ方式，CRC方式，ハミング符号方式の三つだ。それぞれの特徴を理解し，問題に取り組もう。 問1 誤り検出方式であるCRCに関する記述として，適切なものはどれか。 ア 検査用データは，検査対象のデータを生成多項式で処理して得られる１ビットの値である。 イ 受信側では，付加されてきた検査用データで検査対象のデータを割り，余りがなければ送信が正しかったと判断する。 ウ 送信側では，生成多項式を用いて検査対象のデータから検査用データを作り，これを検査対象のデータに付けて送信する。 エ 送信側と受信側では，異なる生成多項式が用いられる。 平成16年度秋テクニカルエンジニア（ネットワーク）試験の午前問31 問2 巡回冗長検査（CRC）の特徴に関する記述のうち
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
