サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
掃除・片付け
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次元)行ベクトルを表す。要素ごと
クロネッカー積とvec作用素は見た目簡単なんだけど、各要素のインデックスを書き下すと頭の中こんがらがってわけわからなくなるから一旦整理した。インデックスに関する記事ってほとんどないね。あとそれに関連して Roth's column lemma っていうのが便利なのでちょっと紹介する。 まとめ クロネッカー積の定義とインデックス vec作用素の定義とインデックス Roth's column lemma クロネッカー積とは クロネッカー積 - Wikipedia 下の式を見ればひと目で分かるけど、 IxJ 行列 と KxL 行列 から IKxJL 行列を作る。 Wikipediaの例を見ると分かりやすい。 クロネッカー積のインデックス クロネッカー積の定義は一目見ればすぐ分かるのに、各要素の定義を見ると途端にめんどくさくなる。 行のインデックスを見ると、K進数みたいになってるのが分かる。 の行
引き続き青いトピックモデル本から、対応トピックモデル(Correcpondence Topic Model; CTM)を実装した。サンプリング式の導出が詳しく載っていなかったので、詳しめに導出してみる。 トピックモデル (機械学習プロフェッショナルシリーズ) 作者: 岩田具治出版社/メーカー: 講談社発売日: 2015/04/08メディア: 単行本(ソフトカバー)この商品を含むブログ (2件) を見る CTM の出典は以下の論文。 http://www.cs.columbia.edu/~blei/papers/BleiJordan2003.pdf Correspondence Topic Model 前回書いた結合トピックモデル(Joint Topic Model; JTM)と同じで、文書のモデリングをするときに文書についている付加情報も考慮するモデル。 JTMとCTMが違うのは以下の点だ
博士を取ってからの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 と同様に付加情報を考慮しながら文書のモデリングが出来る。どう拡張されているかというと、付加情報の中からノイズとノ
LDAの簡単な拡張になっている Joint Topic Model を実装した。青いトピックモデル本で紹介されてた。この本はいろんなモデルが載ってるのでいいね。 トピックモデル (機械学習プロフェッショナルシリーズ) 作者: 岩田具治出版社/メーカー: 講談社発売日: 2015/04/08メディア: 単行本(ソフトカバー)この商品を含むブログ (2件) を見る 実装したあとで気づいたけど既にnzw君が実装して実験してたのでこちらも参考に。 nzw0301.github.io Joint Topic Model Joint Topic Model (JTM) はLDAとほとんど同じなんだけど、文書に付加情報(カテゴリとか)がついてる場合、それも使うことができる。 どんな付加情報を扱えるかというと、基本的にはカテゴリ変数だけ。生成過程を見ると分かるように、付加情報の生成にはカテゴリカル分布が使
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番目の行ベクトル で表されている。つまり、あるサンプルのデータベクトル は無限個ある潜在特徴のうちのいくつかの和になっている。 通常の行列
スライド作りが進まないから現実逃避してちょっとしたスクリプトを書いて遊んだ。 題して「自分がふぁぼったツイートをランダムに表示するスクリプト」 モチベーション 自分は後で読む的な意味合いでツイートをふぁぼるんだけど、例のごとく「後で読む」はどんどん溜まっていって、昔のツイートは全く日の目を見ないことになってしまう。 そこで最近のものから一番古いものまでランダムに表示できたら暇つぶしにいいかなと思って作ったのがこれ。 必要なもの 自分のTwitterアプリケーションキー達 (consumer key, consumer secret, access token, access token secret) Tweepy 使い方 1. まず自分のTwitterアプリケーションキー達を適当なファイルに以下の形式で保存する。 $ cat keys [consumer key] [consumer s
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教授に教えてもらったことを一旦自分で噛み砕いてからまとめたものなので自分の主観とかが混じってしまっているかもしれない。 主語が大きくならないように予め断っておくけど、この書き方はもちろんすべての論文に対して当てはまるわけじゃなくて以下の前提条件がある。 国際会議論文である データマイニング関連分野の論文である 論文誌とか卒論とかもっと長めの論文を書くときは当てはまらない項目もあるし、データマイニング関連分野以外の論文を書いたことが無いのでそれ以外の分野の論文に当てはまるかも
Machine Learning Advent Calendar 2015 の10日目です。 EMアルゴリズム自体の説明は溢れてるけど実際にEMアルゴリズムを使って何かを解いてみたっていう例題はGMM(Gaussian Mixture Model)以外あまり見ない気がする。なので今日は二つの例題を使って具体的にEMアルゴリズムを使ってみる。 導出してみるのはかの有名なPLSA(Probabilistic Latent Semantic Analysis)とあまり有名じゃないSSNB(Semi-Supervised Naive Bayes)。二つとも例題としてはかなり優秀だと思う。 論文 "Unsupervised learning by probabilistic Latent Semantic Analysis", JMLR, 2001 "Text Classification from
無向グラフの時の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万くらいだったから目ん玉戻った。 日本からピッツバーグへの直行便はない。 ちなみに片道航空券は往復航空券より高い。 意味不明だからいろいろ調べてみたら、往復航空券は格安ツアーの航空券を使ってたりするから安くなってるらしい。 荷
グラフのデータを手に入れたらまずは次数分布をプロットするのが定石だけど、なぜか毎回毎回実装しなおしててアホだったから反省してちゃんと書いた。 次数分布とそのCDF、CCDFをプロットする。 要Numpy, Scipy, Matplotlib, Networkx。 使い方 言わずと知れたEnron email networkで試してみる。 まずデータをSNAPから取ってくる。 余談だけどSNAPにはいろんなネットワークデータがあって、これ眺めてるだけで楽しくなってくるね。 $ wget http://snap.stanford.edu/data/email-Enron.txt.gz $ gunzip email-Enron.txt.gz 最初の4行は余計なものが入ってるので消す(tailで+5と指定すると5行目から最後までを出力してくれる便利機能があったなんて知らなかった)。 $ head
AAAI2015のOutstanding paper award honorable mention。発表聞いた時は何でこれが賞とったのかな?と思ったけど実際論文読んだら結構面白かった。 概要 Twitterユーザのいろいろな属性(年齢、性別、人種、収入、学位、子持ち)を推定する。面白いのはQuantcastのデータを使うところ。QuantcastはあるWebページに訪れる人の年齢とか性別とかの割合を出してる。例えば「LinkedInに訪れる人達の何%は男性です」とか。ここから得られるWebページとTwitterのアカウントを結びつけて、それをフォローしてる人たちの属性を推定する。 具体的には、「あなたはespnとwiredをフォローしてるから男性ですね?」とか、「あなたはPlayStationとsteam_gamesをフォローしてるから18-24歳ですね?」とかいう推定をする。 Rese
次のページ
このページを最初にブックマークしてみませんか?
『でかいチーズをベーグルする』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く