新はてなブックマークでも使われてる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に負けていた。しかし、学習が早いというのは実アプリケーシ
How Not To Sort By Average Rating
By Evan Miller February 6, 2009 (Changes) Translations: Dutch Estonian German Russian Ukrainian PROBLEM: You are a web programmer. You have users. Your users rate stuff on your site. You want to put the highest-rated stuff at the top and lowest-rated at the bottom. You need some sort of “score” to sort by. WRONG SOLUTION #1: Score = (Positive ratings) − (Negative ratings) Why it is wrong: Supp
アルゴリズムイントロダクション輪講 #1 が終わりました - ミラクル☆モテメンの脱オタ日記
月曜日にアルゴリズムイントロダクション輪講の第1回を開催しました。http://tokyoenvious.xrea.jp/ria-kyoto/ria-01.pdf が輪講スライドです。輪講中でホワイトボードを使って説明したところもあり (Θ記法のところとか)、資料としては不親切なところもあるかもしれません。 第1巻の最初は基礎部分で、なるべく早めにアルゴリズムそのものに触れたいというのもあり初回だけ一度に 3章分やったのですが、なかなか大変でした。FOR ループの正しさを検証するためのループ不変条件や、アルゴリズムの漸近的効率を記すための漸近記号のところの理解 (特に o や ω) がなかなか難しいようです。 個人的には、漸近記号については p.48 の O 〜 ≦ Ω 〜 ≧ Θ 〜 = o 〜 ω 〜 > という対応がしっくりきましたが、なかなか上手く説明できませんでした。終わった後も
リングバッファ - Wikipedia
リングバッファの概念図 実際のリングバッファ リングバッファ (英: ring buffer)、サーキュラーバッファ (英: circular buffer)、または環状バッファ（かんじょうバッファ）とは、リング状に配置されたバッファである（図を参照）。一時的にデータを貯めておくバッファ領域のうち、終端と先端が論理的に連結され、循環的に利用されるようになっている。最も古い内容を最新の内容で上書きし、常に一定の数の過去までのデータを蓄えるような用途に用いられる[1]。 仕組み[編集] バッファは一般的にメモリ空間効率の高い配列を使って実装されるが、配列を物理的にリング状に配置することはできないので、インデックス（添え字、添え数）をバッファサイズで割って剰余を取る正規化をし、一定の範囲に限定することで、直線状のバッファの両端を論理的に繋げる。正規化により、インデックスがバッファの最後を超えると
マージ - Wikipedia
マージ (merge) は、「併合する」「合併する」という意味合いの英単語である。日本語では、計算機科学や情報工学の文脈でよく用いられる。これらの分野における「マージ」とは、複数のデータベースやファイル、プログラムなどを一つにまとめる行為を意味する。 また、以下で述べるような、二つの線形リストを一つにまとめるアルゴリズムのことをマージアルゴリズムという。 マージアルゴリズム[編集] マージアルゴリズムとは二つの線形リストを一つにまとめるアルゴリズムのことである。主に関数型言語で使用される。 このアルゴリズムは以下のような動作で行う（この例では先頭の値が小さい方を優先することにする）。 二つの線形リスト（、）と空（nil）の線形リスト を用意する。 、 の先頭を調べ値の小さい方のリストの先頭を取り出し、その値を の最後尾に追加する。 、 のどちらかが空になるまで上記の操作を繰り返す。 最後に
Double-Array Articles
ダブル配列のライブラリを公開しているページです． An Implementation of Double-Array Trie URL: http://linux.thai.net/~thep/datrie/datrie.html Darts: Double-ARray Trie System URL: http://chasen.org/~taku/software/darts/ Dame URL: http://www.void.in/wiki/Dame Tiny Double-Array Library URL: http://nanika.osonae.com/TinyDA/index.html Dynamic Double-Array Library URL: http://nanika.osonae.com/DynDA/index.html
アルゴリズムイントロダクション輪講@京都のお知らせ - motemenの日記
2008-08-18 12:19 追記 多数のご応募ありがとうございます。ここでいったん募集を打ち切らせて頂きます。なお、人数の関係で、応募された方からも今回参加できない方が出ることになりますが、あしからずご了承下さい。 社内エンジニアの間に、計算機科学をマジメにやろうという機運が高まっています。それを受けはてな社内で計算機科学に関する教科書の輪講をやろうという話になりました。という訳でまずはアルゴリズムの教科書「数学的基礎とデータ構造 (アルゴリズムイントロダクション)」を輪講してみることにします。はてなスタッフだけでなく社外からの参加も募集しているので、京都オフィスに近い方はぜひご参加下さい。 数学的基礎とデータ構造 (アルゴリズムイントロダクション) 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,Thomas H. Cormen,Clifford Stein,
エイホ–コラシック法 - Wikipedia
エイホ–コラシック法（英: Aho–Corasick algorithm）とは、1975年にアルフレッド・エイホと Margaret J. Corasick が発見した文字列探索アルゴリズムである[1]。 概要[編集] エイホ–コラシック法は、入力テキストについて有限の文字列群（辞書）の各要素を探す辞書式マッチングアルゴリズムの一種である。全パターンのマッチングを一斉に探索するため、そのアルゴリズムの計算量はパターン群の長さに対しても対象テキストの長さに対しても線形であり、さらに見つかったマッチングの数に対しても線形である。全てのマッチングを検出するため、パターン群にサブ文字列があれば、重複して検出される点に注意されたい（つまり、辞書が a, aa, aaa, aaaa で、入力テキストが aaaa の場合など）。 大まかに言えば、このアルゴリズムはトライ木を構築し、サフィックス木的に文字
CodeRepos に nobjdb.js 追加 - 最速チュパカブラ研究会
http://coderepos.org/share/browser/lang/javascript/nobjdb CodeReposに「nobjdb.js」というファイルを追加しました。これは、「syobocalplus」のタイトル検索のルーチンを抜き出し、ライブラリ化したものです。 オブジェクトの集合の中から、文字列検索の結果によって部分集合を抜いてくる処理…… と言うとわかりにくいですが、要するに 購読しているフィードのリストの中をタイトルで検索する(例: LDR) タグクラウドの絞り込み検索(例: はてブ) などという処理です。これを素朴に実装すると for (var i in list) if (list[i].name.indexOf(keyword) >= 0) { // マッチ! } という感じですが、nobjdb.jsでは、ひとつの文字列にタイトルをすべて突っ込んで、 タ
1日で作る全文検索エンジン - Building a full-text search engine in "ONE" day - - とあるはてな社員の日記
最近、「Introduction to Information Retrieval」というStanfordの大学院向け教科書のドラフトを読んでいます。id:naoyaあたりが勉強会で読んでいる教科書です。この教科書には、効率のいい全文検索システムを作るにはどうすればいいか、という(まさに)教科書的手法が網羅的に書いてあり、そのあたりに興味がある人には、非常に興味深く読めるお勧めの本です。 ただ、面白い面白いと言っているだけでは、エンジニアとしては価値半減ですので、GW中にrubyで一日かけて実装してみました。 さすがに実装は、一日で作ったものですから、非常に素朴です。マルチバイト文字はbi-gramで、シングルバイトはスペースなどの区切り記号で認識しています。インデックスは、rubyの処理系のHashやArrayで保持しており、外部にMarshallで書き出す、というものです。検索エンジン
単純ベイズ分類器 - Wikipedia
単純ベイズ分類器（たんじゅんベイズぶんるいき、英: Naive Bayes classifier）は、単純な確率的分類器である。 概要[編集] 単純ベイズ分類器の元となる確率モデルは強い（単純な）独立性仮定と共にベイズの定理を適用することに基づいており、より正確に言えば「独立特徴モデル; independent feature model」と呼ぶべきものである。 確率モデルの性質に基づいて、単純ベイズ分類器は教師あり学習の設定で効率的に訓練可能である。多くの実用例では、単純ベイズ分類器のパラメータ推定には最尤法が使われる。つまり、単純ベイズ分類器を使用するにあたって、ベイズ確率やその他のベイズ的手法を使う必要はない。 設計も仮定も非常に単純であるにもかかわらず、単純ベイズ分類器は複雑な実世界の状況において、期待よりもずっとうまく働く。近頃、ベイズ分類問題の注意深い解析によって、単純ベイズ分
Dynamic Programming による類似文字列マッチの実装例
Dynamic Programming による類似文字列マッチの実装例 2007-01-22-4 [Programming][Algorithm] 「Modern Information Retrieval」(8.6.1 p.216) での Dynamic Programming (DP) の解説のところのアルゴリズムを 素直に Perl で実装したみた。 さらにマッチ箇所取り出しロジックも実装してみた。 # DP はいわゆる「類似文字列検索（あいまい検索）」に使うと 便利なalgorithm。 実は、大学院でも前の会社でも、PerlやらC++やらで実装して使ってた。 単純ながら使い勝手もよく、まさに現場向きかと。 grep 式に頭から見ていくので計算量的にはイマイチなのだが、 転置インデックス検索などで範囲を絞ってから適用すれば実用上問題ない。 ■定義みたいなの Q1. 二つの文字列 "
diff O(np) javascript implementation « ku
昔文書比較アルゴリズムで書かれている G.Myers, W.Miller, An O(NP) Sequence Comparison Algorith をSTLで実装したもの(Edit Distance固定のてきとうなもの)をjavascriptで書き直した。 /* Copyright (c) 2007, KUMAGAI Kentaro Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: 1. Redistributions of source code must retain the above copyright notice, this list of
Web2.0時代の画像補完技術 － ＠IT
2007/08/29 1万枚の写真を使ってできないことで、200万枚の写真ならできることがある。それは熟練したPhotoshopの使い手が1時間かかってやる写真加工の作業を、コンピュータ処理で自動化してしまうこと――。8月初頭に米国サンディエゴで開催された画像処理技術の祭典、SIGGRAPH 2007で発表されたシーン補完技術は、何百万枚もの写真をネットで集められるWeb2.0時代の画像処理技術だ。 写っている邪魔な対象物を自然に置換 「数百万枚の写真を使ったシーン補完」と題した論文と、その成果を発表したのは、カーネギーメロン大学のジェームズ・ヘイズ（James Hays）氏とアレクセイ・A・エフロス（Alexei A. Efros）氏。この補完技術のアイデアは、元となる写真に似た構図や配色の写真を、ネット上で集めた膨大な数の写真データベースから探し出し、元の写真の消したい部分、あるいは復
Bogofilter で日本語を
動機 ずいぶんと前から bogofilter の評価をしているのですが、日本語のメールの判定率がいまいちです。 iconv を使った日本語対応ができるようになっているものの、肝心の単語の抽出ができていないのがいけないのかなぁ…と思い、 bogofilter + kakasi パッチ も最近のバージョンのものは公開されていないようなので、 N-gram による単語分割を組み込んでみました。 N-gram は Unicode のブロックによって N を切り替える複数長 N-gram となっています。 また、プロパティによって記号等を削除（あるいは空白文字に置き換え）を行っているので、判定のノイズの元となるゴミもたまりにくくなっていると思います。 nkf も組み込み可能ですので、パイプで nkf や kakasi を組み合わせないでも bogofilter 単体での日本語メールの扱いができるよう
村上・泉田研究室 ニューラルネットワーク
ネットワークの形態の1つとして、階層型ネットワークがありました。ここでは、階層型ネットワークに対する学習法として有名な誤差逆伝播法について説明します。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
きまぐれ日記: はてなキーワードを高速に付与
RubyForge: Text: Project Info
http://www.greyc.ensicaen.fr/~dtschump/greycstoration/index.html
テクノロジー | キヤノングローバル
