新はてなブックマークでも使われてる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に負けていた。しかし、学習が早いというのは実アプリケーシ
http://www13.plala.or.jp/kmaeda/winc/en.htm
これで見事に円が描画されるのです。 乗除算を一切使わないと言いながら、乗算を使っているではないか？ と思うような人はいませんよね。 cx とか dx とか変な名前を使っていますが、元ネタは数十年前にアセンブラで組んだプログラムの名残です。 それでは実際に乗除算を一切使わずに円を描画して下さい。 全ソースコード DOS Graph Mode で作成した全ソースコードを提供します。 (^_^;) そのままでは、VC++ の現在のバージョンでは動かないかも知れません。 (；_；) /*★ プレゼンハムで円を描く ★*/ #include <stdio.h> #include <stdlib.h> #include <graph.h> /*プレゼンハム関数*/ void en(short x, short y, short r) { short f,dx,cx; f= r+r+3; c
Needleman-Wunsch algorithmを実装した - 西尾泰和のはてなダイアリー
前に86チャットで誰かがdiffを作ろうとしていて、長さ N, M の文字列に対して素朴に N * M の配列を確保していたせいで大きなサイズの入力でメモリを食い過ぎて破綻していたときに「動的計画法で端から埋めていくんだから、直前の１列だけ取っておくだけでいいでしょ」「いや、後でパスを求めないと行けないから全部持つ必要があるんだ！」「ないよ！パスの根元だけ参照で持っておけばいらないパスはGCで消えるでしょ！」という話をしたんだが、今ちょっと自分でも必要になったので作ってみた。うん、思った通りに動くな。 テストケースに書いてあるけど、実行すると下のような入出力になる。 >>> test("1", "001") in1: 1 in2: 001 (((), (0, 2)), 'D') out1: --1 out2: 001 >>> test("1", "100") in1: 1 in2: 100
Homepage — Modular toolkit for Data Processing (MDP)
News 09.03.2016 MDP 3.5 released! This is a bug-fix release Note that from this release MDP is in maintenance mode. 13 years after its first public release, MDP has reached full maturity and no new features are planned in the future. If you plan to do serious machine learning in Python, use sklearn. Note though that some algorithms, notably SFA and Growing Neural Gas, are only available in MDP. We
TagGridのデータ配置アルゴリズムの簡単な解説 - llameradaの日記
はじめに TagGridでは16000毎のFlickrの写真を、写真のタグにしたがって格子状に配置しています。この配置アルゴリズムについて簡単に説明したいと思います。 基本的なアイデア まず、入力となるのはN個のタグ付きデータとします。また、K種類のタグがあるとします。 TagGridでは、このN個のデータとK種類のタグがそれぞれ平面上に配置されるとします。 データだけでなく、タグも2次元平面上に配置するのが大事な点です。 基本的な考え方としては、あるデータのタグが例えばseaとsunの場合、このデータの位置がseaタグと sunタグの近くになるようにデータとタグを配置します。データは複数のタグを持つので、一番良い配置方法というのは簡単には決定できません。そこで、なるだけ良さそうな配置を求めてみます。 フォーマルな問題定義 基本的なアイデアを、もう少しフォーマルに定義します。 n番目のデー
Javascriptでdiffる ( with 形態素解析 ) (nakatani @ cybozu labs)
Javascript で diff というのはいくつか試された例はあるようですが、まだこれといった決定打は出ていない様子です。 実は diff は見た目ほど軽い処理ではないので、Javascript にやらせるのはこれが結構大変…… diff の計算量は、おおざっぱに言うと比較対象の要素数の二乗に比例し（実際にはそれより小さくすることができるのですが、まあ話のイメージとして）、かつメモリを大量に消費するので、バッチ的な処理に最適化されていない Javascript にはどうしても荷が重いものとなってしまいます。 比較対象の要素数を減らせば当然計算量は減りますが、行単位で比較してもあまり嬉しくない（わざわざ Javascript で処理するということは自然文が対象と思って良いでしょう）。最小の文字単位だとギブアップ。 ということは形態素解析で分かち書きして、単語単位で diff するのが J
Google File System(GFS)技術メモ — ありえるえりあ
* 参照した論文 + http://labs.google.com/papers/gfs-sosp2003.pdf * 特徴 + 安いPC(OSはGNU/Linux)で分散ファイルシステムを構築しています(*注1)。 + PCは壊れるという前提で設計しています(*注2)。このため、分散システムを構成するノードが壊れた時、データが失われないことと、自動で復旧できることに主眼を置いています。 + ファイルシステムを利用する側(アプリ)に、ある程度の想定を求めています。任意の利用ケースに対してそこそこのパフォーマンスを出す(=平均的に良い性能)のではなく、特定の利用ケースで性能を発揮できるように設計しています。 + 性能を発揮できる利用ケースは次のようなケースです。 ++ 主にサイズの大きいファイルを扱う(*注3)。 ++ ファイルへの書き込みは追記(append)が多い(ファイルの一部分を何度
スライド 1
ゲノム情報科学研究教育機構講義 ネットワーク解析特論 ネットワーク計算の諸問題 渋谷 東京大学医科学研究所ヒトゲノム解析センター （兼）情報理工学系研究科コンピュータ科学専攻 tshibuya@ims.u-tokyo.ac.jp http://www.hgc.jp/~tshibuya 今日の内容 ネットワーク計算の諸問題 渋谷 ネットワークを扱った様々な情報科学的な問題 Google マルコフモデル 渋滞シミュレーション 遺伝子制御ネットワーク 遺伝子発見 強連結分解 最短路問題 トポロジカルソート DPより速いアラインメントの厳密解法 A*アルゴリズム、両方向ダイクストラ法 マルチプル・アラインメントの最適解 Google ネットワーク計算の諸問題 渋谷 有名なサーチエンジン 1998年、Larry Page と Sergey Brin が創業 膨大なページデータから的確な
コードクローン
コードクローンとは コードクローンとはソースコード中での類似または一致した部分を表します．コードクローンは，「コピーとペースト」によるプログラミングや，意図的に同一処理を繰り返して書くことにより，プログラムテキスト中に作りこまれます．例えば，約20年間保守されている，ある大規模ソフトウェアシステム（約100万行，2000個のモジュールから構成されている）では，約半数のモジュールに何らかのコードクローンが存在していることが確認されています． コードクローン コードクローンの弊害 一般的に，コードクローンはソフトウェアの保守を困難にする要因の一つである，といわれています．例えば，あるコードクローン上にフォールトが発見された場合に，開発者はそれと対応する全てのコードクローンを確認して，必要があれば全てのコードクローンに同様の修正を行う必要があるからです．特に大規模システムでは，チームによる開発が
HowGoogleEarthReallyWorks - Google Earth の <ほんとの> 仕組み
HowGoogleEarthReallyWorks - Google Earth の <ほんとの> 仕組み 目次 この文書について Google Earth の <ほんとの> 仕組み パート1 終幕: 3D の仮想地球を描画する 基本 より良いフィルタリングを持ち込む さあ本題に入ろう Google Earth の <ほんとの> 仕組み この文書について RealityPrime > How Google Earth [Really] Works の日本語訳です。 推敲添削歓迎: 誤訳、タイポ、不統一、そのほか ... 有名サイト HowStuffWorks.com の記事 "How Google Earth Works" を読んだら, この記事が "それがどれだけスゴいか" や "その使い方" を書くだけで "それが(ほんとは)どんな仕組みで動いているのか" を説明していないこと
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
United States Patent: 7158961
Make3D --- convert your image into 3d 一枚の写真を3Dにする
Boost Graph Library: Brandes' Betweenness Centrality
CiteSeerX
http://wrongway.org/cgi-bin/cube/cubexcgiin?!scrambl1!help
MCL - a cluster algorithm for graphs