アルゴリズム講座/実践編/バックトラック
バックトラック(バックトラッキング)は思考アルゴリズムの王様と言っても過言ではありません。私の知る限り思考プログラムの約90％はバックトラックを使っていると思います。 １．バックトラックの考え 人が行う「試行錯誤という行為」を忠実に実行するように考え出されたアルゴリズムで利用範囲は 広範です。もちろん不得意分野もあります。 複数の未知のものを上手く組み合わせて、ある条件を満たす全体を得るのに、その未知のものを ひとつずつ許される範囲内で「もし、こう仮定して」さらにこの状態から「次に、こう仮定して」 というように仮定から仮定へと強引に突き進みます。 そんなことをすれば大抵は途中で行き詰ってしまいます。その時は1歩戻って(バックトラッキング) 仮定を立て直して、また、突き進みます。総ての仮定に失敗したら、そこからまた1歩戻って新たな仮定 を立て直して同様に進行すれば、やがては解に到達することに
ＫＯＮＡＭＩ、「METAL GEAR SOLID 4」関連セッションレポート
「METAL GEAR SOLID 4」関連セッションレポート その2 次世代機という“理想”と、PS3という“現実”の狭間でもがくエンジニア達 9月9日～9月11日開催 会場：昭和女子大学 「METAL GEAR SOLID 4」関連セッションレポートのその2では、「MGS4」の最大の魅力であるプレイステーション 3のコンピューティングパワーをフル活用して生まれたグラフィックステクノロジーに関連したセッションの模様をお届けする。 「MGS4」の歴史は、2005年の東京ゲームショウで衝撃的なデビューを遂げた実機デモ「TGS-2005 TRAILER」に端を発する。しかし、この時期から追っていたメディアや熱心なファンなら誰でも知っていることだが、「TGS-2005 TRAILER」の映像と、2008年6月12日に発売された製品版の映像は、そのクオリティに明確な差異がある。「TGS-2005
ＫＯＮＡＭＩ、「METAL GEAR SOLID 4」関連セッションレポート
「METAL GEAR SOLID 4」関連セッションレポート その1 戸島サウンドディレクターが明かす“戦場ストリーム”とは何か!? 9月9日～9月11日開催 会場：昭和女子大学 米国西海岸で年に1度開催される世界最大規模のゲーム開発者向けカンファレンスGDC(Game Developers Conference)では、毎年、旬のタイトルが入れ替わる。開発者のニーズに合わせて、1タイトルで多い場合は5つも6つものセッションが開催される。GDC 2008では、「Halo 3」が旬のタイトルとしてもっとも多いセッションが組まれた。CEDEC 2007では、セガの「バーチャファイター V」、カプコンの「ロストプラネット」あたりだろうか。 ただ、CEDECの場合、日程もセッション数も限られているため、1タイトルで複数のセッションが開かれること自体が希だが、CEDEC 2008では、なんと3つもの
西川善司の3Dゲームファンのための「METAL GEAR SOLID 4」グラフィックス講座 職人芸的最適化術によって生まれたPS3最高峰グラフィックスの秘密に迫る(後編)
西川善司の3Dゲームファンのための「METAL GEAR SOLID 4」グラフィックス講座 職人芸的最適化術によって生まれたPS3最高峰グラフィックスの秘密に迫る(後編) 10月24日 収録 会場：ＫＯＮＡＭＩ東京本社 2008年最大のPS3キラーソフトとなった「METAL GEAR SOLID 4(MGS4)」。そのグラフィックスの秘密に迫る3Dグラフィックス講座「MGS4」編の後編は、影生成の話や特殊エフェクト、シェーダーの話題を取り上げていく。また、「PS3専用」として開発されただけに気になる、「MGS4」におけるCELLプロセッサの活用状況についても話を伺った。 ■ 「MGS4」における影生成は? 今世代のゲームらしく「MGS4」は、歴代の「MGS」シリーズと比較すると高度な動的影生成メソッドを実装している。影生成技法としてはデプスシャドウ技法(シャドウマップ技法)の改良形を採用
EventuallyConsistent - 結果整合性
EventuallyConsistent - 結果整合性 目次 この文書について 結果整合性 歴史の話 クライアント側の整合性 サーバ側の整合性 まとめ 結果整合性 この文書について Werner Vogels "Eventually Consistent" の日本語訳です. http://www.allthingsdistributed.com/2007/12/eventually_consistent.html 推敲歓迎: 誤訳, タイポ, 訳語の不統一, そのほか... 近年, データ複製の文脈で 結果整合性(eventual consistency) に関する議論が盛んだ. この記事では大規模データの複製における原則や抽象, 高可用性とデータ整合性のトレードオフに関する話題をいくつか集めてみたいと思う. 現在進行中の分野であり, 全ての定義が最初から明快であるとは思わないでほ
blog.katsuma.tv
greeさんで開催されたKey Value Store勉強会に行ってきました。 時間にして4時間超え、内容も国内のKey-Value Storeなソフトウェアの最前線の話ばかりで相当なボリューム。以下、メモってたのを残しておきたいと思います。（誤字、脱字、内容に誤りを含むものなどありましたらお伝えください）また、発表者の方やプロダクトについて、ざっくり調べてURL見つけられたものについてはリンク張っています。 森さん / 末永さん groonga Sennaの後継エンジン 融通が効かないのがSennaのデメリット スコア算出式のカスタマイズなど Sennaの転置索引 索引の構成部品を自由に組み合わせて使える APIもいろいろ QL DB Low Level memcached互換のkey-value store バイナリのみ対応 計測 クライアント memstorm-0.6.8 mem
Robust PageRank and Locally Computable Spam Detection Features - 日々の勉強の航跡
R. Andersen, C. Borgs, J. Chayes, J. Hopcroft, K. Jain, V. Mirrokni, S. Teng Robust PageRank and Locally Computable Spam Detection Features Proceedings of Fourth International Workshop on Adversarial Information Retrieval on the Web 2008. Apr. 論文の在処 概要 Webのspamに関連した論文。 局所的に計算できるcontribution vector*1の近似を用いて、前半ではspamの発見方法の提案、後半ではRobust PageRankという文字通りPageRankをspamに対してrobustにしたランキングシステムの提案をしている。 cont
Lua/組み込み - assari
Captcha security check mokehehe.com is for sale Please prove you're not a robot View Price Processing
ルービックキューブの解き方(How to solve Rubic Cube)
解法その２ 下段→上段→中段 まだ作ってません。ごめんなさい。 おまけ ここから先は完成したキューブを片手に御覧下さい。 いろんなパターンを作ってみよう！！！ ホームへ戻る
ルービック(3^3)キューブの攻略法
ルービック(33)キューブの攻略法 キューブ王 海永 ここでの説明は簡潔にすぎるかとも思う。詳しい説明はwalk_walkにあります。 [名称] ルービックキューブの面に名前をつける。 South,East,North,West,Top,Bottom or S,E N,W,T,B 小立方体を分類し、分類名をつける。 3面見えるものを3面体。2面見えるものを2面体。1面見えるものを1面体or臍。 3面体に31,32,33,..と番号を付ける。2面体に21,22,23,..と番号を付ける。 [操作] 個別の面を90度右回転する操作を、面の名前と同じ名前で呼ぶ。 S,E,N,W,T,B SをしてEをすることをSEと書く。Sの逆(90度左回転)をS^と書く。 SやEで、2面体は別の2面体位置へ、3面体は別の3面体位置に移動する。2面体が3面体の位置へ行くことはない。 [1点干渉、2点干渉]
GoogleNewsのレコメンドの中身 - UMEko Branding
先日、全体ゼミで発表したときの内容ですが、ここにまとめときます。。GoogleNewsのレコメンドの中身を追った論文の要約です。少し前の全体ゼミで用いた資料です。ソース：Abhinandan Das,Mayur Datar,Ashutosh Garg,Shyam Rajaram,"Google News Personalization: Scalable OnlineCollaborative Filtering",WWW2007不勉強な個所が多々ありますので、誤っている箇所等ありましたら、是非ご指摘ください。 個人的には、最近のモデルベースの手法の勉強・おさらいという意味で用いているので、GoogleNews独自の拡張なり実装の部分の内容が省かれている場合があります。また、データ構造やMapReduceを用いた計算の仕組みの部分は、ここでは省略しています。。一応、 全体像 ・LSH(Lo
ベイズ推定と周辺尤度 - アルゴリズムマニア2.0
最近は周辺尤度の研究をしています。といっても、あまり高度なことはやっていませんので、特筆することはないんですよね（汗）。そこで、先週のセミナーで初心者向けベイズイントロ的な話が面白かったので、そこら辺のことをつらつらと書こうと思います。 そもそもベイズ推定とは何か？ベイジアンな確率モデリングでは（ベイジアンが具体的に何を指すかは不明ですが、今から説明することをベイジアンな確率モデリングと呼ぶことに問題はないと思います）、まず全ての確率変数の同時確率を定義します。ここで確率変数は観測変数と、予測したい変数と、これらを出力しているであろう確率モデルの構造です。ということで、同時確率はのように書けます。ベイジアンな確率モデリングでは未知変数は周辺化して消してしまいます。最後に観測値を条件部分に移した予測変数の条件付き確率を計算します。これがベイズ推定です。 こういう定式化の仕方を普段はしないので
HatebuFriends の仕組み - もしかして: blog.iron’s.jp
学生時代に研究・卒論からの現実逃避の一環で作り、去年の10月頃公開（1度移転）した HatebuFriends について今更書いてみたいと思います。 HatebuFriends とは はてなブックマークのブックマーク情報を利用して、好みが似ているユーザや、興味がありそうなページを推薦します。 棒グラフをクリックすると共通のブックマーク一覧が表示されます。同じページをブックマークしたユーザをハイライトすることもできます。 興味がありそうなページを推薦してくれる機能もあります。 人によって精度の差はあると思いますが、自分ではいい感じに推薦されてきていると思っています。 ユーザ間の関連度計算 同じページをブックマークしていることが多いユーザ同士は、似た嗜好を持っていると考えられます。 特に、ブックマークユーザ数が少ないページのほうが、誰もがブックマークするようなページよりも、ブックマークが
西川善司の3Dゲームファンのためのゲームグラフィックス講座 - 職人芸的最適化術によって生まれたPS3最高峰グラフィックスの秘密に迫る(前編)
西川善司の3Dゲームファンのための「METAL GEAR SOLID 4」グラフィックス講座 職人芸的最適化術によって生まれたPS3最高峰グラフィックスの秘密に迫る(前編) 10月24日 収録 会場：ＫＯＮＡＭＩ東京本社 2008年のプレイステーション 3のゲームシーンにおいて、最大の話題をもたらしたのは「METAL GEAR SOLID 4(MGS4)」だ。これは間違いないだろう。 「メタルギア ソリッド(MGS)」シリーズは海外でも人気の高い作品であり、「MGS4」はこの世界の期待に応えるべく世界同時発売を果たしている。その意味では、世界のゲームシーンにおいても、2008年の話題の中心には「MGS4」があったように思う。 そんな、いわばPS3のベンチマーク的作品である「MGS4」にまつわる様々な開発秘話を、小島プロダクションはゲーム開発者会議の「CEDEC2008」において積極的な情報
しかしSVMも最近は速いらしい - 射撃しつつ前転 改
Complement Naive BayesがSVMより速いよーと主張していたので、SVMもなんか最近は速くなってるらしいよ、という事を紹介してみたい。近年はSVMなどの学習を高速に行うという提案が行われており、実装が公開されているものもある。その中の一つにliblinearという機械学習ライブラリがある。ライブラリ名から推測できる通り、liblinearではカーネルを使うことが出来ない。しかし、その分速度が速く、大規模データに適用できるという利点がある。 liblinearを作っているのはlibsvmと同じ研究グループで、Chih-Jen Linがプロジェクトリーダーであるようだ。libsvmはかなり有名なライブラリで、liblinearにはそういった意味で安心感がある。（liblinearの方は公開されてしばらくは割とバグがあったらしいけど。） liblinearにはL1-SVM, L
『【DiGRA公開講座】モンテカルロ木探索とは何か？』
将棋と比べて囲碁の評価関数を難しくしているのは、 ・将棋の駒は種類ごとに機能と優劣に差があるが、囲碁の石にはそれがない。 ・リバーシにおける角のように、明らかな特徴を持った場所が少ない。 ・支配領域の広さを基準としても、領域が確定するのはゲーム終了時になる。 ・局所的な最善手が全体の最善手ではなく、相手に取らせるためにわざと置く「捨石」というテクニックが常套となっている。 などの点で、さらに上級者の間でしか理解できないような評価基準が存在する。 ・石の厚い薄い 石の厚みは物理的厚さではなく、ある石の配置が全局的に与える影響のこと。 ・形の良し悪し 複数の石の配置の評価。良い形になるように、悪い形にならないように注意することにより、「打ち筋が良くなる」効果がある。ただし「愚形の妙手」も多数存在する。 「代表的な悪い形」 ┼┼┼┼┼┼ ┼┼●┼┼┼ ┼┼●●┼┼ アキ三角 ┼┼┼┼┼┼ ┼┼●
新はてなブックマークでも使われてる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
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
文字列の繰り返しと計算量 - odz buffer
scale out の技術 〜 consistent hashing 編 (cloud 研究会, December 19, 2008)