アルゴリズムイントロダクション第24章 単一始点最短路問題 - naoyaのはてなダイアリー
アルゴリズムイントロダクションの輪講で、第24章の単一始点最短路問題を担当しました。発表に使った資料を以下にアップロードしました。 http://bloghackers.net/~naoya/ppt/090622_shortest_paths.ppt SlideShare はこちら。フォントの関係でグラフが崩れたりしているので、ppt で参照した方が見やすいかと思います。 Introduction to Algorithms#24 Shortest-Paths ProblemView more OpenOffice presentations from Naoya Ito. 単一始点最短路問題は、重み付き有向グラフの最短路木を求める問題です。各頂点に最短路重みを記録するのですが、はじめに各頂点の重みを∞として、「緩和」と呼ばれる操作により徐々に頂点の重みを最短路重みに近づけていく、というの
memcachedを超える成果も、Interopで若手技術者がクラウドを支える技術を競う
「日本でゼロからクラウドを生み出すムーブメントを作り出したい」（実行委員長 門林雄基氏）---“クラウドを支える技術”の開発力を競う「クラウドコンピューティングコンペティション」が2009年6月11日、Interop 2009の会場で開催された（写真1）。企業や大学・大学院の研究者、そして高校生を含む若手エンジニアが、新しいアイディアと技術力で作り上げたクラウドコンピューティングの基盤ソフトウエアを披露した。 クラウドコンピューティングコンペティションは、奈良先端科学技術大学院大学の門林雄基准教授らの呼びかけで実現したイベント。若手のエンジニアがP2P（ピア・ツー・ピア）技術や分散データ処理技術といったクラウドコンピューティングの基盤技術を開発し、その成果を競う。検証環境として、情報通信研究機構（NICT）が運用するクラスタ環境「StarBED」のコンピュータを最大1000台まで使用可能で
Thread Base MapReduce - moratorium
Thread Base MapReduce 2007-01-09 (Tue) 0:29 Uncategorized 並列計算フレームワークを作っている人を見てたら自分もなんか作りたくなって来たので、スレッドベースでGoogleのMapReduceを真似て見ました。1マシン用のMapReduceといった所ですかね。 以下にソースコードが有ります。適当に煮るなり焼くなりしてください。 ソースコード ワードカウントが以下のようなコードで記述できます。 [code] class WordCounter : public Mapper { public: virtual void Map(const MapInput& input) { string text = input.value(); istringstream iss(text); string word; while
Ngram(N-gram)とは何か & 形態素解析との比較
全て 1.このサイトについて 2.作品DB開発/運用 3.ホームページ制作技術 4.Perl 5.C言語 / C++ 6.検索エンジン&SEO 7.サッカー 8.自分のこと 9.Linux 10.旅行 11.思ったこと 12.パソコン 13.Berkeley DB 14.その他技術系 15.企画 16.スマートフォン 17.鑑賞 18.皆声.jpニュース 19.インターネット業界 20.運用マニュアル(自分用) 21.技術系以外実用書 22.料理 23.ALEXA 24.アニメ 25.会計 26.漫画 27.設計書 28.色々サイト作成 29.サーバー 30.自分専用 31.生活 32.OP/ED/PV 33.ゲーム 34.DB整備 35.新規開始作品紹介 36.英語圏の話題 37.大道芸 38.映画 39.PHP 40.ダイエット 41.Mac 42.JavaScript 43.MySQ
String::Dictionary - naoyaのはてなダイアリー
String::Dictionary という Perl のライブラリを作ってみました。 http://github.com/naoya/perl-String-Dictionary/tree/master String::Dictionary は検索エンジンその他を作る時に必要になる「辞書」のためのデータ構造 + API です。辞書は単語の集まりですが、これを配列やハッシュなどで持つのではなく、単語をすべて繋げた一つの大きな文字列として保持することでメモリ領域を節約したものです。単語は単に文字列連結で持つだけでなく、Front Coding で圧縮しています。以下簡単な解説です。 辞書は例えば [0] ･･･ jezebel [1] ･･･ jezer [2] ･･･ jezerit [3] ･･･ jeziah [4] ･･･ jeziel ...という風に単語を配列で持つことで実現でき
グーグル株式会社の人が MapReduce (以下 MR)について解説をしてくれるというので聞いてきた - steps to phantasien t(2006-01-27)
2006-01-27 近況 グーグル株式会社の人が MapReduce (以下 MR) について解説をしてくれるというので聞いてきた. 私は友人が誘ってくれたのに便乗しただけの野次馬なので, どういう集りなのかはよく把握していない. 何かの勉強会ということらしい. 技術的には論文に書いてある以上の話はなかったが, 実際に使っている人の話を聞けたのは貴重だった. 忘れないうちにあれこれメモしておく. (発表に使ったスライドはウェブに公開されているものと同じだという. スライドがあるなんて気がつかなかった...) まず MR のマスタープロセスは途中経過や統計情報を HTML として(?) 出力してくれる. そのスクリーションショットがスライドにあった. 進捗などがけっこうグラフィカルに表示される. こういうフィードバックの仕組みは開発生産性に影響しそうだ. (Tapestry の作者がいうと
クラスカルのアルゴリズム - naoyaのはてなダイアリー
昨年からはじめたアルゴリズムイントロダクションの輪講も終盤に差し掛かり、残すところ数章となりました。今週は第23章の最小全域木でした。辺に重みのあるグラフで全域木を張るとき、その全域木を構成する辺の合計コストが最小の組み合わせが最小全域木です。 アルゴリズムイントロダクションでは、クラスカルのアルゴリズム、プリムのアルゴリズムの二点が紹介されています。いずれも20世紀半ばに発見された古典的なアルゴリズムです。 二つのうち前者、クラスカルのアルゴリズムは、コスト最小の辺から順番にみていって、その辺を選んだことで閉路が構成されなければ、それは安全な辺であるとみなし、最小全域木を構成する辺のひとつとして選択します。これを繰り返しているうちに最小全域木が構成されるというアルゴリズムです。 今日はクラスカルのアルゴリズムを Python で実装してみました。扱うグラフは書籍の例を使ってみました。以下
Stephen Marsland
This webpage contains the code and other supporting material for the textbook "Machine Learning: An Algorithmic Perspective" by Stephen Marsland, published by CRC Press, part of the Taylor and Francis group. The first edition was published in 2009, and a revised and updated second edition is due out towards the end of 2014. The book is aimed at computer science and engineering undergraduates studi
プラグインで独自ストレージを作ろう - mixi engineer blog
OpenSocialとかC++0xとか世の中の流れが早すぎて、いろいろと勉強しなきゃなと焦りつつも、ついついピクミン2にはまってしまうmikioです。今回はTokyo Tyrant（TT）を使ってユーザ独自のストレージシステムを簡単に構築する方法について説明します。 プラグインとは オブジェクト指向プログラミングに慣れた人にとっては、インターフェイスと実装を分離することによってプログラムの拡張性や保守性を向上させる技法（データ抽象）は常識ですよね。その考えをさらに進めると、インターフェイスのみをプログラムに記述しておいて、具体的な実装は実行時に割り当てるという、いわゆるプラグイン（plug-in）という技法に至ります。プラグインでカスタマイズできる能力をプラガブル（pluggable）などと言ったりもします。 例えばTokyo Cabinet（TC）では、レコードの挿入、削除、参照といった
Binary Indexed Tree (Fenwick Tree) - naoyaのはてなダイアリー
圧縮アルゴリズムにおける適応型算術符号の実装では、累積頻度表を効率的に更新できるデータ構造が必要になります。もともと算術符号を実装するには累積頻度表が必要なのですが、これが適応型になると、記号列を先頭から符号化しながら、すでに見た記号の累積頻度を更新していく必要があるためです。 累積度数表をナイーブに実装すると、更新には O(n) かかってしまいます。配列で表を持っていた場合、適当な要素の頻度に更新がかかるとその要素よりも前の要素すべてを更新する必要があります。適応型算術符号のように記号を符号化する度に更新がかかるケースには向いていません。 Binary Indexed Tree (BIT, P.Fenwick 氏の名前を取って Fenwick Tree と呼ばれることもあるようです) を使うと、累積頻度表を更新 O(lg n)、参照 O(lg n) で実現することができます。BIT は更
Google が行う様々な実験
前回のブログでは、ユーザーの皆さんに最高の検索体験を提供するための、Google の理念をお話しました。もし間違って入力しても自動修正してくれる「もしかして」や、各検索結果を説明するスニペットなどの単純な機能の背景には、複雑なアルゴリズムが存在しています。Google は、どのアルゴリズムが優れたものなのか検証するために、ごく一部のユーザーの皆さんに新しい機能を試験的に提供する「実験」を行っています。（注：今回のブログ記事では英語での実験の画像を使っていますが、日本でも同様の実験を日々行っています。） 私たちは「実験」をとても大切だと考えていて、検索結果に加えた変更の良し悪しをテストするために幅広く活用しています。 Google では常時 50 ～ 200 にわたる実験を行っています。実験の中には、ページをじっくり見てもほとんど違いが分からないような細かい変更もあれば、一目瞭然のものもあり
Introduction to Information Retrieval
This is the companion website for the following book. Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze, Introduction to Information Retrieval, Cambridge University Press. 2008. You can order this book at CUP, at your local bookstore or on the internet. The best search term to use is the ISBN: 0521865719. The book aims to provide a modern approach to information retrieval from a co
IIR の「効果的な」階層的クラスタリング (nakatani @ cybozu labs)
IR の階層的クラスタリングを試すの続きです。 "efficient" な HAC(hiererachical agglomerative clustering) を実装してみます。 今回は、コード全体をぺたぺた貼り付けるのも見にくいし面倒だしということで、github に置いてみました。 git://github.com/shuyo/iir.git 前回作った corpus パックも commit してありますので、 clone すればいきなり動く、はず。 git clone git://github.com/shuyo/iir.git cd iir/hac ruby hac.rb 4million.corpus おのおの手元でちょこちょこ改変して試してみるには CodeRepos より git の方が向いてるんじゃあないかなあと思ったんですが、git まだ使いこなせてないのでなんか色々
Perceptron を手で計算して理解してみる (nakatani @ cybozu labs)
Perceptron の実装とか見ると、ものすごく簡単なので、本当にこれで学習できちゃうの？ と不安になってしまいました(苦笑)。 こういうときは、実際にパーセプトロンが計算しているとおりに、紙と鉛筆で計算してみて、期待する結果が出てくることを確認してみたくなります。 参照する教科書は「パターン認識と機械学習・上」(PRML) の「 4.1.7 パーセプトロンアルゴリズム」。 短い節です。必要最低限のことを一通り書いてある感じかな。 計算に用いるサンプルですが、手で計算できる規模でないといけないので、論理演算の AND を試してみることにします。 簡単に勉強 ちゃんとした説明は PRML などを見て欲しいですが、とても簡単にまとめます。 ２値の線形識別モデルは、N 次元空間内を (N-1) 次元の超平面(決定面)で分割することで、入力ベクトル x から得られる特徴ベクトル φ(x) が２つ
ビタビアルゴリズム - Wikipedia
ビタビアルゴリズム（英: Viterbi algorithm）は、観測された事象系列を結果として生じる隠された状態の最も尤もらしい並び（ビタビ経路と呼ぶ）を探す動的計画法アルゴリズムの一種であり、特に隠れマルコフモデルに基づいている。観測された事象系列の確率計算のアルゴリズムである 前向きアルゴリズム（英: forward algorithm）も密接に関連している。これらのアルゴリズムは情報理論の一部である。 このアルゴリズムには、いくつかの前提条件がある。まず、観測された事象と隠されている事象は1つの系列上に並んでいる。この系列は多くの場合時系列である。次に、これら2つの並びには一対一の対応があり、1つの観測された事象は正確に1つの隠されている事象に対応している。第三に、時点 での最も尤もらしい隠されている事象の計算は、 での観測された事象と での最も尤もらしい隠された事象の系列のみに依
R de Isomap - 元データ分析の会社で働いていた人の四方山話
RでIsomapを書いてみた。 ただそれだけ。 まだあんまりRのことは分かってないんだけど、for文を使うと明らかに実効速度的に不利であることは判明した。 applyとかでうまく回避するんだろうけど、C言語育ちの私にとっては「行列の全ての要素に何らかの処理を行う」ってなるとすぐにfor文が頭に浮かんでしまう。 というわけで、僕の書いたIsomapには二重ループがやたらと登場してきて実行速度的に速度的に非常にだめだめです。 どうしたものか。 まともに固有値・固有ベクトルを求めてソートをかけるのがめんどくさかったので、主成分分析の関数を代用してみたんだけどこれでいいのだろうか？ まあ、前にPythonで書いたやつと結果が大きく違わないからいいんだろうけど... あと、eigen(A)とprincomp(A)とprcomp(A)で固有値が違う気がするのは俺だけ？ # データ取得 swiss <-
ohmm（オンラインEMによるHMM学習）をリリースしました - DO++
Ohmm-0.01をリリースしました [Ohmm 日本語] [Ohmm English] これは、以前のブログで書いた、オンラインEM法をそのまま素直に隠れマルコフモデル(HMM)に対し適用したライブラリです。 使う場合は、単語（アクセス履歴とかなんでもよい）に分けられているテキストを入力として与えれば、HMMによる学習を行い、結果を出力します。他で利用できるように、パラメータを出力したり、単語のクラスタリング結果を出力します。 HMM自体は、言語情報やアクセス履歴、生物情報（ＤＮＡ）といったシーケンス情報において、前後の情報を用いて各要素をクラスタリングしたい場合に用います。 本ライブラリの特徴はオンラインEMの特徴通り、従来のEMよりも速く収束します。一応標準的な最適化手法（スケーリング、スパースな期待値情報の管理）もいれているので、そこそこ高速に動きます 速度的には100万語、隠れ状
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
これなら分かる最適化数学―基礎原理から計算手法まで
サービス終了のお知らせ
Amazon.co.jp: 階層ベイズモデルとその周辺―時系列・画像・認知への応用 (統計科学のフロンティア 4): 松本隆, 石黒真木夫, 乾敏郎, 田邉國士: 本
