Fast and Exact Top-k Algorithm for PageRank [AAAI'13]
PageRankにおいて高速かつ正確にTop-kを求める
読んだ論文を忘れないうちにまとめておく．
この論文は，PageRankのTop-k検索を求める手法 F-Rank を提案した．
問題
Given: Arbitrary graph G and required number of answer nodes k.
Find: Top-k nodes with respect to thier PageRank scores exactly and efficiently.
提案手法
アイデア
反復計算の各ステップにおいて，
ノードの最終的なスコアの上限値，下限値を推定．
推定値に基づいて不必要なノードを枝刈りし，部分グラフを構築．
結果として，計算対象とするグラフのサイズが小さくなり，計算コストが削減される．
詳細
- 各ステップにおいて，推定値はO(1)でincrementallyに計算可能．
- 上限値，下限値は本来のスコアに収束する．
- k-th highest lower bound estimation を εk とすると，upper bound estimationが εk よりも小さいノードは解になり得ない．
- 解になり得るノードの集合を C，Cにreachableなノード集合をRとする．スコア計算はR全体に，推定値の計算はCを対象に行う．
実験
P2P，Web，Wikipediaの3種のデータセットを用いる．
実行時間
- オリジナルのPageRank計算と比較して，それぞれ40%，70%，90%削減された．
正確性
- オリジナルのPageRankで得られた結果と一致する．
以上より，高速かつ正確な結果が得られることが示された．
Macの読み上げ機能を使って英語の文書を読む
Macのデフォルトの読み上げ機能を使ってみたところ，思っていた以上に流暢な音声で読み上げてくれたので記事にまとめてみたいと思います．
Macの読み上げ機能
Macにはデフォルトで読み上げ機能が付いています．僕自身は読み上げ機能が付いていること自体はもともと知っていましたが，実際に使ったことはありませんでした．
大学4年次になってから論文などの英語の文章を読む機会が増えたため，試しに使って見ることにしました．
使い方
Mac標準のPDF表示アプリケーションであるプレビューを用いて説明したいと思います．読み上げたい文章を選択し，画面上部の「編集」から「スピーチ」を選択し，「読み上げを開始」を押すと読み上げが開始します．
デフォルトでは「Kyoko」という日本人女性の音声による読み上げが行われるため，英語の文章を読み上げた場合は片言の英語が音読されます．
システム環境設定から音声データを変更することができます．「システム環境設定」>「音声入力と読み上げ」を選択すると次の画面が表示されます．
「システムの声」>「カスタマイズ」を選択すると，音声データをダウンロードすることができます．
様々な言語のバリエーションがありますが，英語の場合は「Samantha」をオススメします．
ダウンロードが終了すると，無事にその音声が設定できるようになります．
長い文章の場合でも流暢に読み上げてくれるため，発音を確かめたい場合や音声によって頭にインプットしたい場合にとても有効です．
pythonの実行環境を整える
python2とpython3を切り替えるための方法がいろいろ公開されていますが、どれを使えば良いのかわからなかったのでメモ。
OSはMac OS X Yosemite (10.10.5)です。（El Capitanの別マシンでも同様に導入することができました。 ）
参考ページ
pyenv および virtualenv の使い方
pyenvでpythonのバージョンを切り替える
pyenvのインストール
まずはpyenvのインストールから。
$ git clone https://github.com/yyuu/pyenv.git ~/.pyenv
これでホームディレクトリ直下に.pyenvディレクトリがcloneされます。
そして.bash_profileに以下の3行を追記します。
zshを使っている方は.zshrcに追記してください。
export PYENV_ROOT=$HOME/.pyenv export PATH=$PYENV_ROOT/bin:$PATH eval "$(pyenv init -)"
シェルを再起動するか、
$ source .bash_profile
を実行して変更を反映します。
これでpyenvコマンドが使えるようになります。
pythonのインストール
pyenvを使ってpythonのいろいろなバージョンをinstallしていきます。
$ pyenv install --list
でインストール可能なpythonのバージョンの一覧が表示されます。
ここから仮に3.5.0をインストールする場合は下のコマンドを実行します。
$ pyenv install 3.5.0 $ pyenv rehash
rehashは~/.pyenv/shimsの更新をリフレッシュするコマンドです。
バージョンの一覧は
$ pyenv versions
で確認することができます。
いよいよバージョンの変更ですが、global、localの2通りの変更方法があります。
$ pyenv global 3.5.0
または
$ pyenv local 3.5.0
globalはシステム全体、localはそのディレクトリのみpythonのバージョンの変更を適用します。
実際にpythonのバージョンが変更したかどうかは以下のコマンドで確認することができます。
$ python --version
これで3.5.0に変更されていたら終了です。
もしシステムのデフォルトのpythonに戻したい場合はsystemに変更すれば大丈夫です。
$ pyenv global system
Gitの基本知識
Gitを使い始めて、便利だと思った機能等をメモ。
.gitignore
これはGitで管理する必要のないもの、例えば、エディタのバックアップファイル等を登録しておくことで、リポジトリの管理対象外にすることでできる。
*~ //emacs *.swp //vimのバックアップファイル
ファイル名を変更
ファイル名を変更するには
git mv foo bar
これでファイル名をfooからbarに変更できる。コマンド実行後はワーキングツリー、インデックス共にファイル名が変更された状態になっている。
直前のコミットを変更する
コミットした後にコミット内容やコミットメッセージを変更したいときは、間違いを訂正して新たにコミットを行う機能がある。それが--amendオプションである。
git add README
その後に以下のコマンドを実行すると直前のコミットが変更される。
git commit --amend
・コミットメッセージを修正する場合 この場合はすぐに以下のコマンドを打つと新たにコミットメッセージを入力できる。
git commit --amend
最新のコミット状態へ戻す
誤ってファイルを削除してしまったりした場合に用いる。 仮に.bashrcを削除してしまったとする。 このとき、ワーキングツリーからは削除されているが、インデックスには変わらずに登録されたままになっている。 そこで下のコマンドを実行すると、最新のコミット(HEAD)のときの.bashrcへ戻してくれる。
git checkout HEAD .bashrc
bareリポジトリ
リモートリポジトリを作成するときはbareリポジトリとして作成すると、変更のみを管理するリポジトリとなり、ワーキングツリーとインデックスとの差異で生じるトラブルを抑えることができる。
git init --bare
git config
git configは、ホームディレクトリにある.gitconfig、リポジトリ内の.git/configの2つあるが、優先順位としては後者が優先される。
git statusの詳細
On branch master: この状態でコミットすると、masterブランチにコミットされることを示す。
nothing to commit: ワーキングツリー、インデックスに対して変更がない場合。
Changes to be committed: ここに表示されるファイルは次回のコミットの対象になる。git addでインデックスに登録したファイルや、git mergeコマンドでマージされたファイルなどが含まれる。
Changes but not updated: ワーキンググリーで変更されているが、その変更がインデックスに登録されていないファイルが表示される。
Untracked files: ワーキングツリーには存在するが、Gitの管理対象外となっているファイルが表示される。
Gitを利用する準備
ホームディレクトリ下にあるいわゆるdotfilesを管理し、いろいろな端末から使えるようにするためにgitを導入することにした。
まずはgitをインストールする。
Mac OSの場合、MacPorts、Homebrewを用いると楽にインストールすることができる。
MacPortsの場合
sudo port install git-core
Homebrewの場合
brew install git
また、Linuxの場合はパッケージマネージャを用いて同様にインストールすることができる。 例えば、Debianの場合は
sudo apt-get install git
windowsはCygwin等を用いた方法があるらしいが、windowsのマシンが手元にないため省略、、、
Gitで使う名前、メールアドレスの登録
Gitでログインするユーザの設定は以下の通りである。
git config --global user.name "hogehoge" git config --global user.email foo@bar.hoge
こうすることで、この設定をしたPCにログインするユーザがGitを利用した場合、すべてのリポジトリに反映される。
基本的なワークフロー
１、リポジトリを作成 ２、ファイルの作成、編集 ３、インデックスへ登録 ４、コミット
2〜4を繰り返すことが基本的な流れである。
リポジトリの作成は、管理したいディレクトリ(dotfilesとする)に移動して
git init
と打つだけである。 これで.gitディレクトリが作成される。 この場合、dotfilesディレクトリが作業領域、.gitディレクトリがリポジトリという扱いである。
このリポジトリで.bashrc、.bash_profileを管理する場合、リポジトリにこれらのフィアルを登録する必要がある。 そのため、ホームディレクトリにある.bashrc、.bash_profileをdotfilesディレクトリに移動し、ホームディレクトリに対して移動したファイルのシンボリックリンクを貼る。 こうすることで直接ホームディレクトリにリポジトリを作らなくて済む。
cd ~ mv .bashrc .bash_profile dotfiles ln -s dotfiles/.bashrc . ln -s dotfiles/.bash_profiles
これで2つのファイルはワーキングツリーには存在している状態にはなったが、Gitの管理対象にはなっていない。
そこでインデックスにファイルを登録する。
git add .bashrc .bash_profile
これで初めてリポジトリへコミットすることができる。 コミットするにはコミットメッセージが必要であるため、-mオプションで"Initial commit."等を指定する。
git commit -m "Initial commit."
コミットの履歴は
git log
で確認することができる。 -pオプションを指定すると実際にどのように変更したかが表示される。
ここから新たにファイルを編集する場合は、編集するたびにaddし、それをcommitすれば良い。
基本的な操作は以上である。
