MapReduce - naoyaのはてなダイアリー
"MapReduce" は Google のバックエンドで利用されている並列計算システムです。検索エンジンのインデックス作成をはじめとする、大規模な入力データに対するバッチ処理を想定して作られたシステムです。 MapReduce の面白いところは、map() と reduce() という二つの関数の組み合わせを定義するだけで、大規模データに対する様々な計算問題を解決することができる点です。 MapReduce の計算モデル map() にはその計算問題のデータとしての key-value ペアが次々に渡ってきます。map() では key-value 値のペアを異なる複数の key-value ペアに変換します。reduce() には、map() で作った key-value ペアを同一の key で束ねたものが順番に渡ってきます。その key-values ペアを任意の形式に変換すること
Spaghetti Source - 各種アルゴリズムの C++ による実装
ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない． これらを参考にする方への注意とお願い： これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください． これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください． 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります． 注意！ 現在書き換え中 TODO 分類を正しく行う． 全体的に説明と使い方を詳しく． Verify していないものを Verify． ボロノイ図（いつになることやら……） 基本 テンプレート グラフ
連載：検索エンジンを作る｜gihyo.jp … 技術評論社
運営元のロゴ Copyright © 2007-2024 All Rights Reserved by Gijutsu-Hyoron Co., Ltd. ページ内容の全部あるいは一部を無断で利用することを禁止します。個別にライセンスが設定されている記事等はそのライセンスに従います。
メルセンヌ・ツイスタ - Wikipedia
メルセンヌ・ツイスタ (Mersenne twister、通称MT) は擬似乱数列生成器 (PRNG) の1つである。1996年に国際会議で発表されたもので（1998年1月に論文掲載）松本眞と西村拓士による。既存の疑似乱数列生成手法にある多くの欠点がなく、高品質の疑似乱数列を高速に生成できる。考案者らによる実装が修正BSDライセンスで公開されている。 「メルセンヌ・ツイスタ」は厳密にはある手法に基づいた乱数列生成式（あるいは生成法）の族を指し、内部状態の大きさや周期は設定可能である。以下の長所と短所では、メルセンヌ・ツイスタ自体、よく使われている生成法のMT19937、さらにその実装について、区別することなく述べている。 219937-1 (≒4.315×106001) という長い周期が証明されている。 この周期は、名前の由来にもなっているように（24番目の）メルセンヌ素数であり、保証され
[を] 転置インデックスによる検索システムを作ってみよう！
転置インデックスによる検索システムを作ってみよう！ 2007-11-26-5 [Algorithm][Programming] 転置インデックス[2007-06-17-6]による検索システムの実装は パフォーマンスを無視すれば意外と簡単です。 それを示すために Perl で簡単な検索システムを作ってみました。 検索方式は転置インデックス(Inverted Index)、 ランキングには TF-IDF[2005-10-12-1] を用いました。 検索対象ファイルは一行一記事で以下のフォーマットとします。 [記事ID][SPC][記事内容]\n 記事IDは数字、記事内容は UTF-8 の文字で構成されるものとします。 以下のようなサンプル test.txt を用意しました。 1 これはペンです 2 最近はどうですか？ 3 ペンギン大好き 4 こんにちは。いかがおすごしですか？ 5 ここ最近疲れ
![[を] 転置インデックスによる検索システムを作ってみよう！](https://cdn-ak-scissors.b.st-hatena.com/image/square/af37977ee866988286b95e74fff98500a190545c/height=288;version=1;width=512/https%3A%2F%2Fchalow.net%2Fimages%2Ftcl-logo-25.png){kind=logo}
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。
HTML::Feature - 重要部分を抽出するモジュール - - ダウンロードたけし（寅年）の日記
以前からCPANで公開していたモジュールがあるんですが、日本語での解説ドキュメントがなかったのと、最近大幅にブラッシュアップしたので、せっかくなので紹介記事を書きます。 HTML::Feature - Extract Feature Sentences From HTML Documents 「えいちてぃえむえる::ふぃーちゃー」と読みます。 ブログやニュース記事など様々なHTML文書から「重要部分」を推測して抽出してくれる perl モジュールです。 「重要部分」とはいわゆる「本文」のことですね。本文抽出とか焦点抽出とか色々な言い方があるかと思いますが、まぁ要するに特徴的な部分を推測して抽出するわけです。 どういうものか。 例えばブログ記事からヘッダーやフッター、その他のナビゲーションブロックを除いた「記事らしき部分」だけを切り取りたい、とします。 ぱっと思いつくのは「特定のコメントタグ
文節をどう区切るか
日本語入力プログラムの歴史は、入力の効率を求める歴史でした。初めは「これはペンです」という文章を入力するにも、「これは」で一度変換し「ペンです」でまた変換する方式（単文節変換）や、「これは」と「ぺんです」の間に文節を区切る指示を与える方式をとっていました。やがて、単文節変換や文節ごとに区切り記号を入れる方式から、自動的に文節を区切る連文節変換（複文節変換？）へと進化し、さらには文脈に応じて適切な語を選ぶ用例変換、AI変換が花開き、日本語入力は簡単で効率的になっていきました。 このページは、文節を区切る方法について、現行の日本語入力プログラムでよく使われる方式を解説します。用例変換、AI変換は別項にて解説します。 目次 n文節最長一致法 うしろ向きn文節評価最大法 接続コスト最小法 参考文献・資料 n文節最長一致法 採用している日本語入力プログラム：ATOK、EGBRIDGE、VJEなど。
任意の場所をズームイン：写真合成システム『GigaPan』 | WIRED VISION
任意の場所をズームイン：写真合成システム『GigaPan』 2007年10月18日 サイエンス・テクノロジー コメント： トラックバック (0) Alexis Madrigal 2007年10月18日 写真：James Bell、ステッチ：Scott Telstad 米航空宇宙局(NASA)、米Google社、カーネギー・メロン大学が共同で、普通のデジタルカメラと斬新なアルゴリズムを使って、超高解像度の写真を「生み出す」システムを開発している。 このシステム『GigaPan』については、ワイアード編集部がある建物の屋上から撮影した写真も使ってレビューを行なう予定だが、その前に、手元にある情報をそのまま紹介しよう。 GigaPanは、テキサス州オースティンにある小さな会社、米Charmed Labs社が商品化を進めている[現在ベータ版だが、興味のある人には279ドルで提供している。申し込みは
人工無能を作ろう〜マルコフ連鎖(2接頭語と1接尾語の場合)
すると、上記のようなテーブルが出来あがります。 マルコフ連鎖のアルゴリズムに当てはめる為に、とりあえず文章の出だしの「酢/鶏」を接頭語として選択します。 で、ここからがマルコフ連鎖のメインの部分です。 作成した参考テーブルから、接頭語が「酢/鶏」に当てはまるものを探し、そこから接尾語を選択します。 上記テーブルには「酢/鶏→は」しかありませんので、接尾語は「は」になります。 これで「酢鶏は」と言う文章がとりあえず出来ます。 同じように、前回の接頭語後ろの「鶏」と接尾語の「は」を組み合わせたもの「鶏/は」を新しい接頭語とし、参考テーブルから次に来る接尾語を探します。 すると「鶏/は→好き」と「鶏/は→嫌い」と言う二つの結果が見つかります。 何らかの方法(ランダムなど)でどちらかを選択します。 今回は「鶏/は→嫌い」を選択します。 すると「酢鶏は嫌い」と言う文章が出来ます。 同じ
マルコフ連鎖
第4章 マルコフ連鎖 4.1 確率行列 4.1.1 確率行列 4.1.2 同時確率 4.1.3 同時確率行列 4.1.3.1 例1 4.1.3.2 例2 4.1.4 条件付確率行列 4.1.5 確率行列の式 4.1.6 行列演算 4.1.6.1 例 4.2 マルコフ連鎖 4.2.1 マルコフ連鎖の定義 4.2.2 マルコフ連鎖における同時確率 4.2.2.1 例1 4.2.2.2 例2 4.3 定常性 4.3.1 定常性 4.3.2 非定常的ランダムウォーク 例1 4.3.3 非定常的ランダムウォーク 例2 4.3.3.1 余談(エントロピー増大) 4.3.3.2 余談(ブラウン運動) 4.4 状態遷移図とエルコード性 4.4.1 状態遷移図 4.4.2 エルコード性 4.4.2.1 例 〇 章末テスト
DO++: 教師あり学習の比較
ICML2006に興味深い論文がありました。 "An Empirical Comparison of Supervised Learning Algorithm", Rich Caruana caruana and Alexandru Niculescu-Mizil [link] 90年代初め以降、数多くの画期的な教師あり学習が提案されてきましたが、どれがいいかを包括的に比較したことはあまりありませんでした （文書分類などでは、SVMとAda-boosting 強いねということだったのですが Sebastiani@ACM Survey 2002） 決着をつけようじゃないかということで、11の問題に対してハイパーパラメータも完璧にチューニングして、いろいろな分類器を比較しているみたいです。比較内容は精度や再現率やクロスエントロピーなど様々で、確率を直接出さないやつはsigmoid関数など単調
Face Recognition Homepage - Algorithms
Image-Based Face Recognition Algorithms PCA|ICA|LDA|EP|EBGM|Kernel Methods|Trace Transform AAM|3-D Morphable Model|3-D Face Recognition Bayesian Framework|SVM|HMM|Boosting & Ensemble Algorithms Comparisons PCA Derived from Karhunen-Loeve's transformation. Given an s-dimensional vector representation of each face in a training set of images, Principal Component Analysis (PCA) tends to find a t-dime
良い乱数・悪い乱数
Ｃ言語標準ライブラリの乱数rand( )は質に問題があり、禁止している学会もある。 他にも乱数には様々なアルゴリズムがあるが、多くのものが問題を持っている。 最も多くの人に使われている乱数であろう Visual Basic の Rnd の質は最低である。 そもそも乱数とは 乱数とは、本来サイコロを振って出る目から得られるような数を意味する。 このような乱数は予測不能なものである。 しかし、計算機を使って乱数を発生させた場合、 次に出る数は完全に決まっているので、予測不能とはいえない。 そこで、計算機で作り出される乱数を疑似乱数(PRNG)と呼び区別することがある。 ここでは、特にことわらない限り乱数とは疑似乱数のことを指すとする。 計算機でソフト的に乱数を発生させることの最大のメリットは、 再現性があることである。 初期状態が同じであれば、発生する乱数も全く同じものが得られる。 このことは
自然言語処理研究室 - 長岡技術科学大学 電気系 自然言語処理研究室
ようこそ！ 長岡技術科学大学 電気系 自然言語処理研究室へようこそ。本研究室では、自然言語処理とテキストマイニングに関する様々な研究を行っています。 最近の研究室 国際会議に２件採録されました(9/4) 今年11月にフィリピンのセブ島で開催される自然言語処理に関する国際会議 PACLIC 22に本研究室から２件の論文が採録されましたので ご報告します。 Extracting Troubles from Daily Reports based on Syntactic Pieces [ 国際会議#08PACLIC-kakimoto ] Generating Story Reviews Using Phrases Expressing Emotion [ 国際会議#08PACLIC-ota ] オープンハウスを開催しました(8/25-29) 今年度もオープンハウスを開催して、「人工無
カイ二乗値で単語間の関連の強さを調べる
カイ二乗値で単語間の関連の強さを調べる 2007-09-19-1 [Algorithm][Programming] カイ２乗値を使って単語間の関連度を調べる方法。 つまり、関連語を探すときに、χ二乗値を関連度として使う。 perl によるサンプルコード (chiword.pl)。昔、勉強がてら作ったコード。 #!/usr/bin/perl use strict; use warnings; my %cnt; my $pair_num; while (<>) { chomp; next if /^\s*$/; my @list = sort split(/,/, $_); for (my $i = 0; $i < @list; $i++) { for (my $j = $i + 1; $j < @list; $j++) { next if $list[$i] eq $list[$j]; $c
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Outlier除去によるサポートベクターマシン改良の提案と映像境界検出問題への応用
2007-11-29
http://robotics.stanford.edu/users/nir/Papers/Fr2.pdf
剰余演算子についての愚痴 - nokunoの日記