分からんこと多すぎ

何故か就職できたので技術磨く。一人前の多重線形代数使いを目指しつつ、機械学習、データマイニングをやる

はてなブックマークをデータマイニングした_2013年_06月-09月

DataMining R

概要

TwitterなどのSNSは、自分の興味ある話題を共有できるユーザのグループを見つけ、その人達とオススメ情報を共有するのが、メジャーな使い方でしょう。

したがって、私のようなコミュ症は、そもそもSNSに向いていません。


そこで本記事では、はてブユーザたちが形成する、

同じ話題（タグのグループ）に興味を持っている

ユーザの集団と、

彼らが有用と判断した記事郡を、勝手に解析して紹介します。

人と話す必要はないので，安全安心です．


また、そのユーザの集団の中でも特に、有用な記事を発掘してくるユーザのランキングも、合わせて記載します。

（名前出すのがまずかったら消します）


データ自体は古いので、主に、お気に入り登録すべきユーザを発見するために利用して貰えたら幸いです。

解析手法（高校生向け）やデータの詳細は、最後の方を参照してください。

はてブのデータマイニング結果

このページには新着ブックマーク四ヶ月分まとめて解析した結果出てきた49カテゴリ中、

上位３カテゴリのみを書くので、もっと詳しく知りたい人は別記事参照。

「順位，クラスタ名（適当につけました）・全体から見たそのクラスタの大きさ」でタイトルをつけています。

あくまで新着ブクマの順位なので，どれだけ結束力が強くて高速に情報を広める人たちの集団かという順位です．

第１位・スマートフォン・4.4%

記事ランキング（クラスタの中で著名な記事）

  1. CNET Japan
  2. iPhone 5s / 5c 価格比較：auソフトバンク横並び、ドコモは総額高の実質安。各社 MNP 乗りかえ施策 - Engadget Japanese
  3. ドイツのハッカー集団、複製した指紋でAppleのTouch IDを迂回 | TechCrunch Japan
  4. Apple - Press Info - NTT DOCOMO & Apple Team Up to Offer iPhone in Japan on Friday, September 20
  5. iOS 7の一般公開を控えて、旧バージョンiOSデバイスに旧バージョン向けアプリのインストールが可能になっている | TechCrunch Japan
  6. Google、テレビのHDMI端子に挿すChromecast を発表。価格は35ドル - Engadget Japanese
  7. アップル - iPhone 5c
  8. 現在、僕が iPhone5 にインストールしてるアプリ全115個のまとめ備忘録。
  9. ライフスタイルを彩る「5c」、未来を映す「5s」：どちらも期待を裏切らない“正統進化”――林信行の「iPhone 5c／5s」徹底レビュー (1/4) - ITmedia PC USER
  10. iOS 7にアップデートしてはいけない7つの理由 LINEに通知の不具合も

ユーザランキング（クラスタの中で先駆的なユーザ）

  1. a_matsumoto：期間内合計ブクマ数174
  2. yadokari23：496
  3. anegishi：62
  4. ayaniimi213：349
  5. androidzaurus：337
  6. s_nagano：25
  7. riocampos2：77
  8. mpresso：57
  9. Kmusiclife：57
  10. daichiman：23

25とかでランキングに食い込んできているs_naganoさんとかが、特にこのクラスタのみ集中して調べている人です。

タグランキング（クラスタが共有する話題）

  1. iphone
  2. android
  3. ニュース
  4. webサービス
  5. mobile
  6. google
  7. myinterest
  8. ios
  9. apple
  10. myhotentry



第２位・2chまとめ（サッカー）・4.2%

記事ランキング（クラスタの中で著名な記事）

  1. 名古屋、2ステージ制反対の横断幕を置いていく…ほか各会場の2ステージ制反対横断幕まとめ : footballnet【サッカーまとめ】
  2. 日韓戦で旭日旗…横浜FMに問い合わせ殺到しクラブ側がコメント発表「旭日旗を降った人物は三年前の事件によりスタジアム無期限入場禁止処分を科しています」 : footballnet【サッカーまとめ】
  3. 本田、ミラノ入り情報もあったが、きょうのCSKAの試合にスタメン出場濃厚 : footballnet【サッカーまとめ】
  4. ザックジャパン、東アジア杯豪州戦の視聴率は14.7％ : footballnet【サッカーまとめ】
  5. 梶山陽平をググるとなぜかFC東京のユニを着た柴田理恵が出てくると話題 : footballnet【サッカーまとめ】
  6. J1第17節、広島が首位浮上で折り返し！大宮は連敗…「新代表組」も活躍 : footballnet【サッカーまとめ】
  7. FC東京vs.浦和でも2ステージ制などに反対する横断幕相次ぐ（画像あり） : footballnet【サッカーまとめ】
  8. コンフェデ開幕戦、日本代表はブラジルに0-3完敗！ : footballnet【サッカーまとめ】
  9. 大久保嘉人、J1得点ランク単独トップ 「（代表に）入りたいわ。マジで」「ザックは見ないと思うけど原さんは見るでしょ」 : footballnet【サッカーまとめ】
  10. 本田のミラン移籍、昨日の「今夜が山田」経緯まとめ…CSKAひどすぎる : footballnet【サッカーまとめ】

ユーザランキング（クラスタの中で先駆的なユーザ）

  1. footballnet：期間内合計ブクマ数537
  2. ganthekei：678
  3. toronei：1811
  4. pycol
  5. sunset641229
  6. hiroyukixhp
  7. akillertwit
  8. ksk130421
  9. quamaboco
  10. shinchi

タグランキング（クラスタが共有する話題）

  1. 2chまとめ
  2. サッカー
  3. football
  4. 2chまとめブログ
  5. soccer
  6. 2ch
  7. 笑
  8. 蹴球
  9. 香川真司
  10. jリーグ



第３位・yahooニュース・3.9%

記事ランキング（クラスタの中で著名な記事）
全部yahooで元記事が消えてる…。

ユーザランキング（クラスタの中で先駆的なユーザ）

  1. news_creeper：期間内合計ブクマ数1875
  2. daybeforeyesterday：2491
  3. pycol：5370
  4. Babar_Japan
  5. kai--to
  6. akb48all365
  7. iwax666
  8. uriuri2000gt
  9. ROYGB
  10. mikinews

タグランキング（クラスタが共有する話題）

  1. yahooニュース
  2. hatena
  3. 社会
  4. あとでみる
  5. news
  6. 凍てつく波動
  7. 政治
  8. エンタメ総合
  9. myhotentry
  10. clip



第20位・ニコニコ動画（アイマス）・2.0%

記事ランキング（クラスタの中で著名な記事）

  1. 【im@sDSフェスタ4th】 アイドルマスターDSは続いていく ‐ ニコニコ動画:GINZA
  2. 春香さんがクッキーを焼くそうです ‐ ニコニコ動画:GINZA
  3. 【アイドルマスター】ロックマン的I Want ‐ ニコニコ動画:GINZA

ユーザランキング（クラスタの中で先駆的なユーザ）

  1. nico_imas
  2. Mash
  3. DRUMSCO

タグランキング（クラスタが共有する話題）

  1. ニコニコ動画
  2. アイドルマスター
  3. idolmster



第42位・ゲーム・1.5%

個人的に好きなゲームクラスタ

記事ランキング（クラスタの中で著名な記事）

  1. 「ドラゴンズクラウン」は自分が一番作りたかったゲーム――ヴァニラウェアの神谷盛治氏に，完成までの道のりを聞く - 4Gamer.net
  2. ［TGS 2013］「METAL GEAR SOLID V THE PHANTOM PAIN」の疑問に小島監督が答える。Q＆Aセッションで見えてきた新世代のMGSが目指すもの - 4Gamer.net
  3. 『ぷよぷよテトリス』が発売決定、2大パズルゲームが夢の頂上決戦!! - ファミ通.com

ユーザランキング（クラスタの中で先駆的なユーザ）

  1. gogorou
  2. otori_r
  3. a6u

タグランキング（クラスタが共有する話題）

  1. ゲーム
  2. game
  3. interview
  4. ぷよぷよ
  5. 任天堂



第48位・炎上・1.2%

ブービー賞

記事ランキング（クラスタの中で著名な記事）
加盟店従業員の不適切な行為についてのお詫びとお知らせ
コンビニ店員がアイスの冷蔵ケース内で寝転ぶ写真、Facebookに ローソンが謝罪、FC契約解除 - ITmedia ニュース
痛いニュース(ﾉ∀`) : 【Twitter】 お好み焼き屋「道とん堀」で客がソース容器を鼻に突っ込んだ写真公開→大炎上 - ライブドアブログ

ユーザランキング（クラスタの中で先駆的なユーザ）

  1. daybeforeyesterday
  2. silverscythe
  3. westerndog

タグランキング（クラスタが共有する話題）

  1. 炎上
  2. 社会
  3. 事件
  4. web
  5. ビジネス
  6. コンビニ
  7. ネタ
  8. ニュース
  9. twitter
  10. facebook



総評

iPhoneクラスタの団結力はやばい。

結束力が強くて情報をいち早く集める人は、iPhoneらしいです。

あるいは、はてなユーザにiPhoneの人が多いのかもしれません。


パラメータチューニングしていないので、細かく分けすぎた気がする。

もっとおおまかに、政治経済とかエンタメとか、はてブの公式クラスタくらいに分けて比較してみたい。


なお、毎日解析することも可能です。

そうすると、その時々で流行っているワードのクラスタが分かります。

あとは、痛いニュース見てる人に、近いクラスタ（計算すれば分かります）の政治経済を見せるとか、そういう使い方も。

スマホのアプリ需要あるなら、たぶん1年くらいかかるだろうけれど、1からObjectve-CとかMongoDBとか勉強して作ります。


実験設定他

データ はてブ2013_06-09新着ブックマーク（4ヶ月分）
記事数 34,122記事
ユーザ数 21,251ユーザ
タグ種類数 15,054タグ
手法 初代Google検索の中の人（HITS）の父の親戚の友達的なもの
そのうち説明書きます（今回は細かめのクラスタ用パラメータ）
言語 R（フィボナッチ数列作るのにFortranの1600倍くらい時間かかる）
コア数 1コア（手法自体は並列化可能）
解析時間 間違って消したので不明．この2-3倍量のデータで30分-60分くらい



手法（HITS）の解説

高校生向け．

死ぬほど長いので，暇な人のみ読んで下さい．



インターネットにおけるつながりを可視化すると，以下のようになります．

f:id:rishida:20140118131213p:plain

数字が振ってあるのがノード（WebページやSNSユーザ），数字をつないでいるのがエッジ（リンクやフォロー）です．

インターネットにおけるつながり（グラフ構造）を，行列にすると，以下のように表すことができます．

f:id:rishida:20140118132051p:plain

ノード（Webページ）ｉとノードｊの間にエッジ（リンク）があれば，行列Rのｉ行ｊ列に1を入れています．


以下は，とりあえず，Webページの例で説明します．

記事自体に価値のあるWebページは，たくさんのページから被リンクを受けます．（仮定１）

有用な記事を拾ってくるWebページは，たくさんのページにリンクを張ります．（仮定２）

根気のあるユーザたちはWebリンクをたどり続けることにより，最終的には価値のあるWebページにアクセスすると予想できます．（仮定３）


では，それを数学で再現しましょう．

ここで，このグラフ構造（Webリンク）にしたがって，無限の人数のユーザが無限回リンクを踏んで移動した時のことを考えます．

その時，最終的にどのくらいの割合のユーザが，あるWebページｉに到達するのかを計算すれば，それは（仮定３）でのアクセス数と，大体一致するはずです．


じゃあやってみようということで，無限のユーザUを用意します．

u^{T}= (\begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \end{array} )

これは，今各ページにいるユーザの割合を示すベクトルです．（実際は（1+2+3+4+5+6+7）で割ったものを使います）

要素番号とWebページが対応しています．

つまり，初期段階でWebページ１を見に行った人は，全体の 1/(1+2+3+4+5+6+7) = 1/28 人になります．


そして，この人達が記事内容に満足できず，各Webページにあるリンクを踏んだとします．

（行列のｉ行ｊ列が１だと，Webページｊからｉへリンクがあることとします．）

各列は，列和で割られているものとします．１列目は全部1/3，７列目は全部1/2です．

以後，この行列をRと呼びます．

Webページ１は，Webページ2,3,4からリンクを張られているため，それらのページにいた人(2+3+4)/(1+2+3+4+5+6+7) が，Webページ１に流入してきます．

例えば，Webページ２にいる人は，Webページ２が張っている４つのリンク（行列の2列目）から１つを選ぶでしょう．

つまりWebページ２のユーザの1/4が，Webページ１に流入してきます．

2/(1+2+3+4+5+6+7)（人数）× 1/4 （リンクを踏む確率）= 2/(4*(1+2+3+4+5+6+7))

が，Webページ２からWebページ１へ流入する人です．


同様の計算をすると，Webページ１にいるユーザは，(2*3 + 3*4 + 4*4)/(4*3*(1+2+3+4+5+6+7))であることが分かります．

これは，行列Rの１行目と，ベクトルuの積を取ったものに一致します．

つまり，行列Rとベクトルu=u(0)　（時刻tのベクトルをu(t)と書きます）の積を取ると，それは１回リンクを踏んだあとの，各ページにおけるユーザの割合u(1)になります．

u(1) = R u(0)

では，無限回，行列Rとベクトルu(t)の積を取ると，どうなるでしょうか？


それは，Webリンクにしたがって，無限の人数のユーザが無限回リンクを踏んで移動した状況（仮定３）と，一致するはずです．


無限回行列とベクトルの積を取ると，ある１つの状態に落ち着くことが知られています．

それは一般に，固有ベクトルと呼ばれています．

固有ベクトルというものは，無限回の積なんて取らなくても，求めることができます．

（興味のある人は，べき乗法やコレスキー分解を調べてください）

なので，一瞬で無限回リンクを踏んだ時の，各ページの人数比を知ることができます．

u( \infty )=(\begin{array}{cccccccc} 0.46 & 0.52 & 0.46 & 0.46 & 0.24 & 0.11 & 0.11 \end{array} )

ここで，この値とWebリンクの構造を見比べてみましょう．

f:id:rishida:20140118131213p:plain

実際に，一番被リンクの多い，Webページ２が，u(∞)で最大の値を取っています．

つまり，u(∞)の値が大きい順で，良いWebページであるということが分かりました．

めでたしめでたし．



蛇足

面白いデータがありそうなサービスや、詳しく解析して欲しいタグ教えて下さい。

なんでもいいのでSNSまわりのデータ下さい。ビッグデータ欲しい。ある地域のルータのアクセスログ一ヶ月分とかでも小さい。

今は新着RSSからデータを抜いているんですが、もっとはてなブックマークのサーバに負荷をかけないデータの取り方を、どなたか教えて下さい。

Internet，*internet，03_net，インターネット，ネット，みたいなタグは涙出るので統一してください。

あらゆる種類の記事に出てくる「あとで読む」「まとめ」「これは酷い」とかも勘弁してください。

RユーザのためのJulia入門（行列編）

Julia（プログラミング言語）が、高速で取っ付き易い言語との噂だったので、Deep押し過ぎのNIPSで折れた心を癒やすために、遊んでみる。

なお、本当にRしか書けない底辺コーダーなので、言語の仕様とかは他のページを見てください。

この記事は、とりあえずJuliaの配列操作が知りたい人向けの、公式文書の抜粋みたいなものです。

書いてる途中で発見したのですが、↓を読むのが一番早いと思います。

Multi-dimensional Arrays — Julia Language 0.3.0-dev documentation

Juliaとは

The Julia Language

高速で、簡単に学べて、数学っぽい書き方ができる言語。

公式いわく、Cの半分くらいの早さらしいです。

設計理念的な話は↓

なぜ僕らはJuliaを作ったか - 丸井綜研

きちんと勉強したい人は↓

Julia Documentation — Julia Language 0.3.0-dev documentation

基本的な話

拡張子.jlでファイルを作ってコンパイル＆実行できるようですが、今回はお試しなので対話的に書きます。

コメントアウトは"#"、代入は"="

julia> #コメントアウトは"#"

julia> x = 2
2

プリントはこんな感じ

julia> print("x is equal to ", 2)
x is equal to 2

積には3通りの書き方がある。

julia> (x + 1) * x
6

julia> (x + 1)x
6

julia> *(x,x+1,x+2)
24

後ろに(x+1)みたいに書くのはダメ。

julia> (x + 1)(x + 1)
ERROR: type: apply: expected Function, got Int64

"*"記号がない場合、かけるもの同士の間にスペースを入れるのはダメ。

julia> 2 (x + 1)
ERROR: syntax: extra token "(" after end of expression

"ans"で前回の演算の答えが呼べる。ただしエラーは除く。

julia> ans
24

関数は以下のように書く。

function multi(x::Int,y)
    x*y
end

julia> multi(3,4)
12

xはInt型で宣言しているので、Float型は計算できない。
Vector型やMatrix型があって便利。

julia> typeof(1.1)
Float64

julia> multi(1.1,2)
ERROR: no method multi(Float64,Int64)

julia> multi(1,2.1)
2.1

for文とif文はこんな感じ。
複数返り値は","で区切れば良い。タプルで帰ってくる。

function foo(n)
  x = 0
  for i = 1:n
    if x < 5
      x = x + 1
    else
      x = x + 2
      return(x, 10)
    end
  end
  x
end

julia> foo(5)
5

julia> foo(15)
(7,10)

配列の操作

RユーザがPythonを投げ出す最大の理由は、配列の操作が煩雑なことだと思う。

なので、今回は配列の操作の話をする。

ベクトルは[]で作る。

julia> a = [1:3]
3-element Array{Int64,1}:
 1
 2
 3

要素番号で配列の中身が呼べる。

julia> a[2]
2

julia> a[[3,1,1,2,3]]
5-element Array{Int64,1}:
 3
 1
 1
 2
 3

true,falseでも配列の中身が呼べる。

julia> a[[true,false,true]]
2-element Array{Int64,1}:
 1
 3

行列積は"*"、転置はtranspose()

julia> A = a * transpose(a)
3x3 Array{Int64,2}:
 1  2  3
 2  4  6
 3  6  9

julia> transpose(a) * a
1-element Array{Int64,1}:
 14

行列の生成はこんな感じ

#単位行列
julia> x = eye(2,3)
2x3 Array{Float64,2}:
 1.0  0.0  0.0
 0.0  1.0  0.0

#乱数
julia> x = rand(2,3)
2x3 Array{Float64,2}:
 0.440441  0.608175  0.123271
 0.636391  0.30175   0.560413

#変形
julia> x = reshape(1:12, 3, 4)
3x4 Array{Int64,2}:
 1  4  7  10
 2  5  8  11
 3  6  9  12

行列の中身の呼び出しは、完全にR。

Pythonでテンソル操作して泣きそうになったので、この仕様は神だと思った。

julia> A
3x3 Array{Int64,2}:
 1  2  3
 2  4  6
 3  6  9

#左上から数えて五番目の要素を取り出す
julia> A[5]
4

#行列の二行二列の要素を取り出す
julia> A[2,2]
4

#行列の第二要素を二回取り出す
julia> A[[2,2]]
2-element Array{Int64,1}:
 2
 2

#1,2行かつ2,3列の要素を取り出す
julia> A[[1,2],[2,3]]
2x2 Array{Int64,2}:
 2  3
 4  6

#要素番号を指定して、関数で呼び出すこともできる
julia> getindex(A,[1,5])
2-element Array{Int64,1}:
 1
 4

代入も可

julia> A[1:2,2:3] = -1
-1

julia> A
3x3 Array{Int64,2}:
 1  -1  -1
 2  -1  -1
 3   6   9

要素ごとの積も取れる。

julia> A .* A
3x3 Array{Int64,2}:
 1   1   1
 4   1   1
 9  36  81

テンソル（R的にはArray）も作れます。

julia> x = reshape(1:12, 3, 2, 2)
3x2x2 Array{Int64,3}:
[:, :, 1] =
 1  4
 2  5
 3  6

[:, :, 2] =
 7  10
 8  11
 9  12

スパース型を標準装備。

julia> I = [1, 4, 3, 5]; J = [4, 7, 18, 9]; V = [1, 2, -5, 3];

julia> S = sparse(I,J,V)
5x18 sparse matrix with 4 Int64 nonzeros:
	[1 ,  4]  =  1
	[4 ,  7]  =  2
	[5 ,  9]  =  3
	[3 , 18]  =  -5

exitで終了できます。

exit()

以上でとりあえず行列まわりは大丈夫だと思います。

誰かがわかりやすいwikiを作ってくれますように。

RecSys2013のBestPaperを読む_Fast_Parallel_SGD

MachineLearning

RecSys 2013 (Hong Kong) - RecSysのbest paperが、なんだか面白そうだったので読む。

A Fast Parallel SGD for Matrix Factorization in Shared Memory Systems

著：Yong Zhuang, Wei-Sheng Chin, Yu-Chin Juan, and Chih-Jen Lin

本論文自体は、Matrix FactorizationのためのSGDの拡張である点が、他の論文とは違うらしい。

序論は確率的勾配降下法（SGD）の並列化について - 分からんこと多すぎに書いたので、本文の3章（SGDの並列化に関する諸問題）からになる。

また結論から言うと、計算速度は従来手法の十倍程度になる。

ただし、プログラミング上のテクニック的な話なので、理論とかあんまりない。

勉強になるし実用的で、企業的にはすごく身になる話なのだろうけれど、数学的な面白さはない。

Problem in Parallel SGD Methods For Matrix Factorization

SGDの並列化には、Locking Problemという問題と、Memory Discontinuityという問題がある。

Locking Problem

並列化において、すべてのスレッドを常にbusy状態にすることは、重要である。

Locking Problemというのは、他のコアの処理が終了するのを待つために、アイドリング状態になることを指す。

また、この問題は、分割したあとの行列Rの各ブロック行列がアンバランス（疎密の差が激しい状態）だと、より深刻になる。

密部分の更新には時間がかかるが、疎部分の更新には時間がかからないため、多くの疎部分の更新に割かれているスレッドが、待ちの状態にならざるを得ない。

分割したブロック行列の密疎の差をなくすための、簡単な方法として、random sufflingというものがある。

これは、行列の行のインデックスや列のインデックスを、ランダムに並べ替える方法である。

しかしこの方法でも、各ブロック行列に入っている要素の数は同じではないし、よしんば同じだったとしても、必要な更新時間は異なっている。

（訳注：おそらく大規模行列だと、この辺りの僅かな無駄の影響が、無視できないほど大きいのだろう）

ちなみにDSGDではメモリが共有されていないので、スレッド間の対話（更新値の渡し合い）の方が、スレッドのアイドルの問題よりも重要視されているようである。

Memory Discontinuity

プログラムが不連続的にキャッシュにアクセスするとき、キャッシュミス（参照すべきデータがキャッシュ上になく、メインメモリにアクセスしに行くこと）を頻繁に起こし、パフォーマンスが低下する。

HogWildやDSGDでの実装では、更新時にランダムに行列Rの一部を取り出すため、この問題に苦しめられる。

（筆者たちはこれをRandomMethodと呼称している）

The reason is that not only are rating instances randomly accessed, but also user/item identities become discontinuous.

（これはデータのインスタンスにランダムにアクセスするためだけでなく、ユーザ/アイテムのインデックスが処理ごとに切り替わるためである、の意？）

HogWildとDSGDではこの問題の深刻さは若干異なっている。

HogWildではそれぞれのスレッドでランダムにアクセスするため、行列R,P,Qの全てにおいて、Memory Discontinuityが起きる。

対してDSGDでは、ブロックの中でランダムにアクセスされるだけなので、本論文ではここでの問題を軽減するように、手法を改善する。

Fast Parallel SGD

本論文内では、lock-free scheduling とpartial random methodを提案する。

これは、Locking ProblemとMemory Discontinuityを解決するためである。

Lock-Free Scheduling

DSGDに習って、行列Rをブロックに分割する。

そしてs個のスレッドをbusy状態にし続けられるように、スケジューラを設計する。

ブロックBijが他の処理中のすべてのブロックから独立なとき、これをfree blockと呼ぶ。

一方そうでない時を、non-free blockと呼ぶ。

スレッドが処理を終えた時、スケジューラは、以下の2つの基準にしたがって、新たなブロックを割り当てる。

  1. 割り当てるblockがfree blockであること
  2. すべてのfree blockの中で最も更新回数が少ないこと

両方の条件を満たしたものが複数ある場合は、ランダムに1つ選択する。

s個のスレッドが与えられた時、少なくとも行列Rを（s+1）×（s+1）個に分割する。

f:id:rishida:20131117150804p:plain

上の図では、R00をスレッドT1で処理し、R22をスレッドT2で処理している。

今、T2における処理が完了したとすると、そのスレッドを用いて、R11、R12、R21のうちの１つを新たに割り振り、処理を行う。

このようにすることによって、Locking Problemを回避することができる。

ただし、あるブロックに多くの要素が固まっている場合、そのブロックの更新回数は必然的に少なくなってしまう。

簡単な救済策としては、前述したrandom shufflingがある。

（筆者たちの体感だが、random shuffle後は、最も密なブロックの要素数は、最も疎なブロックの要素数の二倍に、届かない程度になるらしい）

ブロックの更新回数の差に関する指標を求めて計算したところ、ほぼ差がなくなっていることが、図に示されている。

ただ、Random

Partial Random Method

Memory Discontinuityを解決するために、Random Methodに対抗して、ordered methodというものを導入する。

これは、userあるいはitem方向に関して連続的に選択していく方法である。

f:id:rishida:20131117154612p:plain

例えば上図のようにアクセスすると、Pに連続的にアクセスできる。

アクセスの順番が固定されていれば、元の行列Rを同じ順序でメモリに格納することで、同じ順序で連続的なアクセスが可能となる。

ただ、ordered methodは確かに連続的にアクセスできるようになるが、経験的には安定的なものではないと言える。

learning rate（最急降下法の係数γ）を変化させると、RandomMethodの方が高速になる場合があるのである。（図9）

つまり、収束性という観点においては、RandomMethodの方が良いと言えるのかもしれない。

例えばcoordinate descent methodにおいては、ランダムな更新の方がはるかに収束速度が早い。

そこで、筆者たちはPartial random methodを導入する。

f:id:rishida:20131117160127p:plain

上図で示したように、ブロック内の更新は順番に（ordered methodで）行うが、ブロックの選択においては乱択にする。

他文献[4]に示されている関連手法に関する調査では、ordered methodの方がrandom methodよりも収束が悪いと言っている。

これは筆者たちが実験的に示した結果とは逆の結果となる。

それに関して考えうる理由としては、筆者たちがRMSE（最小二乗誤差）を指標としているのに対して、訓練誤差を見ていることが上げられる。

おわりに

あとはFPSGD早いという実験結果が載っているだけなので、省略する。

大体既存の十倍くらい早い。

FPSGDのMethod間の比較では、Partial Random Method最強らしい。

Rでパッケージを書くべきか悩む。

超訳してたらごめんなさい。している気はする。