Chokudai's Labo
About 本名 高橋 直大（たかはし なおひろ） ＨＮ chokudai 所属 慶應義塾大学 環境情報学部３年 実績 2009年度 TopCoder Marathon Match 54 ３位 天下一プログラマーコンテスト 特別賞 TopCoder Marathon Match 56 ４位 NASA-TopCoder Challenge 個人４位 2008年度 2008年度慶応義塾大学塾長奨励賞受賞 Imagine Cup 2008 Algorithm部門 世界３位 TopCoder Marathon Match 49 世界２位 2007年度 Imagine Cup 2007 Algorithm部門 ２次予選進出 2006年度 Imagine Cup 2006 Algorithm部門 ２次予選進出 SuperCon 2006 ６位 書いたもの 最強最速アルゴリズマー養成講座 第１回 あなた
競技大好き、世界3位のアルゴリズマー「高橋直大」
こんにちは、電設部の塚田です！ 月日の流れは早いもので、もう11月も半ばを過ぎ、7月の暑い日に産声をあげたこの連載も4回目となりました。来年3月に筆者は学校を卒業いたします。それまでに、まだまだたくさんの学生スターエンジニアに会いたい、話を聞きたい所存です。皆さま、どうかお付き合いくださいませ。 「学生スターエンジニア」4人目は、アルゴリズマー 高橋直大！ 第4回のターゲットは高橋直大さんです。慶應義塾大学 環境情報学部の2年生で、ITmedia エンタープライズにて「最強最速アルゴリズマー養成講座」という連載を行っています。 彼のことを知ったのは、Imagine Cup 2008（筆者注：マイクロソフトが主催する、全世界の学生向け技術コンテスト）が開催された2008年の7月です。彼は、この大会のアルゴリズム部門で世界第3位という快挙を成し遂げました。この偉業を報じる各メディアの記事を見て
ソーシャルウェブ と レコメンデーション －第４回データマイニング+WEB勉強会＠東京
「第４回データマイニング＋ＷＥＢ勉強会＠東京 (#TokyoWebmining)」の講師資料です。 『ソーシャルウェブ と レコメンデーション』 hamadakoichi, 濱田晃一
特徴点検出器を作ってライブラリに追加した - デー
前々からアニメ顔類似検索のbag of featuresで使っている特徴点の決め方がイラストにあまり合っていない気がしていたけど、実装がすごく面倒くさそうだったのでやらなかった。しかし、最近SURFに特許があることが発覚して、SURFを使っている意味は特にないなーと思ったので、満足のいくものをつくろう思ったのであった。（ただ特許は気にせずにやる） ということで、こんなのができた(クリックで拡大)。 結構速いし、スケールの変化、回転、ある程度のゆがみには大体対応できている。対応点の決定は、点の特徴ベクトルが一番近い点と二番目に近い点を取って、ふたつの特徴ベクトルの距離の差を確信度として、確信度が高いもののみマッチングしたことにして表示している。 SIFTやSURFに比べると点多すぎだろ（なぜ渦巻きに…）と思うかもしれないけど、これは僕なりにイラストの特性とかbag of featuresで使
順序木の簡潔表現を用いたトライ辞書の評価（スライド） - やた＠はてな日記
情報処理学会第 72 回全国大会での発表に使用したスライドをアップロードしました． 内容を簡単に説明すると，順序木に対する簡潔表現 6 種類とノードの配置順序 2 種類の組み合わせを試して，どれが良いのかを調べたというものです．実験において Google N-gram コーパス全体をトライに登録したところが特徴的です． PowerPoint (pptx) http://sites.google.com/site/headdythehero/cabine/2010/0311/IPSJ-2010.pptx?attredirects=0&d=1 PDF http://sites.google.com/site/headdythehero/cabine/2010/0311/IPSJ-2010.pdf?attredirects=0&d=1 # 聞いてくれる人が少ない発表というのは寂しいものです． 追
大規模ソーシャルサーチエンジンの構造 - file-glob こと k.daibaの日記
はじめに Googleのように，どのドキュメントが適切なのかを選ぶのではなく，質問を誰にするのが適切かを選ぶ検索エンジンをAardvarkという会社が作り，その構造を論文で公開しました．この会社はもともとGoogleの社員だった人達が作った物で，最近Googleが買い上げました．今日はその論文の要旨をまとめてみました． タイトルと著者 タイトルはGoogle創始者のLarry PageさんとSergey Brinさんが1988年に発表した"Anatomy of a Large-Scale Hypertextual Search Engine"と韻を踏んでいます．論文を発表したのは，Aardvark社のDamon HorowitzさんとStanford Univ.のSepandar D. Kamvarさんです．以下小見出しが章，少々見出しが節という形式で進めます． ABSTRACT Aard
協調フィルタリングのグラフィカルモデル - nokunoの日記
協調フィルタリングとはAmazonのお勧めのように「この商品を購入した人はこんな商品も購入しています」という情報を用いて推薦をする手法です。グラフィカルモデルはベイジアンネットワークとも呼ばれ、最近一部で流行している機械学習の手法です。今回は、協調フィルタリングをグラフィカルモデルで表現したらどのようになるだろう、と考えて思いついたアイデアを紹介します。 今、ユーザuとアイテムiの組{u,i}のデータが大量に与えられているとします。例えばソーシャルブックマークならユーザとブックマークしているページの組み合わせ、E-commerseならユーザと購入した商品の組み合わせ、などです。ここではSBMを例に考えるので、はてブと同様にユーザはマイナスの評価を付けることはできないものとします。 このときユーザuに対してお勧めのページを推薦することを考えると、ユーザuがまだブックマークしていないページiに
PFIセミナー資料: 研究開発2009 - DO++
昨日ありました、PFIでのセミナーでの発表資料です。 研究開発のチームの紹介の後に、2009年サーベイした論文の中で面白かった論文を 機械学習、データ構造、画像処理で紹介してます 紹介した話は - Multi-class CW (Multi-class Confidence Weighted Learning,) - AROW (Adaptive Regularization Of Weight Vector) - Online-EM algorithm - 全備簡潔木 (Fully-functional Succinct Tree) - 圧縮連想配列 (compressed function) - PatchMatch です。 ＃資料中の簡潔木の表現方法のDFUDSの紹介でtxも使用と書いてあるのは、公開しているtxでは、 LOUDSのみをつかっていますので正確ではありませんでした。これ
最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (1/5) - ITmedia エンタープライズ
動的計画法とメモ化再帰 今回は、非常によく用いられるアルゴリズムである、「動的計画法」「メモ化再帰」について説明します。この2つはセットで覚えて、両方使えるようにしておくと便利です。 なお、メモ化再帰に関しては、第5・6回の連載の知識を踏まえた上で読んでいただけると、理解が深まります。まだお読みになっていない方は、この機会にぜひご覧ください。 中学受験などを経験された方であれば、こういった問題を一度は解いたことがあるのではないでしょうか。小学校の知識までで解こうとすれば、少し時間は掛かるかもしれませんが、それでもこれが解けないという方は少ないだろうと思います。 この問題をプログラムで解こうとすると、さまざまな解法が存在します。解き方によって計算時間や有効範囲が大きく変化しますので、それぞれのパターンについて考えます。 以下の説明では、縦h、横wとして表記し、プログラムの実行時間に関しては、
検索クエリログからのスペル訂正辞書の自動生成 - mixi engineer blog
先月ハワイに行ってきてオルオルな （ハワイ語で '楽しい' という意味） 気分の takahi-i です。最近ログデータの有効活用が話題になっていますが、検索エンジンが出力する検索クエリログを使用してどんなことができるのかについて紹介させていただきます。 検索クエリログ 検索クエリログ (以下検索ログ) は検索エンジンを使用するユーザから発行された検索の履歴を保存したファイルです。検索ログのフォーマットは使用する検索エンジンや Web サーバによって異なります。さらにまた検索ログが含む情報にも差異があることが考えられますが、本稿では検索ログは解析を行う上で重要な三つの要素を含むと仮定します。三つの要素とはユーザ ID （もしくは IP アドレス）、クエリ文、そしてクエリが検索エンジンに処理された時間です。以下検索ログの一例を載せます。 ユーザID クエリ文 クエリ発行時 438904 Su
Bayesian Setsによる関連文書検索システムStupa - mixi engineer blog
都会よりも田舎が好きなfujisawaです。Bayesian Setsというアルゴリズムを使って、関連する文書を高速・高精度に検索できるシステムを作成しましたので、そのご紹介をさせていただきます。 Bayesian Setsとは Bayesian Setsはいくつかアイテムを入力すると、それを補完するようなアイテムを返してくれるアルゴリズムです。原著論文の先頭に"Inspired by Google Sets"と書かれているように、Google Setsを参考にして作成されています。実際にどのような出力が得られるか、Google Setsに以下の表のクエリを検索して試してみますと、 クエリ 出力 apple, banana chocolate, strawberry, vanilla, cherry, ... apple, macintosh software, windows, mac,
HITS, 主成分分析, SVD - naoyaのはてなダイアリー
ウェブグラフのリンク解析によるページの評価と言えば PageRank が著名ですが、もうひとつ Jon Kleinberg による HITS (Hyperlink-induced topic search)も有名です。最初の論文 Authoritative Sources in a Hyperlinked Environment は 1999年です。IIR の 21章で、この PageRank と HITS についての解説がありました。 HITS HITS はウェブページの評価に二つの軸を用います。一つが authority スコア、もう一つが hub スコアです。 例えば「Perl の情報が欲しい」という検索要求に対しては CPAN や 開発者である Larry Wall のホームページなどが重要度の高いページかと思います。これらのページは「Perl に関して信頼できる情報源」ということ
Netflix Update: Try This at Home
[Followup to this] Ok, so here's where I tell all about how I (now we) got to be tied for third place on the netflix prize. And I don't mean a sordid tale of computing in the jungle, but rather the actual math and methods. So yes, after reading this post, you too should be able to rank in the top ten or so. Ur... yesterday's top ten anyway. My first disclaimer is that our last submission which tie
佐々木 祥さん, 上村 理さんの講演 - Tocotonistの日記(晴れのち快晴)
10:20〜11:00 講師: 佐々木 祥さん(twitter), 上村 理さん(twitter) 所属：東京工業大学 博士課程、修士課程 講演タイトル：エコメンデーション 資料upあり videoあり 講演概要 情報爆発の時代においてはユーザのニーズに合わせた情報発見のためのシステムとして，リコメンデーションの必要性は高まっている。しかしながら参加ユーザ数の増加，嗜好の多様化により，リコメンデーションに必要となる計算量は莫大となっている。 この問題に対し，計算処理の分散方法が各種提案されているが，これらの方法は複数の計算機を使い処理を行うため経済的側面や環境的側面から見ても「エコ」ではない。そこで，推薦の精度を保ちつつ，計算量削減を実現する方法を検討する。 以下は私のメモです。 佐々木さんの講演 １サイトにBMするだけではなく、２つのサイト間の関係としてBMするのも良い。 graphのl
最近傍探索 - Wikipedia
最近傍探索（英: Nearest neighbor search, NNS）は、距離空間における最も近い点を探す最適化問題の一種、あるいはその解法。近接探索（英: proximity search）、類似探索（英: similarity search）、最近点探索（英: closest point search）などとも呼ぶ。問題はすなわち、距離空間 M における点の集合 S があり、クエリ点 q ∈ M があるとき、S の中で q に最も近い点を探す、という問題である。多くの場合、M には d次元のユークリッド空間が採用され、距離はユークリッド距離かマンハッタン距離で測定される。低次元の場合と高次元の場合で異なるアルゴリズムがとられる。 ドナルド・クヌースは、The Art of Computer Programming Vol.3（1973年）で、これを郵便局の問題で表した。これはすな
バイナリシリアライズ形式「MessagePack」 - Blog by Sadayuki Furuhashi
Googleが公開したバイナリエンコード手法であるProtocol Buffersは、クライアントとサーバーの両方でシリアライズ形式を取り決めておき（IDL）、双方がそれに従ってデータをやりとりするようにします。 この方法では高速なデータのやりとりができる反面、IDLを書かなければならない、仕様を変えるたびにIDLを書き直さなければならない（あらかじめしっかりとIDLを設計しておかないとプログラミングを始められない）という面倒さがあります。 ※追記：Protocol BuffersのデシリアライザはIDLに記述されていないデータが来ても無視するので（Updating A Message Type - Protocol Buffers Language Guide）、仕様を拡張していっても問題ないようです。 一方JSONやYAMLなどのシリアライズ形式では、何も考えずにシリアライズしたデータ
BLOG::broomie.net: 各種分類器の分類精度を示した絵がおもしろい
今日会社で多次元のデータを２次元にクールでベストプラクティスな感じでプロットするにはどうしたらいいんだろうね、やっぱ多次元尺度構成法じゃない？的な会話をしていたのだけれども、２次元にデータを落とし込むと人間にもわかるデータになって本当におもしろいですよね。今日はその一例というか、いくつかの分類器の分類精度を２次元にプロットした結果を示した実験結果を解説したページを紹介します。おおーこうゆうのみたかったんだよなー！と個人的にはかなりエキサイティングな感じでした。 要約というか意訳になってしまうのですが、ページに以下のように説明されています。(細かいところは訳してません) http://home.comcast.net/~tom.fawcett/public_html/ML-gallery/pages/index.html 分類タスクの機械学習の研究では定量的な評価が重要です(精度とかACUと
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
加藤 和彦 Kazuhiko KATO, Dr. Prof.
azito.com
生きあたりまったりブログ
