コンピュータサイエンス史上最大の課題「並列処理による性能向上」～情報処理学会創立50周年記念全国大会の招待講演
「いま、並列処理の壁というコンピュータサイエンス史上最大の課題に直面しています。しかしこれはチャンスでもあります。新しい時代を切り開いていきましょう」。IBM名誉フェローのFran Allen氏は、昨日3月10日に行われた日本の情報処理学会創立50周年記念全国大会の招待講演の演壇からこんなメッセージを聴衆に投げかけました。 Fran Allen氏は、コンパイラやプログラミング言語が専門で、女性で初めてチューリング賞を受賞した人。今回の招待講演のためにわざわざ来日したと紹介されました。 講演のタイトルは「The Challenge of the Multicores」。ここからは、Allen氏の講演の内容を紹介しましょう。 （この講演は英語で行われたものです。内容にはできるだけ正確を期したつもりですが、理解不足のところや聞き取れなかったところもありました。もし誤解や不正確なところがありました
Ruby でパターンマッチ - まめめも
ref: 未来の国のアリス - d.y.d. で紹介されている implicit future が Ruby に欲しい！ # promise を作る x = Promise.new a = [1, x, 2, x, 3, x] # 今はまだ値になっていない p a #=> [1, _promise_, 2, _promise_, 3, _promise_] # この promise は 42 に決めた！ (代入ではないよ) x === 42 # x の箇所は勝手に 42 になっている p a #=> [1, 42, 2, 42, 3, 42] というのも、これがあれば Ruby でパターンマッチができる気がするんですよね。こんな感じに。 # 何にでもマッチする箇所には _ と書く (実体は Promise.new) def _ Promise.new end # + と定数だけからなる抽象
ベイズ理論 - yasuhisa's blog
同時確率、条件付き確率からベイジアンアップデートまで。パラメトリック、ノンパラメトリック(データサイズが増えるにつれて、パラメータ数が対数オーダーで増える)のところは初めてだとたぶんわけわからないところで、ちょっと前で説明してみたけど、若干でしゃばりすぎた気がする。どうするべきかちょっと迷うところではある。難しい。 ベイジアンな考え方は、自分もちゃんと理解するまで3ヶ月はかかったので(パラメータの事前分布ってなんですか!!とか)、今日初めてという人はたぶんわけわからなかったかもなーと(宗教なので、最初は受け入れ難いものなんですよ、きっと)。コインの例のやつは、自分も最初よく分からなかったので、Rで事後分布がupdateされていく様子とかをRで書いたりしていました。 ベイズの事後分布と事後予測分布を出してみた - Seeking for my unique color. FSNLPの例は分か
さあ、Yコンビネータ(不動点演算子)を使おう！ - よくわかりません
前回、おとうさんにもわかるYコンビネータ！(絵解き解説編) - よくわかりませんというエントリで、Yコンビネータ(不動点演算子)と再帰の絵解き解説をしました。 Yコンビネータ自身は、結局のところ再帰を産み出してくれるだけです。関数(正確にはλという単純な文字列変換ルール)だけで出来て、プログラミングに関するいろんな原理の研究を可能にするのが凄い訳です。その辺のさわりを、きしださんが解説されています。しかし、単なる再帰なら、実際のプログラミングではYコンビネータなんて使わなくても出来ます。 じゃあ、Yコンビネータとか不動点とかは、偉い学者さんとかが研究に使えばいいもので、普通のプログラマには何の意味もないモノなのでしょうか？ というわけで、今回はポジティブに、Yコンビネータや不動点で出てくる考え方を、理論だけじゃなく、実際のプログラミングに応用する例を見てみましょう。 今回、プログラムの例を
おとうさんにもわかるYコンビネータ！(絵解き解説編) - よくわかりません
先日YコンビネータのきしださんのYコンビネータのエントリが話題になっていました。 ずいぶん日にちが経ってしまいましたが、自分も、自分なりにYコンビネータのあたりを絵解きで整理してみたいと思います。きしださんのエントリタイトル*1に引っ掛けて、目標として、自分の父親(非プログラマ。その辺のおっさん)でも解る内容を目指します。 なぜ不動点演算子というのか、不動点だったらなぜ再帰なのか、この辺りも含めて、実感を持って納得できればいいなと思います。 きしださんのエントリのおさらい 本題の前に、きしださんのエントリをおさらいしておきます。 Yコンビネータはただのオモチャじゃないんだよ 関数だけで色んな事が出来る 条件分岐をする関数ってのもある。 再帰(ループ)を作れる関数もある。←これがYコンビネータ。 数値も関数で表現できる。 つまり、関数だけで、条件分岐も、再帰(ループ)も、数値も作れちゃう！！
肉厚と抜き勾配をおさえるべし！（1/3） － ＠IT MONOist
本連載「100円均一でモノの仕組みを考える」では、実際に100円均一ショップで販売されている商品を分解／観察して、その仕組みや構造を理解しながら、製品開発の過程を考察していきます。連載第12回のお題は、文房具の定番商品の1つ「テープディスペンサー」です。
正規表現で素数判定 - NO!と言えるようになりたい
追記：ハッキリ言ってこの正規表現はネタなので，実際に素数判定を行いたい場合は，もっと別な賢いアルゴリズムを使ったほうが良いです 正規表現で素数が判定できるという記事を見たので試してみた． http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/ この記事によると /^1?$|^(11+?)\1+$/ という正規表現を使うと，素数判定が出来るらしい．ある整数 n が素数かどうか判定したい場合は，"1" * nという文字列がこの正規表現にマッチするかどうかを調べればよく，マッチすれば非素数，マッチしなければ素数となる．ただし，"1" * n は，例えば，n が 4 ならば "1111" と 1 が 4 回連続して続く文字列となる． Rubyで書いた素数判定プログラムはこん
Unix Magazine「インターフェイスの街角」
Unix Magazine「インターフェイスの街角」関連資料 掲示板 2006年4月号 「写真の位置登録」 2006年3月号 「マイ認証」 2006年2月号 「索引ナビゲータ」 2006年1月号 「Greasemonkeyによるブラウザ機能の拡張」 2005年12月号 「本棚演算」 2005年11月号 「Rindaで実世界指向プログラミング」 2005年10月号 「並べる! 技術」 2005年9月号 「TV番組の検索と録画予約システム」 2005年8月号 「位置情報からの検索」 2005年7月号 「逆リンクと兄弟リンク」 2005年6月号 「携帯から位置情報を活用」 2005年5月号 「Ajax」 2005年4月号 「Phidgetsシステム」 2005年3月号 「ファイルシステムによる階層型データの管理」 2005年2月号 「最近の画像認証」 2005年1月号 「位置コミュニケーション」
傾き検出のアルゴリズム - myashikiの日記
アプリの傾き検出のアルゴリズムメモ (1)指定のスライスで白-＞黒となる点を抽出 縦、横でそれぞれ左右、上下の両端から２００ポイントで４００点ｘ２のエッジ情報を抽出 (2)縦、横それぞれをハフ変換して直線式の傾きを求める ハフ変換で得られる直線情報の上位10点から間違っていそうな点をのぞき平均をとって傾きを抽出。縦横で重みの多い方を採用 いじょうでふ
【インフォシーク】Infoseek ： 楽天が運営するポータルサイト
日頃より楽天のサービスをご利用いただきましてありがとうございます。 サービスをご利用いただいておりますところ大変申し訳ございませんが、現在、緊急メンテナンスを行わせていただいております。 お客様には、緊急のメンテナンスにより、ご迷惑をおかけしており、誠に申し訳ございません。 メンテナンスが終了次第、サービスを復旧いたしますので、 今しばらくお待ちいただけますよう、お願い申し上げます。
画像・エッジ検出 - ディジタル信号処理講座
このページを見るときは固定等幅フォントを使用してください エッジ検出とは エッジは物体の外縁を表す線ですが，画像処理では画像を特徴づける線要素という感じでしょうか． エッジ検出（又はエッジ抽出）は画像処理のなかでも基本的な操作の１つです． 特定の物体を取り出したり，複雑な画像認識，画像理解ための手がかりとして使われます． エッジは信号において急激な変化がある場合に領域を分割する要素として表現されます． 微分法によるエッジ検出 エッジは信号が変化をする部分ですので，信号の変化分を取り出す微分(Gradient)を用いるのが一般的な方法です． 画像（２次元）の微分によるエッジ検出は以下のようになります． 【各方向の微分量算出】 fx = s(i+1,j) - s(i,j) fy = s(i,j+1) - s(i,j) 【画像のエッジの強さ】 ______________ y(i,j) = √f
「言語処理のための機械学習入門」を参考に各種モデルに対するEMアルゴリズムを実装したよ - nokunoの日記
Amazonにもレビューを書いたのですが、高村さんの「言語処理のための機械学習入門」を読みました。実はこの本を読むのは2回目で、1回目はドラフト版のレビューをさせていただく機会があったのですが、そのときは「言語処理研究者のための機械学習入門」というタイトルで、ちょっと敷居が高いのではないかとコメントしたら「研究者」の部分が削られたという経緯があったりしました。 それはともかくとして、以前読んだときは時間もなくて実装までする暇はなかったのですが、今度はもうちょっとじっくり読みたいなということで、このブログに書いてみようと思います。EMアルゴリズムは教師なし学習を確率モデルと最尤推定でやろうとするときに必ず出てくる手法で、隠れ変数や欠損値を含む色々なモデルに適用できる汎用的なフレームワークになっています。一般的には混合ガウス分布の場合をまず説明して、それがk-means法の一般化した形になって
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意して
Oracle の B*Tree インデックスの内部構造についてお勉強中（その１）
お仕事のデータベース一式のリース切れ間近ということで、リース延長で耐えることができるのか、それともシステム更改が必要なのかを見極めるため、最近はデータベース周りのチューニングばかりやってます。 当初設計時に、５年間持つ設計をしたのですが、流石に５年目にもなると予定とはそれなりに乖離が発生するものです。テーブル＆インデックス設計をユーザ向けの処理をとにかく高速に処理できるように設計したので、ユーザ向けの処理は速度的に全然大丈夫なのですが、データの肥大化によるバッチ処理のパフォーマンス劣化が顕著です。単純にストレージと CPU パワーが足りていないのでしょう。 しかしながらチューニングの余地はまだまだ十分にありそうです。バッチ向けの最適化を図ることにしました。うまくいけば来年度どころか、後数年はリース延長で延命できるかもしれません。 今回実施したチューニングの１つのポイントとして、バッチ処理向
enbug diary(2009-09-23)
_ 連想配列に使うハッシュ関数 unladen-swallowのissue を見て、ちょっと気になったので、昨今のハッシュ関数の事情を調べていたのですが、 一言でいうと、難しい、です。 Pythonのハッシュ関数は、今でも FNV っぽいアルゴリズムを用いています。 ただし、実際には独立して開発されていて、たまたま似ているというだけだそうです。 で、 Hash functions: An empirical comparison なんかを見ると、 Murmur2 が汎用的には奨励されていて、 FNVよりも大体速くて、場合によっては衝突も少ないという結果が出ているみたいです。 では、なぜPythonがあいもかわらずFNVっぽいのかというと、 Python 3000のハッシュアルゴリズムの議論 でも見られるように、「ランダムなハッシュ関数は望ましくない（かもしれない）」というのが根拠らしいです
類似画像検索システムを作ろう - 人工知能に関する断創録
C++版のOpenCVを使ってカラーヒストグラムを用いた類似画像検索を実験してみました。バッチ処理などのスクリプトはPythonを使ってますが、PerlでもRubyでも似たような感じでできます。 指定した画像と類似した画像を検索するシステムは類似画像検索システムと言います。GoogleやYahoo!のイメージ検索は、クエリにキーワードを入れてキーワードに関連した画像を検索しますが、類似画像検索ではクエリに画像を与えるのが特徴的です。この分野は、Content-Based Image Retrieval (CBIR)と呼ばれており、最新のサーベイ論文（Datta,2008）を読むと1990年代前半とけっこう昔から研究されてます。 最新の手法では、色、形状、テクスチャ、特徴点などさまざまな特徴量を用いて類似度を判定するそうですが、今回は、もっとも簡単な「色」を用いた類似画像検索を実験してみます
天気予報から機械学習、金融工学まで - DO++
もう随分経ちますが，先日CompView秋の学校というのに行き，2泊3日みっちり機会学習を勉強してきました．講師陣は豪華でどの話も面白かったのですが特にElad Hazanによる"Prediction in the dark: the multi-armed bandit problem"が非常に面白かったです． その話を説明するために，まず簡単ながら驚くべき性能を達成するアルゴリズムを紹介しましょう． 解きたい問題は，毎日，次の日の天気が晴れか雨かを予想する問題です．t日目が晴れの場合 y(t)=1, 雨の場合 y(t)=0と表すことにしましょう．t日目にy(t+1)を予想するわけです． さて、自分は天気の専門家ではないので，自分で予報せずに，専門家に頼ることにしてみます．M人の天気予報士がいて，それぞれが独自に次の日の天気を予想しています．i人目の天気予報士のt日目の予報をp(i,t)
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Wikipediaから作成したN-gramデータを公開しました - nokunoの日記
Wikipediaによるテキストマイニング入門 - nokunoの日記
Skip Graph の concurrent JOIN を考える - その3 - higepon blog