Hatena::ブログ(Diary)

でこすけの日記

2012-07-22 HaskellのSystem.Random

Haskell乱数生成関数getStdRandomは、Global Random Generator (GRG)の値を書き換えるためIOになる。GRGはSystem.RandomにtheStdGenという名前で定義されていて、グローバル変数 (IORef)である。GRGに頼らないで自前のRandom Number Generatorを使うこともできる。

つまり

--IOで乱数を取る(Global Random Generatorを読んで書き換える)
rollDice :: IO Int
rollDice = getStdRandom (randomR (1,6))

--自前のRandom Number Generatorを与えると、IO無しで書ける
gen = mkStdGen <ここに適当なseed値>

--1個だけ変数を取る
(fst (random gen))::Int

--10個変数を取る
getRands :: Random a => Int -> StdGen -> [a]
getRands 0 _ = []
getRands x gen =     
  v : getRands (x-1) gen'
  where (v, gen') = random gen 

((getRands 10 gen)::[Int])

2012-02-18 さいきん

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

2012-01-20 Winning from losing

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

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

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

翻訳すると、

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

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

なぜでしょう?

*1平均値が負のポイント

*2平均値が正のポイント

2012-01-10 Rで単純ベイズ

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

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

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


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

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


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

2012-01-08 ランダムウオークで距離を測ろう

モチベーション

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

RW(ランダムウオーク)

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

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


RWR(Random Walk with Restart)

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

実験:モナドと近い単語

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

実験結果

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

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