吉田です。弊社では主に研究開発に携わっていますが、最近は顧問的なポジションになっている気がします。 普段は国立情報学研究所 (NII)という所で研究していて、よく論文を国際会議に投稿するということをします。 先日、CIKMという会議の結果が帰ってきて、今年開催される国際会議の結果が全て出そろったので、思い出話をしてみたいと思います。 紹介する論文の順番は、各会議が開催された(る)順です。 所々、専門用語を説明なしに使っていますがご容赦ください。 Yoichi Iwata and Yuichi Yoshida, Exact and Approximation Algorithms for the Constraint Satisfaction Problem over the Point Algebra. (STACS’13) 初めて東大の岩田君と書いた論文です。 岩田君は弊社でインターンや

運営元のロゴ Copyright © 2007-2024 All Rights Reserved by Gijutsu-Hyoron Co., Ltd. ページ内容の全部あるいは一部を無断で利用することを禁止します⁠。個別にライセンスが設定されている記事等はそのライセンスに従います。

2006年のデータマイニング学会、IEEE ICDMで選ばれた「データマイニングで使われるトップ10アルゴリズム」に沿って機械学習の手法を紹介します（この論文は@doryokujin君のポストで知りました、ありがとうございます！）。 必ずしも論文の内容には沿っておらず個人的な私見も入っていますので、詳細は原論文をご確認下さい。また、データマイニングの全体観をサーベイしたスライド資料がありますので、こちらも併せてご覧下さい。 データマイニングの基礎 View more presentations from Issei Kurahashi 1. C4.5 C4.5はCLSやID3といったアルゴリズムを改良してできたもので、決定木を使って分類器を作ります。決定木といえばCARTが良く使われますが、CARTとの違いは以下のとおりです。 CARTは2分岐しかできないがC4.5は3分岐以上もできる C

内容は線形識別モデルの学習について（Perceptron, PA, CW, AROW, NHELDとNLP2010のtutorial + 最新のアップデート. 更新式が整理されています）、オンライン凸最適化のregret解析、sublinearなSVMの学習の話です。最近公開したjubatusの中の学習アルゴリズムの解説でもあります。 コスト関数が凸である場合のOnline Gradient Descentのregret解析の証明は美しかったので、普通はこういうのはプレゼンではやらないとおもうのですが紹介しました。 Sublinearの学習の話は今後いろいろ発展しそうです。各学習例に動的に重みをつけて優先的に学習する方法は直感的にはできそうだと昔考えてたのですが、こういう形できれいに定式化できるのだと感心しました。 IBISはそこそこ参加していますが、毎年新しい分野の問題が登場してきて面白

社内で「機械学習とパターン認識」(PRML) の読書会をやっているのだけど、計算がやっぱり難しいようでみんな苦戦中。 そんなこんなで、光成さん(@herumi さん)が PRML の数式を手抜き無しで解説するアンチョコ(虎の巻 / PRML教科書ガイド)をマメに作ってくれている。*1 PRML のための数学(PDF) 内容は PRML の2章から4章と、9章、PRMLでもっとも計算が難しいと評判の10章を対象としている。 たとえば2章のアンチョコでは、2章の中で必要とされる解析や線形代数の道具(積分の変数変換、行列の各種操作)を一通り取り上げた後、ガウス分布の最尤推定における平均や分散による偏微分という、おそらく多くの人がつまづくのだろう計算がきちんと説明されている。 また3章のアンチョコでは、Woodbury の公式やヘッセ行列を解説しつつ、エビデンス関数などを導出しているし、4章になる

先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。 しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解

<追記>ベンチマークプログラムに誤りがありました。ソート済のシーケンスに対してソートを掛けていました。ご指摘ありがとうございます＞ak氏 そんな夢のようなソートアルゴリズムがあるのかというと、あるらしいんです。それがtim sortと呼ばれるアルゴリズムです。 画期的（？）なソートアルゴリズム「Sleep Sort」：濃縮還元オレンジニュース｜gihyo.jp … 技術評論社 このあたりで拾ってきたネタですね。 merge sortを改良したアルゴリズムで、安定*1しており、しかも実行速度にも優れているとか。アルゴリズムの性能の評価は済んでいるらしく、CPythonやJDK7には既に導入済みのようですね。 ならば当然Perlのソートも…と考えるわけですが、まず評価のためにJavaのソースをC++にそのまま移植してみました。それがこれ（いちおうテスト済）： https://github.co

自然言語処理を活用したwebサービス開発に関わって5年以上経った。いい機会なのでこれまでを振り返って役に立ったと思う5冊をメモしておく。 1.珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造 まずはこれ。有名な本なので知っている人も多いと思う。簡単に説明するとちょっと前に「フェルミ推定」という名前で流行ったような、データから必要な数値を概算する方法や、問題が起きたときに問題点がどこにあるのか？最小の労力で解決するにはどこをいじればよいのか？などが書いてある。「webサービスで自然言語処理だ！」というと無限に夢が広がりがちなので、どういうデータが使えるのか、それをどういう形にもっていけばイケてるサービスになるのか、それはどのくらいの期間で実現できるか、ということを考える必要がある。そういうわけで本書は真っ先に読むべき一冊なのでは(余談だけれど、以前M << Nなデータに対してO(

この記事で、アルゴリズムの勉強はアルゴリズムカタログを覚えることじゃないよということを書きました。 プログラムの理論とはなにか アルゴリズムの勉強というのは、スポーツで言えば腕立て伏せや走り込みみたいな基礎体力を養うようなもので、「ソートなんか実際に自分で書くことないだろう」とかいうのは「サッカーは腕つかわないのに腕立ていらないだろう」とか「野球で1kmも走ることなんかないのに長距離の走り込みいらないだろう」とか言うようなものです。 Twitterでアルゴリズムの勉強とはなにかと尋ねられて、「アルゴリズムの基本的なパターンを知って、それらの性質の分析のしかたをしって、いろいろなアルゴリズムでどのように応用されているか知って、自分が組むアルゴリズムの性質を判断できるようになることだと思います。 」と答えたのですが、じゃあ実際どういう本で勉強すればいいか、ぼくの知ってる本からまとめてみました。

吉田です。今まで数解に渡って乱択アルゴリズムを紹介してきました。そろそろ解析やアイデアがシンプルかつ結果が綺麗な乱択アルゴリズムは尽きてきたかと思っていましたが、もう一つとても素敵な手法が有るのを思い出しましたので解説します。Color Codingと呼ばれる手法です。 \(G = (V, E)\)をグラフ、\(s,t\in V\)を\(G\)中の二頂点、\(k\geq 0\)を整数とします。\((s,v,k)\)パスとは、\(s\)と\(t\)を結ぶパスで内点の個数が丁度\(k\)個のものを指します。但しパスは同じ頂点や枝を二度使ってはいけません。例えば以下の図で赤い線で示されているパスは\((s,t,5)\)パスです。

予約したもののインフォバーを手に入れられない海野です． 人間の高度な知的処理の一つが、推論処理です．今日はその推論を、述語論理と機械学習の組み合わせで模倣したMarkov Logic Networkという手法と、そのOSS実装であるAlchemyの紹介です． 鳥とはなんですか？という質問に対してどう答えるでしょうか．大雑把には、以下のように考えるでしょう． 鳥とは、空を飛ぶ動物です． この回答に対して、「ペンギンは飛ばないよ」と反論する人がいるかも知れません． 鳥とは、くちばしを持った動物です． すると、「カモノハシは鳥じゃないよ」と言われるでしょう．人間は初めて見た生き物が鳥かそうじゃないか判断するとき、どうしているのでしょうか．思うに、少数の規則（飛ぶかどうか．くちばしをもつか）から総合的に判断しているように思われます．人間の推論というのは概ね以下のような特徴を持っているのではないかと

こんにちは、この夏はシルキードライで乗り切りたい岡野原です。 今日は最近公開したC++のオープンソースであるdag vectorについて紹介します。 github: dag_vector ライセンスは修正BSDライセンスです。 dag vector (direct accessible gamma code vector) は値を圧縮して格納したまま任意の場所の値を高速に参照可能な配列ライブラリです。しかもデータ末尾への追記が可能です。 dag vectorはstd::vectorのように利用できます。下にいくつか例を見ていきましょう。 dag_vectorの例 #include "dag_vector.hpp" // dag_vectorは0以上の正整数の配列を扱う配列。 dag_vector dv; // 値はいつでも追加可能。追加された値は圧縮して格納される // 正整数xは2lg(

どうも，実は今年から開発チームにjoinしていた中川です．可愛い犬の写真がなかったので，可愛いマスコットの画像を貼っておきます． 最近MapReduceとかその実装であるHadoopとかをよく聞くようになりました．これはつまり，それだけ大量のデータをなんとか処理したいという要望があるからだと思います．しかし当たり前ですが，MapReduceは銀の弾丸ではありません． ということで，最近気になっているMapReduceとは違ったアプローチを取っている分散処理基盤について，社内のTechTalkで話した内容を簡単にまとめて紹介したいと思います． Bulk Sychronous Parallel このアルゴリズム自体は1990年に誕生したものです．長いのでBSPと書きます．さて，グラフから最短経路を求める時，MapReduceは使えるでしょうか？このような論文が出るくらいですから出来ないことはあ

About Project Euler What is Project Euler? Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems. The motivation for starting Project Euler, and