MapReduce - naoyaのはてなダイアリー
"MapReduce" は Google のバックエンドで利用されている並列計算システムです。検索エンジンのインデックス作成をはじめとする、大規模な入力データに対するバッチ処理を想定して作られたシステムです。 MapReduce の面白いところは、map() と reduce() という二つの関数の組み合わせを定義するだけで、大規模データに対する様々な計算問題を解決することができる点です。 MapReduce の計算モデル map() にはその計算問題のデータとしての key-value ペアが次々に渡ってきます。map() では key-value 値のペアを異なる複数の key-value ペアに変換します。reduce() には、map() で作った key-value ペアを同一の key で束ねたものが順番に渡ってきます。その key-values ペアを任意の形式に変換すること
Libicpc - nya3.jp
libicpc チーム kkntkr / Unknown による、ACM-ICPC 向けのアルゴリズムの実装をまとめたページです。 基礎 テンプレート マクロ 計算 ビット演算 実数比較 幾何 基礎 データ構造 内積・外積 回転方向関数 射影 面積・体積 円と円の共通部分 多角形の面積 交差 円と円の交点 円と直線の交差判定 円と直線の交点 凸多角形と線分の包含判定 多角形と点の包含判定 直線と直線の交差判定 直線と直線の交点 直線と線分の交差判定 線分と点の交差判定 線分と線分の交差判定 距離 最遠点対 直線と点の距離 直線と直線の距離 直線と線分の距離 線分と点の距離 線分と線分の距離 多角形 凸包 凸多角形のクリッピング その他 アレンジメント ダイス 三次元幾何 直線と直線の距離 グラフ 基礎 データ構造 最短路 Bellman-Ford Dijkstra Warshall-Flo
期待値最大化法などのあれこれ - DO++
実装よりの話。 近年、Nonparametric Bayes手法が自然言語処理やら機械学習で流行っているのですが測度論とかからスタートするのは大変で、恩恵にあずかりたいがなかなか大変。 で教師無し学習で頻出する期待値最大化法(EM法[英語 wikipedia])を使っている場合、そのコードをちょっと変えるとDPを近似できますよというのを実際試してみると結構うまくいく （ACLのtutorialとかが詳しい） 期待値最大化法では、Mステップでを各パラメーターを正規化する部分があるが、 zのパラメータ = C_{z} / \sum_{z'} C_{z'} (C_{z}はEステップで数えたzの出現回数）、 ここを zのパラメータ = exp Ψ(C_{z}) / exp Ψ(\sum_{z'} C_{z'}) と置き換えるだけでDirichlet Processを使ったものと同じ効果（大きいクラ
Support Vector Machine
最近よく巷で耳にするモノ． SVM， Support Vector Machine， さぽーとべくたーましん． これっていったい，どんなもんなんでしょう． なにやら便利そうなモノらしいので，ちょいと調べて要点をまとめてみようかな，なんて． でも，ただまとめただけだとそのへんの記事を読むのとなんにも変わらないので， コーディングするために必要な知識を中心にまとめてみることにします．
統計的機械学習(Hiroshi Nakagawa)
統計的機械学習 (under construction) 導入ppt pdf 情報の変換過程のモデル化 ベイズ統計の意義 識別モデルと生成モデル 次元の呪い 損失関数, bias, variance, noise 数学のおさらいppt pdf 線形代数学で役立つ公式 情報理論の諸概念 (KL-divergenceなど) 指数型分布族、自然共役 正規分布(条件付き、および事前分布) 評価方法ppt pdf 順位なし結果の評価(再現率、精度、適合率、F値) 順位付き結果の評価 線形回帰と識別ppt pdf 線形回帰 正規方程式 正規化項の導入 線形識別 カーネル法ppt pdf 線形識別の一般化 カーネルの構築法 最大マージン分類器 ソフトマージンの分類器 SVMによる回帰モデル SVM実装上の工夫 モデル推定ppt pdf 潜在変数のあるモデル EMアルゴリズム 変分ベイズ法 Expecta
ワードサラダ技術について
後半部分が重要で、未来の挙動が現在の値だけで決定され、過去の挙動と無関係である ということです。 さて、実例です。たとえば次の文章を考えてみます。 「通信販売大手セシールは９日、生命保険の販売に本格参入する方針を明らかにした。」 まず形態素解析するとこんな感じになります。 通信 名詞,サ変接続,*,*,*,*,通信,ツウシン,ツーシン 販売 名詞,サ変接続,*,*,*,*,販売,ハンバイ,ハンバイ 大手 名詞,一般,*,*,*,*,大手,オオテ,オーテ セシール 名詞,固有名詞,組織,*,*,*,セシール,セシール,セシール は 助詞,係助詞,*,*,*,*,は,ハ,ワ ９ 名詞,数,*,*,*,*,９,キュウ,キュー 日 名詞,接尾,助数詞,*,*,*,日,ニチ,ニチ 、 記号,読点,*,*,*,*,、,、,、 生命 名詞,一般,*,*,*,*,生命,セイメイ,セイメイ 保険 名詞,一般
[を] Dynamic Programming による類似文字列マッチの実装例
Dynamic Programming による類似文字列マッチの実装例 2007-01-22-4 [Programming][Algorithm] 「Modern Information Retrieval」(8.6.1 p.216) での Dynamic Programming (DP) の解説のところのアルゴリズムを 素直に Perl で実装したみた。 さらにマッチ箇所取り出しロジックも実装してみた。 DP はいわゆる「類似文字列検索（あいまい検索）」に使うと 便利なアルゴリズム。 実は、大学院でも前の会社でも、PerlやらC++やらで実装して使ってた。 単純ながら使い勝手もよく、まさに現場向きかと。 grep 式に頭から見ていくので計算量的にはイマイチなのだが、 転置インデックス検索などで範囲を絞ってから適用すれば実用上問題ない。 ■定義みたいなの Q1. 二
きまぐれ日記: Schwartzian Transform でランダムシャッフル
Schwartzian Transform を使って配列をシャッフルする話をみて、なるほどな～と思いつつも、よくよく考えてみるとこれは2つの意味で駄目です。 1. 計算量が O(n * log(n)) であること。 2. ランダムにシャッフルできない。 1. は説明するまでもないので、2の理由を考えてみます。 まず、rand() が 0..k-1 までの k種類の整数から 1 つ数値を返すものとします。配列のサイズが n の場合、 weightの並びの場合の数は k^n 通り存在します。ところが、配列の順列の場合の数は n! です。 ここで何か矛盾点があるように思えてきます。 実際に k = 2, n = 2 の場合を考えて見ましょう。この場合、サイズ2の配列をシャッフルするんですから、 要素を入れ替える場合と入れ替えない場合が 1/2 の確率で出現するのが正しいシャッフルです。 k =
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www-masu.ist.osaka-u.ac.jp/~kakugawa/lecture/2006/fcs/note/slide1/index.html
CSDL | IEEE Computer Society
http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf
2007年第11回PRMUアルゴリズムコンテスト トップページ