でこすけの日記

”The Little Redis Book”の翻訳を少しずつやってる。

ウソには3種類ある。ウソ、みえすいたウソ、そして統計だ

というわけで数字を扱うにはいろいろなトリックがあるのですが、この問題が面白かったので考えてみました。

http://chrisladroue.com/2012/01/winning-from-losing/

翻訳すると、

• ゲーム1: 0.49の確率で1ポイント獲得、0.51の確率で１ポイントを失う
• ゲーム2: 現在のポイントが３の倍数なら、確率0.095で１ポイント獲得、確率0.905で１ポイントを失うゲームを行う。３の倍数でないなら、確率0.745で１ポイント獲得、確率0.255で１ポイントを失うゲームを行う
• ゲーム3: 毎回コインを振り、表が出たらゲーム1、裏が出たらゲーム2を行う
• それぞれのゲームは1000ステップ行い、最後ステップ終了時のポイントを得点とする。

ゲーム１とゲーム２は平均すると負ける*1のに、その２つを半分ずつ合わせたゲーム３は平均すると勝てます*2。つまり、勝てないゲームを２つあわせると勝てるゲームになるのです。

なぜでしょう？

全ての人間は二つに分けられる

何事も分類するのは人類の常、幸せになるための方法ということで、データを分類するのは非常に有用です。そして計算機でデータを分類するためのもっとも簡単なモデルは、単純ベイズモデルです。このモデルでは分類に対するデータの影響を全部独立と仮定します。

と、まあそれは置いておいて・・

Rで単純ベイズを使うためには、id:kosugittiさんのベイズな予測にあるように、package:e1071を使うのが一番楽みたいですね

このnaiveBayes関数はデータが正規分布に従うと仮定されているのだけど、もっと一般な分布に対してはどうすればいいのでしょう。まあ単純ベイズぐらいだったら自分で書けという話かもしれないですね

Rのpackageの探し方が知りたいです。今は適当にgoogleで検索しているけど、有名なアルゴリズムに対して、「このアルゴリズムはこのpackageを使うのが定番」みたいなものはどうやって見つけるのでしょう

モチベーション

• 最近のウェブサービスは、関連したデータを集めてくるのが上手いですよね。facebookやSPYSEEの「知り合いかも」機能が異常に精度が良くて怖いです。これらは人同士の近さ、親密さを機械学習によって計算しています。
• そんなわけで、データ同士の距離を測ってみましょう。最近クローラの話をたまにしていたので、ウェブページのクローラを使って、単語同士の距離を計ってみます。

RW(ランダムウオーク)

酔った人みたいに、一定確率でランダムに隣の場所に歩いていくモデルです。そういえば、今日帰宅途中にお土産を持ってふらふらしているサラリーマンを見ました。

隣の場所に歩くときに、サイコロを振ってランダムにどこにいくか決めるのでモンテカルロ法に分類されます。このランダムウオークが今回の道具です。

RWR(Random Walk with Restart)

さきほどのランダムウオークに加えて、一定確率で開始地点に戻ってやりなおすモデルです。

実験：モナドと近い単語

Haskellにおける魅惑の単語、モナドと近い単語を探してみましょう。より具体的に言い換えれば、Monadを開始地点にしてHaskellWikiでRWRしてみましょう。リンクをランダムにたどります。

実験結果

1000回クロールの結果、モナドに近い単語は

到達回数	単語
1162	Monad
880	Haskell
103	Monads_as_computation
89	Functor
84	Base_package
79	Monad_laws
78	Monads_as_containers
72	Syntactic_sugar
67	Sudoku
62	Monad/ST
56	What_a_Monad_is_not
55	Haskell_in_industry
53	Research_papers/Monads_and_arrows
53	Haskell_Communities_and_Activities_Report
51	DSL
45	Language_and_library_specification
42	IRC_channel
42	Haskell_in_research
39	Parallel
39	Mailing_lists
39	Functor_hierarchy_proposal
37	Tutorials
35	Learning_Haskell
35	Hac_Boston
33	Applications_and_libraries
31	Haskell_in_education
31	Foreign_Function_Interface
27	Books
25	Liyang/sudoku.hs
25	Introduction
24	HakkuTaikai
24	Arrow
22	Functional_programming
21	HaskellImplementorsWorkshop/2011
17	ThingsToAvoid/Discussion
17	Research_papers
14	Conferences
12	The_Other_Prelude
12	All_About_Monads
11	Syntactic_sugar/Pros
11	Consultants
10	Solution1.html
10	Parallel/Research
10	Jobs
10	Functor-Applicative-Monad_Proposal

上のほうは割とモナドっぽいですね。実際にモナドに関係のあるAll_About_Monadなど、Monadのページから少し距離があるページも抽出できました！

でもモンテカルロって遅いよね

はい、乱数を使って収束するまでやるような計算は、わりと効率が悪いことが多いです。

実際は、ランダムウオークをした結果とまったく同じものを、グラフからの行列計算で求めることができますが、それはまた別の機会に・・・

ソースコード

import Network.Shpider
import System.Random (getStdRandom, randomR)
import Control.Concurrent (threadDelay)
import Data.Map ((!))
import Data.List (sort)
import System (getArgs)
import qualified Data.Map as Map
import Debug.Trace
traceS a = trace $ show a

getLinks :: String -> IO [String]
getLinks url = do
  links <- runShpider $ do
    download url
    currentLinks
  return $ fmap linkAddress links

randomWalkWithRestarts :: Int -> String -> String -> IO (Map.Map String Int)
randomWalkWithRestarts iterNum baseUrl start = do
  paths <- mapM (\x->rwr baseUrl start []) [1..iterNum]
  let pathsMap = map (\path -> Map.fromListWith (+) $ zip path (cycle [1]) ) paths
  return $ Map.unionsWith (+) pathsMap

filterLinks :: String -> [String] -> [String]
filterLinks baseUrl urls =
  let urlSubs = [drop l url | url<-urls, take l url == baseUrl] in --baseを削った
  [urlSub | urlSub<-urlSubs, not $ elem '#' urlSub,
    not $ elem '?' urlSub, not $ elem ':' urlSub] -- #?:を含むURLは除外
  where l = length baseUrl

randomChoose :: [a] -> IO a
randomChoose xs = do
  count <- liftIO $ getStdRandom (randomR (0, length xs - 1))
  return $ xs !! count

rwr :: String -> String -> [String] -> IO [String]
rwr baseUrl current path = do
  threadDelay 1000 --sleep 1sec
  coutinueCount <- traceS path $ ( liftIO $ getStdRandom (randomR (0, 3)) )
  if coutinueCount == (1::Int) 
    then return (current:path)
    else do
      links <- getLinks (baseUrl ++ current)  
      let flinks = filterLinks baseUrl links
      if length flinks == 0 then return (current:path) 
      else do
        link <- randomChoose $ flinks
        rwr baseUrl link (current:path)

startPoint = "http://www.haskell.org/haskellwiki/Tutorials"

main = do
  argv <- getArgs
  let iterNum = read $ argv !! 0 --RandomWalkのトライ回数。1だと無限ループするので注意　
  result <- randomWalkWithRestarts iterNum "http://www.haskell.org/haskellwiki/" "Monad" 
  let resultFreqOrd = reverse.sort $ map (\x -> (snd x, fst x)) (Map.toList result) --頻度順にソート
  mapM_ (\x->putStrLn $ (show $ fst x) ++ " " ++ (snd x)) resultFreqOrd

  runghc rwr.hs 1000

問題点

今回の手法の問題点としては

• すべてのリンクを同じ重要さで考えています
• 自己リンク、相互リンクをしているページが強く出ます
• 意味的な解析をしていません。グラフ的な距離の近さ、強さしか見ていません。

などがあります。

参考文献

『涼宮ハルヒの憂鬱』から遠く離れて - だいたいこれが元ネタです

”Supervised Random Walks:Predicting and Recommending Links in Social Networks” - facebookのリンク予測のお話です。RWRと最適化問題

Haskellでクローラを書く方法を少し調べてみたけど、hackage:shpiderが一番近そうですね。up-to-dateみたいだし。

http://hackage.haskell.org/packages/archive/shpider/0.2.1.1/doc/html/Network-Shpider.html

はてなダイアリーからはてなブログに移行したい。