新はてなブックマークでも使われてる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に負けていた。しかし、学習が早いというのは実アプリケーシ
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
The Danger of Naïveté
In my previous post on shuffling, I glossed over something very important. The very first thing that came to mind for a shuffle algorithm is this: for (int i = 0; i < cards.Length; i++) { int n = rand.Next(cards.Length); Swap(ref cards[i], ref cards[n]); } It’s a nice, simple solution to the shuffling problem: Loop through each card in the deck.Swap the current card with another randomly chosen ca
Fussy's HOMEPAGE
あなたは + 48657人めの訪問者です ようこそFussyのホームページへ Mozillaでしか動作確認をしてませんが、おそらく他のブラウザでも大丈夫でしょう。 当サイトへのリンクはご自由にどうぞ。 散歩中のクッキー(右)とチャコ(左)です Contents Profile 自己紹介と日記のページです。 【随時更新】 Latest Topics ニュースサイトから仕入れた最新情報を集めています。 【毎週日曜日更新】 Algorithm プログラムの作成で使われる様々なアルゴリズムを紹介するコーナーです。 【2024/12/29更新】 Link 知り合いの方のホームページなどを紹介しています。 【2013/12/28更新】 更新履歴 一日一回のクリックで、スポンサー企業が一円の寄付をしてくれます。
とりとめのないパーサー談義 - あどけない話
パーサーに関して、調べたことと疑問を書いておきます。パーサーに詳しい人に答えて頂けると、とても嬉しいです。 チョムスキー階層によれば、以下のような関係が成り立ちます。 正規文法 < 文脈自由文法 < 文脈依存文法 < 制限のない文法 それで、文脈自由文法の中は、こういう関係が成り立ちます。 LL法 < SL法 < LALR法 < LR法 < GLR法 GLR法は、文脈自由文法の全体を解析できる能力を持ちます。 疑問1) GLR法は、文脈依存文法(の一部)も解析できるのか？ LL(1) LL(1)に、収まっているのは XML や Lisp です。 LALR(1) LALR(1)に、収まっているのは、ほとんどのコンピュータ言語です。たとえば、C や Java。 GLR GLRに収まっているのは、C++ です。たとえば、D 言語の「テンプレート再訪」には、以下のように文脈がないと比較なのかテンプ
レコメンデーションの虚実（3）～顧客属性はなぜ追い求められなかったのか
レコメンデーションの虚実（3）～顧客属性はなぜ追い求められなかったのか：ソーシャルメディア セカンドステージ（1/2 ページ） 「顧客の属性」を読み取る方法 連載前回で、協調フィルタリングには顧客同士の行動の類似性を見ているだけで、“顧客の属性を見ていない”という問題があるということを書いた。例えば、妻にプレゼントするために夫が女性用化粧品を購入すると、その後しばらくは女性用化粧品をさかんに勧められるような現象が起きてしまうというようなことを挙げた。そしてこうした顧客の属性を見ていないという問題は、コンテンツフィルタリングでも協調フィルタリングでもカバーできないということも書いた。 「モノを買う」という行動を解析してみよう。バラバラに分解すれば、次の3つに分けることができる。 ・商品の属性（その商品がどのような分野の商品で、どのような名前を持ち、どのような特徴があるのか） ・顧客の属性（顧
ソーシャルメディア セカンドステージ：【第2回】レコメンデーションの虚実（2）?レコメンデーションの分類 (1/2) - ITmedia アンカーデスク
レコメンデーションの代表的手法 レコメンデーションには、いくつかのアプローチがある。とりあえずそのアプローチを俯瞰してみると、おおむね以下の5つに分類することができる。 （1）ルールに基づくレコメンデーション （2）コンテンツベースのフィルタリング （3）協調フィルタリング （4）統計学的なアプローチ （5）行動ターゲティング （6）ソーシャルネットワーキング ひとつずつ説明していこう。 （1）のルールに基づくレコメンデーションというのは、「ビジネスルール方式」とか「インテンショナル（意図的な）レコメンド」などと言った呼び方もある。例えば「美容室に髪を切りに来た人に、ヘアケア製品を勧める」「プリンターを買った人に、インクトナーを勧める」など、最初に「ある製品を買った人、ある行動をした人には、この製品やサービスを勧める」というルールを定めておく方法だ。このレコメンデーションはわかりやすいけれ
レコメンデーションの虚実（1）〜認知限界をどう乗り越えるのか (1/2) - ITmedia アンカーデスク
【新連載】レコメンデーションの虚実（1）～認知限界をどう乗り越えるのか：ソーシャルメディア セカンドステージ（1/2 ページ） ネット情報増大と認知限界 インターネットの情報は、今や洪水のようになっている。この洪水の中からどのように有用なコンテンツやデータをすくい上げるのかは、インターネットにおける最も重要なテーマだ。この問題を解決するアーキテクチャとしては検索エンジンが長く定番だったが、情報のオーバーロード（過負荷）が起きている中で、検索エンジンだけでは対応しきれなくなった。 つまりはネットの情報の総体が、人間の認知能力をはるかに超えてしまっているということだ。これを「認知限界」という。認知限界というのはもともと、1978年にノーベル経済学賞を受賞したアメリカの経営学者、ハーバート・アレクサンダー・サイモンが企業などの組織を説明するために使った言葉である。外の世界がどんどん複雑になってく
第10回 麻雀の役を判定する：ITpro
図1に示す(1)から(3)までの麻雀（マージャン）の手牌があります。「あがり牌」はすべて山からツモったものとし，リーチはかけていません。またドラやハイテイ＊1なども関係ないものとします。これらの役を判定して，親の場合の点数を計算するプログラムを作ってください。 「ややこしや～ややこしや～」というのは野村萬斎ですが，思わずそううなってしまうことがプログラミングをしているとよくあります。今回の麻雀の役判定は，考えれば考えていくほどややこしく，そうしたものの代表と言えるでしょう。排他処理や優先順位が複雑にからんでいて一筋縄ではいきません。 今回はややこしい組み合わせを解決する方法を考えてみます。麻雀になじみのない方も，ちょっとしたパズル気分で試してみてください。 麻雀の役を考える 麻雀を知らない方のためにルールをおおざっぱに説明しておきましょう＊2。麻雀の牌には，大きく分けて「萬子（マンズ）」「
Towards a Scalable Non-Blocking Coding Style（状態遷移機械の設計に関して）
Webinar: Managing the Security and Commercial Impact of Java Updates March 12, 2020 Live WebinarJoin Azul and SoftwareONE for this webinar about the security and commercial applications of Java...Read More dev.next March 24-27, 2020 Broomfield, CO, USAAzul is one of the sponsors at this event which brings together practitioners, experts, and...Read More
Sorting a million 32-bit integers in 2MB of RAM using Python
Ramblings through technology, politics, culture and philosophy by the creator of the Python programming language. Someone jokingly asked me how I would sort a million 32-bit integers in 2 megabytes of RAM, using Python. Taking up the challenge, I leared something about buffered I/O. Obviously this is a joke question -- the data alone would take up 4 megabytes, assuming binary encoding! But there's
画像圧縮アルゴリズム (10) 算術符号化
Range Coder復号化処理による数直線の変化は、以下のようになります。 復号化の場合、数直線は常に0からRangeまでの範囲になります。符号が数直線上のどこに位置しているのかをチェックして、Rangeを復号化されたデータが持つ範囲に変換するところは、やはり算術符号化での処理と本質的に変わりありません。 処理方法は以上になりますが、ここでいくつかの問題を解決する必要があります。まず一つは、符号化と復号化での計算で使用している変数Range / Sizeが0になる可能性があるということで、このときはRangeを計算した結果が0になってしまうため、処理を続けることができなくなります。よってRangeの取り得る最小値は、データのサイズより大きくなければなりません。Range / Sizeが0になった場合、サンプル・プログラムでは単純にエラー終了しています。Rangeの最小値はサンプル・プログ
フィボナッチヒープ - Wikipedia
フィボナッチヒープの例。次数0，1，3の3つの木を持つ。(水色で示されている)3つの頂点はマークされている。それゆえにヒープのポテンシャルは9である。 フィボナッチヒープはminimum-heap propertyを満足する木の集まりである。つまり、ある子のキーは常に親のキーよりも等しいか大きい。つまり最小のキーは常に何れかの木のルートにある。二項ヒープと比較してフィボナッチヒープの構造はより柔軟である。木は規定された形を特に持っておらず、極端な場合はヒープ中の n 個の要素が全て別々の（n 個の）木に属しているかもしれないし、深さ n の一つの木に属しているかもしれない。この柔軟さによって、ある種の操作を後回しにするなど「怠惰な」処理方法が許される。例えば、二つのヒープを結合するには単に二つのヒープの木のリストを連結するだけで良いし、「キーの減算」操作の過程ではあるノードが親から切り離さ
DO++: 左傾赤黒木
漢字で書くと仰々しいが、赤黒木 (wikipedia) red-black tree (english wikipedia)という平衡二分木で最も多くつかわれているデータ構造の、改善版が出てたそうだ。 left-leaning red-black tree (pdf) 日本語に訳すと左傾赤黒木かな。簡単な漢字を並べている感じがしてしまう 赤黒木の詳細については、wikipediaなどをよんでもらうとして、これは更新時間が定数で更新箇所が局所的（これはマルチスレッドとかでロックする箇所をかなり細かい単位で、できるという強い利点もある）のだが、実装が結構面倒くさい。例えばC++ stl のmapとかの赤黒木の実装のstl_tree.h(google code search)は大変なことになっている（特にRb_tree_rebalance_for_eraseとか） 赤黒木というのは動的データ構造
高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」
はじめに 大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するのは2003年に提案されたデータ構造、wavelet tree（以下「WT」と表記）です。WTは圧縮索引やSuccinct Data Structureなど、データをコンパクトに表現する際に重要なデータ構造です。WTは文字列T[0...n-1]が与えられた時、次の2つの操作を定数時間でサポートします。 rank(p, c)――T[0...p]中のcの出現回数を返す select(i, c)――(i+1)番目のcの位置を返す WTの作業領域量は、文字列をそのまま保存した時の約2倍程度です。 対象読者 C++の
ICP(Iterative Closest Point)のアルゴリズム - かみやんの技術者ブログ
つくばチャレンジ２００７の出場者の技術資料にICPを使っているという人が何人かいたので、僕もICPを採用することにしました。という訳でまずはICPについて調べました。 ICPはパターンマッチングの１種なので、ちょっと人工知能的。手書き認識とか、OCRとか、音声認識とか、顔認識とかジェスチャー認識も多くはパターンマッチングが使われる。やっとソフトウェアらしい自分の領分なので楽しい。 『Efficient Variants of the ICP Algorithm』この論文が、ICPの様々なアルゴリズムについて検証していてよい感じでした。3Dのレーザーレンジファインダから得られる２つのメッシュの合成について書かれています。 この論文は、主にいろいろなアルゴリズムを試験して、何が高速であるかを検証しています。 概要 概要としては、ICPは以下の６つのステージからなります。 Selection :
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
vincent krutler
http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html
サービス終了のお知らせ
teacup. byGMO サービス終了のお知らせ｜GMO MEDIA
