サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
TGS2024
yamaguchiyuto.hatenablog.com
すごいHaskell本を読んだのでなにか練習したいなと思っていたところ、某会*1で「B-treeなんて誰でも簡単に実装できますよね」と煽られたので実装してみた。すごく直感的に書けたので Haskell すごいなーと思った。実装方針は "Introduction to Algorithms" に書いてあるとおり。 すごいHaskellたのしく学ぼう! 作者: Miran Lipovača,田中英行,村主崇行出版社/メーカー: オーム社発売日: 2012/05/23メディア: 単行本(ソフトカバー)購入: 25人 クリック: 580回この商品を含むブログ (73件) を見る アルゴリズムイントロダクション 第3版 総合版 (世界標準MIT教科書) 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,Thomas H. Cormen,Clifford Stein,Ronald
研究者からエンジニアに転職 個人的にはかなり悩んだんだけど、結局これといった "かっこいい理由" みたいなものも特になくて、研究者だけじゃなくていろいろやってみたかったからという感じで転職してみた。研究者もエンジニアもどっちも楽しい! 論文が3本出た 論文がIJCAIでファースト2本、CIKMで学生さんファーストのポスターが1本出た。とりあえず自分の研究者としての仕事は一旦ここまで。また機会を見て戻ってきたい。 When Does Label Propagation Fail? A View from a Network Generative Model @ IJCAI2017 論文 ラベル伝搬法がネットワーク生成モデルの一つである確率的ブロックモデルと理論的につながっていることを示し、ネットワーク生成モデルの見地からラベル伝搬法の性質を解析する論文。 When Does Label Pr
研究留学 Advent Calender 2017 の19日目です。特にこれといったテーマも思いつかなかったので、エッセイ的に書きます。 テンプレ いついったか:2014年4月から2015年3月 どこに行ったか:カーネギーメロン大学の Christos Faloutsos 教授のところ(ペンシルベニア州ピッツバーグ) 何をやったか:ソーシャルデータとかグラフデータに対するデータマイニングの研究 どうやって行ったか:出身研究室の教授の紹介(つまりコネ) 行くまで(だけ)が辛かった Dとった直後に行くことが決まっていたので、博論を書きつつビザ取得とか家探しとかの留学準備をしなくちゃいけなくて、さらにちょうどその時期に結婚したのでその辺の諸々も含めすべて同時にこなさなきゃいけなくてそれはそれは辛かった。人生の節目となるイベントを2つ以上同時にこなすのはやめたほうが良い! ピッツバーグで暮らす ピ
前回の記事で Edward を使ってみたらすごく良かったので、もう一回遊んでみる。今回はグラフクラスタリングによく使われる Stochastic Block Model (SBM) を実装する。 前回の記事はこれ。 yamaguchiyuto.hatenablog.com ちなみにプルリク送ったらマージされたので、コードはリポジトリの edward/examples/stochastic_block_model.py にある。 github.com Stochastic Block Model Stochastic Block Model (SBM) はグラフの確率的生成モデルの一つ。グラフの確率的生成モデルと言うと、有名どころでは Erdos-Renyi model とか Barabasi-Albert model とかあるけど、そういうやつ。 SBM がどういうモデルなのか、すごく簡単
Edward っていう確率モデリングのためのライブラリがよさげって話を聞いたので入門してみたら良かったという話。せっかくなので、行列分解を確率モデルとして定義した Probabilistic Matrix Factorization を実装してみた。 Edward – Home 行列分解 (Matrix Factorization) 前にも書いた気がするけど、行列分解ってのは N x M 行列 X を、適当な K に対して N x K 行列 U と M x K 行列 V(の転置)との積に分解する手法のこと。つまり、 となるような U と V 見つければOK。ここで、 と が近くなる( になる)というのは例のごとく二乗誤差で評価する。つまり、 が最小となるような U と V を求める。 は U の i 番目の(K次元)行ベクトルで、 は V の j 番目の(K次元)行ベクトルを表す。要素ごと
博士を取ってからの3年間はアカデミックで仕事をしていたけど、4月から民間企業に移ることにした。転職するかどうかそうとう悩んだわけだけど、その時に研究についていろいろと考えたのでちょっと書いてみたい。 工学では研究と開発の違いなんて無い 誰もが納得するような明確な違いは無いと思う。あったら教えて欲しい。 実際、ほとんどの研究(論文)が何かを開発しているし、それが世の中の役に立たないと評価されない。逆に、ほとんどのプロダクトには新規性(もしくは他のプロダクトとの差異)がある。確かに、工学において研究と呼ばれるものは開発と呼ばれるものより平均的には基礎的なことをやっているとは思うけど、とはいえ明確な線引は出来ない。 研究を神格化しすぎる風潮があるんじゃないかな。 「研究者です」というと「すごい!」と言われることがよくある。そう言ってもらえるのは嬉しいけど、べつにすごくないよ。99%の研究者は世の
またまた引き続き青いトピックモデル本から。今回は Author Topic Model を導出して実装してみる。とりあえずこのシリーズは一旦今回で最後。 トピックモデル (機械学習プロフェッショナルシリーズ) 作者: 岩田具治出版社/メーカー: 講談社発売日: 2015/04/08メディア: 単行本(ソフトカバー)この商品を含むブログ (2件) を見る 出典は以下の論文。これまで実装してきたモデルと比べるとずば抜けて有名っぽい。 https://arxiv.org/ftp/arxiv/papers/1207/1207.4169.pdf Author Topic Model Author Topic Model (ATM) は文書に付加情報として著者情報が付いているデータのモデリングをするのに使われる*1。一つの文書に複数(一人以上)の著者がいるときに、文書中のそれぞれの単語についてどの著者
さらに引き続き青いトピックモデル本から。今回はノイズ有り対応トピックモデル (Noisy Correspondence Topic Model; NCTM) を導出して実装する。 トピックモデル (機械学習プロフェッショナルシリーズ) 作者: 岩田具治出版社/メーカー: 講談社発売日: 2015/04/08メディア: 単行本(ソフトカバー)この商品を含むブログ (2件) を見る 出典は以下の論文。 http://www.kecl.ntt.co.jp/as/members/iwata/nips2009.pdf Noisy Correspondence Topic Model このモデルは Correspondence Topic Model (CTM) の拡張になっていて、CTM と同様に付加情報を考慮しながら文書のモデリングが出来る。どう拡張されているかというと、付加情報の中からノイズとノ
KDD16で発表されてた論文。著者はかの有名なFactorization Machinesの人。Googleに行ってたのね。いままでとはちょっと違う研究をしてるように感じる。 論文はここから読める。 www.kdd.org 勉強会で紹介したので念のため、その時のスライドはこちら。 Robust Large-Scale Machine Learning in the Cloud from Yuto Yamaguchi 一言まとめ 一般化線形モデルの学習を Coordinate Descent で、めっちゃスケールさせるよ。 概要 Coordinate Descent (CD) はシングルマシン上では収束が早いアルゴリズムとして知られてるんだけど、分散には向かない。なぜなら、アルゴリズムの特性上、分散させると1つのワーカーに割り当てられる work load が小さくなってしまって、オーバヘッ
ノンパラベイズ面白いね。佐藤一誠先生のノンパラメトリックベイズの本を読んで自分なりに理解できたので実装してみた。本読んで理解して、自分で導出して、実装・実験するの本当に重要。定着度がぜんぜん違う。 ノンパラメトリックベイズ 点過程と統計的機械学習の数理 (機械学習プロフェッショナルシリーズ) 作者: 佐藤一誠出版社/メーカー: 講談社発売日: 2016/04/20メディア: 単行本(ソフトカバー)この商品を含むブログを見る 無限混合ガウスモデルは上の本の5.2節で説明されてるモデルで、ディリクレ過程混合ガウスモデル(Dirichlet Process Gaussian Mixture Model; DPGMM)とも呼ぶらしい。面倒くさいので以下DPGMMと書く。 DPGMM 普通の混合ガウスだと分割数(クラスタの数)K を事前に決めなきゃいけないんだけど、これが面倒くさいし、よほどそのデー
引き続きノンパラベイズ。今回はノンパラベイズ本の7.4節で説明されてる無限潜在特徴モデル(Infinite latent feature model; ILFM)を実装した。 ノンパラメトリックベイズ 点過程と統計的機械学習の数理 (機械学習プロフェッショナルシリーズ) 作者: 佐藤一誠出版社/メーカー: 講談社発売日: 2016/04/20メディア: 単行本(ソフトカバー)この商品を含むブログを見る 無限潜在特徴モデル 一言で言えば、潜在次元に無限次元を仮定する行列分解。 与えられたデータ行列 をバイナリ行列 と特徴行列 の積に分解する。 バイナリ行列の要素 はサンプル n が k 番目の潜在特徴を持つか持たないかを表している。k番目の潜在特徴は のk番目の行ベクトル で表されている。つまり、あるサンプルのデータベクトル は無限個ある潜在特徴のうちのいくつかの和になっている。 通常の行列
CP分解の次はTucker分解を導出して実装する。丁寧にTucker分解の導出を説明してる文献(Web含め)が全然なかったので、自分で書く。CP分解についてはある程度知ってる前提とする。CP分解についてはこちらから。 yamaguchiyuto.hatenablog.com まとめ Tucker分解とは ALSでTucker分解の更新式の導出 PythonでTucker分解を実装 人工データを使って実験 Tucker分解とは Tucker分解は、テンソルを1つのテンソル(コアテンソルと呼ぶ)と、それぞれのモードに対して一つずつの行列に分解する。 上の図の例では、もとのテンソルのサイズは IxJxK だけど、これをコアテンソルのサイズの RxSxT (R<=I, S<=J, T<=K) まで小さくしている。また、あとで説明するけど、行列 U、V、W は全て直行行列となるように分解する。このコ
テンソル分解の基本中の基本のCP分解を導出して実装した。最適化の方法は色々あるらしいけど多分いちばんよく使われる Alternating Least Square (ALS) を使った。ちなみにここでテンソルって呼んでるのはただの多次元配列のこと。 まとめ CP分解とは AlSによるCP分解の更新式を導出 ALSによるCP分解をpythonで実装 人工データを使って実験 CP分解とは CP分解が何かを知るためには、まず Matrix factorization (MF) について知ると良い。 MFでは、N x M 行列 X を以下のように分解する ここで、は N x R 行列で、は M x R 行列。この分解を要素ごとに書くとこうなる つまり要素 を なんかよくわからない次元のベクトル との内積で表現することにしましょうと言っているわけ。 じゃあこの と っていうベクトルたちをどうやって求
scikit-learn準拠で Label propagation 的なアルゴリズム達を実装した。なんで実装したかというと、 グラフそのもの(隣接行列)を入力したい。 scikit-learnには既にsklearn.semi_supervised.LabelPropagationが実装されてるけど、これはグラフを入力するんじゃなくて、普通にサンプル数×特徴数のデータ行列を与えて、そこから類似度グラフを作るようになってる。これだと例えば手元にソーシャルグラフがあって、そのユーザ(ノード)の属性(興味とか)を Label propagation で推定するということができない。 ハイパーパラメータを楽に決めたい。 自分でグリッドサーチとかやるのはめんどくさいので、sklearn.grid_search.GridSearchCVとかを使いたい。そのためにsklearn準拠にした。 自分の研究成果
Graph embedding を調べる上で避けては通れないっぽいTransEを実装して実験再現してみた。モデルがシンプルでカッコイイし実装も簡単だった。データもパラメータも公開されてて実験を再現できたのもポイント高い。 TransE NIPS'13で提案されたGraph embeddingをする手法。Google scholarで既に100以上引用されていろんな拡張モデルが提案されてる。論文は以下。 papers.nips.cc TransEはKnowledge graph(Freebaseとか)をベクトル空間上にembeddingする。入力としてKnowledge graphを与えると、全てのsubject, predicate, objectに対してそれぞれk次元のベクトルを出力する。ポイントは出力されたベクトル空間に構造があること。例えば、 v(Kei Nishikori) + v
最近Graph embeddingに興味があって調べてるので有名っぽいRESCAL [ICML'11] をとりあえず実装してみた。さすが結構引用されてるだけあって簡単お手頃に実装できた。やっぱシンプルさ大事。 Graph embedding 入力 グラフ G = (V,E) 出力 それぞれの頂点 に対して r次元ベクトルを1つずつ 要するにグラフ上の頂点の特徴を表す特徴ベクトルがほしいってこと。Representation learningとも言える。グラフ(上の頂点)をベクトル空間上に "埋め込む" からGraph embeddingと呼ばれている。この特徴ベクトルを使うことで普通のベクトルベースの機械学習手法をグラフにそのまま適用できるからうれしいねということになる。 RESCAL ICML'11で提案されて、WWW'12でちょっと修正&拡張されてちょっとでかめの実データで実験されてる
CMUに留学している時にFaloutsos教授に教わった論文の書き方をまとめる。この書き方に従うことで論文の採択率がかなり上がった。今となっては自分的に当たり前のことだし、できる研究者の皆様は自然と守っていることも多いと思うけど良い論文を書きたいと思っている学生とかに参考にしてもらえたらと思う。ただし、Faloutsos教授に教えてもらったことを一旦自分で噛み砕いてからまとめたものなので自分の主観とかが混じってしまっているかもしれない。 主語が大きくならないように予め断っておくけど、この書き方はもちろんすべての論文に対して当てはまるわけじゃなくて以下の前提条件がある。 国際会議論文である データマイニング関連分野の論文である 論文誌とか卒論とかもっと長めの論文を書くときは当てはまらない項目もあるし、データマイニング関連分野以外の論文を書いたことが無いのでそれ以外の分野の論文に当てはまるかも
無向グラフの時のPersonalized PageRank*1とLabel Propagation*2(LGCとも呼ばれる)が本質的に等価というお話。つまりLabel Propagationを計算したいときはPersonalized PageRankを計算すれば等価な結果が得られる。Personalized PageRankとLabel Propagationを知ってる人向けに書くのでわからない人はブラウザの戻るボタンを押してね。 まず、Label Propagationは以下のように書ける。 ただし、で、Wはデータ間の類似度行列、Dは次数の対角行列を示す。また、yはlabeled exampleのラベルを格納するベクトルで、positiveなら1、そうでなければ0を格納する(unlabeledも0)。αは0から1のパラメータ。この等式を満たすfが求められればLabel Propagati
ICWSM2015で発表してきた。タイトルは"Patterns in Interactive Tagging Networks"。2年前にポスター発表していて、今回はフルペーパーで発表できた。この会議は面白いから今後も参加したいなー。 今回の発表は初めての「分析しました論文」だった。WWW2015での発表でも使ったデータと同じもの(規模は違う)を使って、Twitterにおけるユーザのタグ付け関係(リストをタグとみなした)について基礎的な分析をした。 正直、当たり前とも思える結果を示しただけなんだけど、それを「しっかり示す」ことに意義があると認められたんだとおもう。メタレビュアもそう言っていた。ICWSMは特にこの辺を重視している印象で、他の論文もこういう感じのものが多かった気がする。Research questionを明確に示して、それにしっかりと答えるのが何よりも大事ということかな。 P
WWW2015でポスター発表してきた。WWWは以前聴講だけで参加したことがあって、今回はポスターだったので、次回はフルペーパーで発表したい。今回のポスターのタイトルは"Why Do You Follow Him? Multilinear Analysis on Twitter"。キャッチーなタイトルにしたいなーと思ってあれこれ考えた結果結局ありがちなタイトルになった笑 今回の発表はTwitterにおいてユーザが他のユーザをフォローする理由を分析しましょうというもの。以前から@ceekzさんと一緒にTwitterのデータ使った研究しましょうと言ってたのでようやく一つ発表できた。基本的には@ceekzさんにデータの収集と基本的な分析をしてもらって、僕が持ってたちょっとしたアイデア(テンソル分解)を試してみた感じ。 この発表に関するリソースは以下のとおり。 データ:http://dx.doi.o
PAKDD2015に論文が通っていたので発表した。タイトルは"SocNL: Bayesian Label Propagation with Confidence"。自分で参加して発表したかったんだけどちょうど同じ日程でWWW2015が開催されていて、そっちでの発表もあったので、PAKDDには参加できなかった。残念。なので共著のFaloutsos教授の知り合いの方にかわりに発表してもらった。大変お世話になりました。 前回のAAAI2015に引き続き、今回の発表もグラフ上でのノード分類アルゴリズムの提案。やっぱりアルゴリズムを考えていろいろ解析するのは楽しい。今後もこういう研究をしていきたい。 SocNL: Bayesian Label Propagation with Confidence from Yuto Yamaguchi 概要 今回の発表はグラフ上でのノード分類アルゴリズムをベイズ推
いろいろとあれがあれしてアメリカのピッツバーグにあるカーネギーメロン大学で一年間研究することになった。 そろそろ二週間くらいになるけど、ピッツバーグで暮らし始めてから色々と大変だったから今後ピッツバーグに来る人のためにちょっとメモ。 ピッツバーグ便利帳 メインページ - ピッツバーグ便利帳 これがないと始まらない。ホントにお世話になってます。 渡米関連 飛行機 Air CANADAにした。 自分が飛行機に乗った時期(4月)は航空券を買うのが遅かったのもあるのかJALとかANAは40万円くらいした。 目ん玉飛び出そうになったから他のを探したらAir CANADAなら13万くらいだったから目ん玉戻った。 日本からピッツバーグへの直行便はない。 ちなみに片道航空券は往復航空券より高い。 意味不明だからいろいろ調べてみたら、往復航空券は格安ツアーの航空券を使ってたりするから安くなってるらしい。 荷
AAAI2015で発表してきた。タイトルは"OMNI-Prop: Seamless Node Classification on Arbitrary Label Correlation"。必殺チェアーからの質問による時間稼ぎは出ずにちゃんと聞いてくれてる人たちから質問が出たから良かったかな。 今回はソーシャルネットワークにデータを限らずに出来るだけ広範囲のグラフに適用できるアルゴリズムを提案した。話を一般的にしようとすればするほど大変だといういい経験が出来た。ドメインに特化した問題を解くアルゴリズムももちろん重要だけど、やっぱりいろんなデータに対して適用できるアルゴリズムを提案するってのはその分野の発展にも寄与できるしもっと重要だと思う。 OMNI-Prop: Seamless Node Classification on Arbitrary Label Correlation from
AAAI2015に参加中(TASAは何なのか知らない)。1,2日目はワークショップとチュートリアルと招待講演があった。例のごとくワークショップはパスしていくつかチュートリアルと招待講演を聞いて回った。 いろいろ聞いた感じだと、AIコミュニティはホントにいろんな分野の融合になっていて、扱う範囲が広すぎると思った。自分は元々AIの人間ではないので、知らない単語とか分野がかなり合って、いろいろ知れただけでも参加してよかったと思った。レセプションで話した人たちもみんな結構バラバラの分野から来てて面白かった。 以下参加したチュートリアルと招待講演のメモ。 The Future of (Artificial) Intelligence - Stuart Russell 最近シンギュラリティやばいとかニュースで話題になったりしてるから、しょうがないそれに対して答えてやろうという招待講演。 色々例を挙げて
ICML14から。数式とか書くのはめんどくさいからアイデアを中心に書く。 概要 ネットワーク上の ノード分類 の話で、各ノードは 複数のラベルタイプを持っている という設定。例えば論文中で使われている例だと、Facebookユーザの出身地、現住所、高校、大学、雇い主の5つのラベルタイプを同時に推定する。 アイデア 提案手法は接続されているノードペアの 多くが出来るだけラベルを共有する ようにノードのラベルを決定する。このやり方がうまくいくことを説明するために既存手法(ラベル伝搬法)がうまくいかない例を挙げる。下の図(論文中Fig. 1)に対してラベル伝搬法を適用すると、u のhometownとcurrent cityはそれぞれ多数決により H と C' と推定される。でもこれだと右の方にいる赤いやつらと u がどのタイプのラベルも共有しないため、 なぜ友達なのかが説明されない という状況に
WWW14から。次のWWW15はイタリアフローレンス!参加したい! 概要 Social tagging systems(FlickrとかDeliciousとか)においてリソース(Flickrなら写真、DeliciousならWebページ)に付けられたタグがどのように "Stable" になっていくかを分析。 Social tagging systemsではいろんな人が何のルールもなしに好き勝手タグ付けをするので、結果として意味を成さないめちゃくちゃなタグ付けになってしまいそうだけど、(多くの人が経験上分かるように)そうはならない。時間を追ってどんどんタグ付けされていくわけだけど、一定時間経つとあるリソースに付けられたタグの "割合" は変化しなくなる。こういう状況を "Stable" であるという。 例えば、Deliciousでgoogle.comは多分"search engine"とかそう
グラフベース半教師あり学習 (SSL) のLabel propagation (LP) とLabel spreading (LS) の違いを説明している文献があまりなかったのでそれについてちょっと書いてみる。SSL自体とかLP、LSについては以下の記事にまとめた文献がいい感じなのでそちらを参照。 半教師あり学習のモデル仮定 - でかいチーズをベーグルする LPの元論文はこれ (PDF) "Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions", ICML2003 LSの元論文はこれ (PDF) "Learning with Local and Global Consistency", NIPS2003 まとめ LPとLSの超概要、ランダムウォークとしての解釈、最適化問題としての解釈を書いた 軽い実験をした
ICDM14からもう一本。一度も参加したこと無いけど来年は参加してみたいな。 概要 TwitterからCampaign Promotersを検出する。Campaign Promotersってのは企業によるマーケティングやら政府による何らかのキャンペーンとかをやってるTwitterアカウントのこと。ちょっと前に流行ってたけどキャンペーンとかマーケティングをステルスでやるアカウントが多いからそういうの見つけたいよねっていうモチベーション。 貢献 複数タイプのノード、エッジを扱えるようにMRFを拡張してT-MRF (Typed MRF) を提案 Campaign Promotersを検出できるようにMRFのノードポテンシャルとエッジポテンシャルを設計 手法 一言で言えばタスク特化にした特殊なグラフを作って、MRFを使ってTwitterユーザがPromotersかNon-promotersかを推定
Python Advent Calender 2014の19日目。 scikit-learnに準拠した学習器を自分で実装してscikit-learnに実装されているgrid searchとかcross validationを使えるようにするお話。Pythonの話というか完全にscikit-learnの話なんだけど、まあいいよね。 scikit-learnについてはこの辺がわかりやすいかな。 pythonの機械学習ライブラリscikit-learnの紹介 はじパタlt scikit-learnで始める機械学習 scikit-learn準拠にするには? 全部下のページに書いてある。 Contributing — scikit-learn 0.15.2 documentation やること sklearn.base.BaseEstimatorを継承する 回帰ならRegressorMixin
次のページ
このページを最初にブックマークしてみませんか?
『でかいチーズをベーグルする』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く