おねえさんのコンピュータを作ってみた
まだやってたのか、と言われてしまいそうですが、おねえさんが計算にかけた時間と比べればまだまだです。 『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！ この動画で出てくるおねえさんのコンピュータを作ってみた、というお話。 おねえさんのコンピュータからアクセスできます。 検索アルゴリズム HTML+CSSでコンピュータの画面を再現してみました。Javascriptを組むより、そっちの方に時間がかかった気がする。 経路の描画にはCanvasを使ってます。 この問題は自己回避歩行(Self-avoiding walk)と呼ばれるものらしいです。 単にグラフ上を移動するだけなので、小さいなサイズなら単純な深さ優先検索(DFS)で解けます(大きなサイズで何が起こるのか・・・それは動画で)。 実装では、DFSによる検索プログラムをWeb Workerを使って走らせ、スタートとゴールを
平方根を使わずに高速で２点間の距離を近似する - きしだのHatena
２点間の距離の計算では平方根が必要になりますが、平方根は少し重い計算です。ということで、平方根を使わず、掛け算・割り算・足し算と絶対値・最大・最小だけで距離を近似する方法についての記事を翻訳してみました。 flipcode - Fast Approximate Distance Functions (12:02 補足：おそらく今の標準的なCPUでやる意味はほとんどないと思います。近似のアプローチとして面白いというくらいの話。Z80でやりましょう) 距離関数高速近似 by Rafael Baptista (27 June 2003) ２点間のユークリッド距離を求める計算式は次のようになる。 二次元では次のようになる。 この関数の計算には、平方根が必要になる。これは最近のコンピュータでも高価な計算である。平方根は逐次近似によって求められる。つまり、コンピュータは平方根近似のループを行って、与え
頻出典型アルゴリズムの演習問題としてよさげなやつ - kyuridenamidaのチラ裏
効率的な別解とか存在する問題もあるけど演習によさそうなやつをピックアップ。そのアルゴリズムじゃないと解けないわけではないって問題も多いので注意。(ただ演習するのには都合が良いかなと)※個人的難易度をつけてみました。とても主観的な難易度付けなので気にせず解いてみてください。深さ優先探索・Balls[☆]・Sum of Integers[☆]・The Number of Island[☆]・Block[★]幅優先探索・Mysterious Worm[★]・Cheese[★]・Seven Puzzle[★☆]・Stray Twins[★★]・Deven-Eleven[★★]・Summer of Phyonkichi[★★☆]ワーシャルフロイド法(For 全点対最短路問題)・Traveling Alone: One-way Ticket of Youth[★]・A reward for a Car
アルゴリズムの勉強のしかた - きしだのHatena
この記事で、アルゴリズムの勉強はアルゴリズムカタログを覚えることじゃないよということを書きました。 プログラムの理論とはなにか アルゴリズムの勉強というのは、スポーツで言えば腕立て伏せや走り込みみたいな基礎体力を養うようなもので、「ソートなんか実際に自分で書くことないだろう」とかいうのは「サッカーは腕つかわないのに腕立ていらないだろう」とか「野球で1kmも走ることなんかないのに長距離の走り込みいらないだろう」とか言うようなものです。 Twitterでアルゴリズムの勉強とはなにかと尋ねられて、「アルゴリズムの基本的なパターンを知って、それらの性質の分析のしかたをしって、いろいろなアルゴリズムでどのように応用されているか知って、自分が組むアルゴリズムの性質を判断できるようになることだと思います。 」と答えたのですが、じゃあ実際どういう本で勉強すればいいか、ぼくの知ってる本からまとめてみました。
機械学習超入門IV 〜SVM(サポートベクターマシン)だって30分で作れちゃう☆〜 - EchizenBlog-Zwei
ニーズがあるのかさっぱりわからない機械学習超入門だけどひっそり続けていきたい。 前回は識別関数の基礎であるパーセプトロンの簡単な説明とPerlによる実装を解説した。実はこの時点でかの有名なSVM(Support Vector Machine、サポートベクターマシン)もほぼ完成していたのだ！というわけで今回はSVMをPerlで作ってしまうお話。 参考: これからはじめる人のための機械学習の教科書まとめ - EchizenBlog-Zwei 機械学習超入門 〜そろそろナイーブベイズについてひとこと言っておくか〜 - EchizenBlog-Zwei 機械学習超入門II 〜Gmailの優先トレイでも使っているPA法を30分で習得しよう！〜 - EchizenBlog-Zwei 機械学習超入門III 〜機械学習の基礎、パーセプトロンを30分で作って学ぶ〜 - EchizenBlog-Zwei さて
RPC サーバの遅延リターン - steps to phantasien(2009-07-04)
最近は過労気味でウェブにものを書くこともできない, という話で上司の同情を誘うべく 日本人の労働時間やストレスの実態をまとめた エンドレス・ワーカーズ を読んだら, 自分の労働時間は日本人労働者の上位 2 割から漏れていることを知り愕然とした. あんなに働いたってのに...残業エリートへの道は険しい. 道を進みたいわけじゃないけれど. (平均は越えてたぜ!) いずれにせよ流行からはすっかり脱落しているので, 時流を無視して仕事の話でもしよう. 以前, 会社の blog で RPC の結果をノンブロッキングスタイルで受け取るプリミティブ "弱関数" を提案した. でも試行錯誤の結果, いまは使っていない. C++ での弱参照は意図しないリークを作りやすい. 使いわすれることも多く, 忘れた頃にクラッシュする. 要求は明示的にキャンセルした方がいいことがわかった. (世間はみんなそうやってます
禁断探索法をpythonで
ヒューリスティクスは割と好きだ。スパッととけないものをなんとか現実と折り合いを付けながらよりよい解を見つけるみたいな、なんとも煮え切らない美しさのなさがたまらん。インフォマティクスも似たような香りはする。 特に、「シミュレーションできない学問は学問として未成熟である」という言葉に従うのであれば、創薬研究は（学際領域）と言われている割には未成熟な学問の組み合わせのために発見的な手法の割合が増えすぎるし、精度の高い予測法の誕生もまだまだ先であろう。というわけで、発見的な探索手法は当分有用だし、学際領域故に融合部分での応用が期待されるため、アルゴリズムとしてきちんと押さえておくと色々役に立つ。 メタヒューリスティクスの数理の4章はpythonのコードが載っているので、勉強になる。 第4章 応用 4.1 グラフ分割問題 4.2 最大安定集合問題 4.3 グラフ彩色問題 4.4 巡回セールスマン問題
Web上の膨大な画像に基づく自動画像補完技術の威力 - A Successful Failure
画像内に映り込んだ所望のオブジェクトを排除し、違和感の無い画像を生成するシーン補完技術に関しては近年複数の研究成果が発表されている。しかし中でも2007年のSIGGRAPHにて米カーネギメロン大のJames HaysとAlexei A. Efrosが発表した手法*1はブレークスルーとなりうる画期的なものだ。 論より証拠、早速適用例を見てみよう。本エントリで利用する画像はPresentationからの引用である。元画像の中から邪魔なオブジェクト等の隠蔽すべき領域を指定すると、その領域が補完された画像が自動的に生成される。 アルゴリズム 効果は抜群だがアイデア自体は単純なものだ。Web上には莫大な数量の画像がアップされており、今や対象となる画像の類似画像を一瞬にして大量に検索することができる。そこで、検索された類似画像で隠蔽領域を完全に置き換えてしまうことで違和感の無い補完画像を生成するのだ。
memcachedを超える成果も、Interopで若手技術者がクラウドを支える技術を競う
「日本でゼロからクラウドを生み出すムーブメントを作り出したい」（実行委員長 門林雄基氏）---“クラウドを支える技術”の開発力を競う「クラウドコンピューティングコンペティション」が2009年6月11日、Interop 2009の会場で開催された（写真1）。企業や大学・大学院の研究者、そして高校生を含む若手エンジニアが、新しいアイディアと技術力で作り上げたクラウドコンピューティングの基盤ソフトウエアを披露した。 クラウドコンピューティングコンペティションは、奈良先端科学技術大学院大学の門林雄基准教授らの呼びかけで実現したイベント。若手のエンジニアがP2P（ピア・ツー・ピア）技術や分散データ処理技術といったクラウドコンピューティングの基盤技術を開発し、その成果を競う。検証環境として、情報通信研究機構（NICT）が運用するクラスタ環境「StarBED」のコンピュータを最大1000台まで使用可能で
EventuallyConsistent - 結果整合性
EventuallyConsistent - 結果整合性 目次 この文書について 結果整合性 歴史の話 クライアント側の整合性 サーバ側の整合性 まとめ 結果整合性 この文書について Werner Vogels "Eventually Consistent" の日本語訳です. http://www.allthingsdistributed.com/2007/12/eventually_consistent.html 推敲歓迎: 誤訳, タイポ, 訳語の不統一, そのほか... 近年, データ複製の文脈で 結果整合性(eventual consistency) に関する議論が盛んだ. この記事では大規模データの複製における原則や抽象, 高可用性とデータ整合性のトレードオフに関する話題をいくつか集めてみたいと思う. 現在進行中の分野であり, 全ての定義が最初から明快であるとは思わないでほ
Support Vector Machine
最近よく巷で耳にするモノ． SVM， Support Vector Machine， さぽーとべくたーましん． これっていったい，どんなもんなんでしょう． なにやら便利そうなモノらしいので，ちょいと調べて要点をまとめてみようかな，なんて． でも，ただまとめただけだとそのへんの記事を読むのとなんにも変わらないので， コーディングするために必要な知識を中心にまとめてみることにします．
新はてなブックマークでも使われてる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に負けていた。しかし、学習が早いというのは実アプリケーシ
[メモ] サポートベクターマシン(SVM) - 机上の空論
サポートベクターマシン(以下 SVM) とは ・ニューラルネットワークの一種 ・教師ありクラスタリング SVM の基本的な考え方 ・元々2クラスの線形分離手法として提案される ・単層パーセプトロンに似ているが、SVM はマージン最大化という手法をとっているのがポイント。 ・マージン最大化とは、超平面と学習データの隙間となるマージンをなるべく大きく取ろうというもの。 (ここでいう超平面とは、2つのクラスにぶった切る平面のこと) ・ちなみに超平面と、ちょうどマージンの分だけ離れている学習データをサポートベクトルという。 ・このマージン最大化という考えを取り入れることによって、テストデータの識別精度を高めている。 SVM の発展 ・線形分離不可能な問題への対応 - ソフトマージン(学習データが多少マージンにくい込んだり、反するクラスの空間にくい込んだりしても許す)で対応
自然言語処理における類似度学習(機械学習における距離学習)について - 武蔵野日記
Twitter でグラフ理論に関する話題が上がっていたので、最近調べている距離学習(distance metric learning)について少しまとめてみる。カーネルとか距離(類似度)とかを学習するという話(カーネルというのは2点間の近さを測る関数だと思ってもらえれば)。 この分野では Liu Yang によるA comprehensive survey on distance metric learning (2005) が包括的なサーベイ論文として有名なようだが、それのアップデート(かつ簡略)版として同じ著者によるAn overview of distance metric learning (2007) が出ているので、それをさらに簡略化してお届けする(元論文自体本文は3ページしかないし、引用文献のあとに表が2ページあって、それぞれ相違点と共通点がまとまっているので、これを見ると非
昨年の論文をふりかえる - DO++
新年すっかりあけてました。 今年もよろしくお願いします。 年末年始はドタバタして昨年を振り返られなかったのですが、せっかくなので2008年に読んだ論文で私個人のベスト５を以下に列挙してみます。 D. Sontag, et. al. "Tightening LP Relaxations for MAP using Message Passing", UAI 2008 [pdf] Graphical ModelのMAP推定問題で従来解けなかった規模の複雑さの問題を高速にしかも最大であるという保障付きで解けるようにした。書いたメンバーはこの問題に関するオールスターのような感じ。解く問題は、n個の頂点からなるグラフで、各頂点には変数x1...xnがついていて、各頂点と各枝に対し関数gi(xi)、gij(xi,xj)が与えられた時、∑i gi(xi) + ∑ij gij(xi,xj)が最大となるよう
GC - GCアルゴリズム詳細解説 - livedoor Wiki（ウィキ）
GC¥¢¥ë¥´¥ê¥º¥à¾ÜºÙ²òÀâ ÆüËܸì¤Î»ñÎÁ¤¬¤¹¤¯¤Ê¤¤GC¥¢¥ë¥´¥ê¥º¥à¤Ë¤Ä¤¤¤Æ¾ÜºÙ¤Ë²òÀ⤷¤Þ¤¹ ¥È¥Ã¥×¥Ú¡¼¥¸¥Ú¡¼¥¸°ìÍ÷¥á¥ó¥Ð¡¼ÊÔ½¸ GC ºÇ½ª¹¹¿·¡§ author_nari 2010ǯ03·î14Æü(Æü) 20:47:11ÍúÎò Tweet ¤³¤ÎWiki¤¬Ìܻؤ¹½ê GC¤È¤Ï¡© GC¤ò³Ø¤ÖÁ°¤ËÃΤäƤª¤¯»ö ¼Â¹Ô»þ¥á¥â¥ê¹½Â¤ ´ðËÜ¥¢¥ë¥´¥ê¥º¥àÊÔ Reference Counter Mark&Sweep Copying ±þÍÑ¥¢¥ë¥´¥ê¥º¥àÊÔ IncrementalGC À¤ÂåÊÌGC ¥¹¥Ê¥Ã¥×¥·¥ç¥Ã¥È·¿GC LazySweep TwoFinger Lisp2 Pa
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
404 Blog Not Found:アルゴリズム百選 - 配列を再発明する
2007年12月03日04:00 カテゴリアルゴリズム百選 アルゴリズム百選 - 配列を再発明する アルゴリズムを理解するのに最適な方法は、すでに当たり前のように使われている仕組みを、もう一度時分の手で作ってみることです。ここでは、配列に関するアルゴリズムを再実装してみます。 ここでは、MyArrayというオブジェクトを作って、それに配列としての機能を持たせることにします。まずは基本的な操作ができるようにしておきます。 残念ながらRubyなどと異なり、JavaScriptでは[]を演算子として再定義することは出来ないので、ここではget()メソッドとset()メソッドをその代わりとして用意することにします。また、利便性を考えて、組み込みのArrayに変換するtoArray()メソッドも用意しておくことにしましょう。 function MyArray(){ this.size = argum
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ
Java プログラミング(基礎と応用)