種
自分はストレス耐性が高い方ではなく、無駄に色んなことに気を揉んでしまう性格のせいか疲れを溜め込みやすい性格のようだ。そういうことに気づいたのはつい最近である。最近ではあるが、最近そうなったか?というとそうでもないように思う。振り返れば中学ぐらいの頃から余計なものをたくさん背負う癖があったようにも思うし、そうでなければ(全くそういうのに向いてないのに)生徒会役員とかやらなかっただろうなと思う。
心が折れるというのは面白い表現だと感じる。普段は折れていないのだろうか。まっすぐなのだろうか。それとも真っ直ぐでも折れてもない、いい塩梅に曲がっているのだろうか。そういう形状が通常時ならば、枯れ枝のようにポキっと折れていたら、それはまぁ誰が見たってまともな状態ではないという兆候なのだろう。
自分はどうか。自分のことは良くわからない。しかし、もう、特定のことしかやっていたくないと思うことが増えた。仕事に行かずにこれだけをやっていたい。それは本を読むことだったりコードを書くことだったり、或いは延々と映画を観たいとか旅行に行きたいとか、あるいは何の予定もなくサンフランシスコに行ってスタートアップ訪問したいとか、突拍子もないことだったりもするのだけれど、何かこう色々とうまく回せなくなってきていると感じる。この状況をどう捉えればいいか自分でもよう分からない。
がんばって客観的に自分の状況を鑑みるに、どうにもこうにも消化不良を起こしているような心情が占めているように思う。自分では納得してないけどやらなきゃならん、やるぜー、うぉーっ、と頑張ってきたことが、ある日突然外的要因により、それはもうどうしようもないくらいの力によって、ポシャってしまう。そういうことがなぜか自分の身にはたくさんあった。
そういうことが何度かあって、結果として、自分は何も成果を残せていない。残せていないから、何も自分で自分を褒める要素なんてない。当然誰からも評価はされない。新たに得たものは何もない。一応会社員としてはこれはまずい。種を植えることになって、自分はいつものように土を作っていたが、やーそろそろ種を植えようかね、というところで、畑は使われなくなってしまった。使われないから自分は畑をもとの状態に戻した。
気がつけば、確実に結果を残せることを自分で身つけて拾って片付けるようなことに自然と意識が傾き始めた。必然であったし無意識でもあったのだが、結果が残せるということは精神衛生上とても良いことだった。そうか、何かの本に書いてあったけど、小さな勝利を積み重ねるのは、だから大事なのか、ということに気付かされる。
プログラミングで言えば、細かいバグを直したり、リファクタリングしたり、依存しているライブラリのバージョンを(特に理由もなく)上げてみたり、テストが足りないところでテストを書いてみたりといった、まぁ概ね自分やらなきゃならないタスクではないとは思うような、間違えようのないタスクをやることが心の平穏につながる。どうやったってうまくいくし、自分の成果として形に残る。これは素晴らしいことだ。面白くはないけれど。
そうこうしているうちに、もしかしたら、少しは育つかもしれない種みたいのが何とか見つかってきている。
自分は土は作れる。だが種がなかった。だけど種さえあれば、何とかなるのではないか。そういう気持ちが、最近になって、本当に久しぶりなのだがようやく芽生えてきた。
そういうものをどうにかこうにか育てられればと願う。 願うだけでなく、芽が出るぐらいまでは、まぁ自分で面倒を見てやりたいと、そう思う。畑はいつでも移ることができるが、多分育てられる種は見つけた場所でしか育てられないと思うので。
自分が2016年に作ったrails拡張系gemとその解説
この記事はトレタ Advent Calendar 2016の4日目です。
3日目は弊社CTOのmasuidriveによる【定番】 新しいWebサービスを開発・運営するときに使いたいサービス 【2016年末版】でした。私の推しサービスはBugsnagです。詳細はこちらのスライドを参照ください。
さて、3日目のこの記事では、私が今年railsの実装についての調査と暇つぶしを兼ねて作ったrails拡張系gemについて紹介します。
flatten_routes
routes.rb
を書くときにresouce
やresources
を使った書き方をしているとroutes.rb
だけでは実際のURLがパッと見でわかりにくくなることがある。
$ rake routes
を使えばよいのだが、routes.rb
が膨大になってくると表示まで3~4秒待たされることもあり、プロジェクトが佳境を迎え、1秒でも惜しい状況では結構なストレスになる。
そこで、routes.rb
を書くときのもう一つの記法である verb {directory} => {controller}/{action}
の書き方もコメントで併記できたらよさそうと考えてこのgemを作った。
実行例は以下の通りである。
仮にroutes.rb
が以下の通りだったとすると
Rails.application.routes.draw do ActiveAdmin.routes(self) resources :todos, except: [:new, :edit] do member do post :start post :finish post :restart post :giveup put :awesome end collection do get :finished get :not_yet end end end
Rails.root
で以下のコマンドを実行することで
$ rake flatten_routes:annotate
こうなる
Rails.application.routes.draw do # == generated by flatten_routes from here 2016-02-27 17:56:31 +0900 # get '/admin' => 'admin/dashboard#index' # get '/admin/dashboard' => 'admin/dashboard#index' # post '/admin/todos/batch_action' => 'admin/todos#batch_action' # get '/admin/todos' => 'admin/todos#index' # post '/admin/todos' => 'admin/todos#create' # get '/admin/todos/new' => 'admin/todos#new' # get '/admin/todos/:id/edit' => 'admin/todos#edit' # get '/admin/todos/:id' => 'admin/todos#show' # patch '/admin/todos/:id' => 'admin/todos#update' # put '/admin/todos/:id' => 'admin/todos#update' # delete '/admin/todos/:id' => 'admin/todos#destroy' # get '/admin/comments' => 'admin/comments#index' # post '/admin/comments' => 'admin/comments#create' # get '/admin/comments/:id' => 'admin/comments#show' # delete '/admin/comments/:id' => 'admin/comments#destroy' # post '/todos/:id/start' => 'todos#start' # post '/todos/:id/finish' => 'todos#finish' # post '/todos/:id/restart' => 'todos#restart' # post '/todos/:id/giveup' => 'todos#giveup' # put '/todos/:id/awesome' => 'todos#awesome' # get '/todos/finished' => 'todos#finished' # get '/todos/not_yet' => 'todos#not_yet' # get '/todos' => 'todos#index' # post '/todos' => 'todos#create' # get '/todos/:id' => 'todos#show' # patch '/todos/:id' => 'todos#update' # put '/todos/:id' => 'todos#update' # delete '/todos/:id' => 'todos#destroy' # == generated by flatten_routes to here ActiveAdmin.routes(self) resources :todos, except: [:new, :edit] do member do post :start post :finish post :restart post :giveup put :awesome end collection do get :finished get :not_yet end end end
コメントするだけでなく、いっそのことresoruces
やresource
を使う記法をすべてconvertしたい、という時には
$ rake flatten_routes:convert
を実行することで、上記の例でコメントされていた部分が記述され、オリジナルのresources
やresouce
を使っていた方がコメントアウトされる。
railsからrouting情報を取り出す方法について
$ rake route
がそれっぽい情報を表示してくれているのでその辺のソースを参考に調べた。(このgemを書いた当時はrails5が出る前だったので4-2-stable
ブランチを参照した)
rails4.2におけるrake routes
タスクは以下の様に実装されている
desc 'Print out all defined routes in match order, with names. Target specific controller with CONTROLLER=x.' task routes: :environment do all_routes = Rails.application.routes.routes require 'action_dispatch/routing/inspector' inspector = ActionDispatch::Routing::RoutesInspector.new(all_routes) puts inspector.format(ActionDispatch::Routing::ConsoleFormatter.new, ENV['CONTROLLER']) end
Rails.application.routes.routes
でrouting情報の構造を取得し、それを ActionDispatch::Routing::RoutesInspectorに渡して、 ActionDispatch::Routing::ConsoleFormatter で定義されたformat(定義箇所はここ)で整形されたものをputsしているということがわかる。ちなみに、ActionDispatch::Routing::RoutesInspector
はActionController::RoutingError
がraiseされたときに出るエラーページのルーティング一覧を表示する部分でも使われており、htmlのtableに整形するためのformatterも実装されている。
なので、今回はオリジナルのformatterを作ってそれをinspectorに渡すように実装すればいいかなと思ったが、別にformatterを差し替えて使いまわすような使い方を提供するgemでもないので、ベタっとformatterを書いて実装した。中身はroutes.rb
のフォーマットに合わせて置換したり見た目を揃えるためにスペース入れたりとかそういう当たり前のことしかしていないので割愛。
補足
単に実際のURLをコメントするだけなら他のgemとしてはannotateというgemがある。
自分はプライベートでも仕事でもよく使っており、ActiveRecordのModelにコメントでschema情報を付けるだけのgemかと思っていたのだが、READMEをよく読んだらrouting情報もコメントしてくれる機能があったらしい。じゃあこれ使えばいいか
error_arranger
Controller内部でエラーが起きて、rescue_fromに渡されたりそのままraiseされてrack layerで処理される前に何か前処理を入れたりできないかなぁと思って作ったgem。
例えば
class PostsController < ActionController end
みたいなcontrollerがあったとして、PostsController
内部で発生したエラーメッセージに何か注釈をつけたりしたい、みたいなケースがあったら(あるのか?)以下のようにarrange_exception!
を実装することで実現できる。
class PostsController < ApplicationController private def arrange_exception!(exception) exception.message << 'This error raised in PostsController' end end
エラーがrailsで処理される前にcallbackを差し込む仕組みについて
結論から言えばモンキーパッチを当てているので、あまり行儀が良い方法ではない。
で、モンキーパッチの内容は下記である。
module ActionController module Rescue extend ActiveSupport::Concern include ActiveSupport::Rescuable private def process_action(*args) super rescue Exception => exception request.env['action_dispatch.show_detailed_exceptions'] ||= show_detailed_exceptions? arrange_exception!(exception) if self.respond_to?(:arrange_exception!) rescue_with_handler(exception) || raise(exception) end end end
単にcontrollerにarrange_exception!
という名前のメソッドが生えていたらそれを呼んでからrescue_fromで定義されたhandlerに渡すかそのままraiseする、という感じである。
このgemを作った当時、Controllerのactionで発生したエラーがどこでhandlingされるか分からなくて散々railsのソースを読んでようやく見つけた記憶があるのだが、rails/actionpack/lib/action_controller/metal/rescue.rbに実装されている。
ソースをちゃんと読み切れていないのだが、どうもrails/actionpack/lib/action_controller/metal
配下に実装されているモジュールがロードされて、そのモジュールの中でprocess_action
というメソッドをoverrideしていってstackされていき、実際にリクエストが来てactionが実行されるときにcallbackとしてcontrollerからprocess_actionが呼ばれる。。という感じのように見えるのだが、よくわかっていない。謎い。
practical_errors
先に説明したerror_arranger
を使って、railsでよく見るエラーにもう少し丁寧な解説をつけてみたらrails初心者に優しくなるんじゃなかろうか?と思って作ってみたgem。
例えば、Post.find(1000)
を実行してActiveRecord::RecordNotFound
がraiseされたとする。
そのときには以下のようなメッセージをerrorオブジェクトに追加してくれる。
ActiveRecord::RecordNotFound ( ========== Practical Errors appends message from here ========== Rails says, "Couldn't find Post with 'id'=1000". You might have called ActiveRecord::FinderMethods#find, but the record for provided id was not found. If you DO NOT want to raise ActiveRecord::RecordNotFound even if the record was not found, you should use ActiveRecord::FinderMethods#find_by instead. Post.find(1000) # raise ActiveRecord::RecordNotFound Post.find_by(id: 1000) # just returns nill ========== Practical Errors appends message to here ========== See more detail about Practical Errors: https://github.com/serihiro/practical_errors )
idで検索してnilになるケースが想定される場合はfind_by使ってね、的なrails初心者のコードをレビューする時につけるようなコメントをrailsに勝手にやってもらえる。もちろん、ちゃんとエラーメッセージを読む相手であるということが前提だ。読まない相手の場合は頑張って教育しよう。
ちなみに、ActiveRecord::RecordNotUnique
のときの追加メッセージはこうだ。
The column included in the record that you were about to insert or update, is not allowed duplicated value. This error was detected by database, not Rails. You might have configured uniqueness validation to this column, but uniqueness validation is not panacea. In race condition, uniqueness validation was passed easily. For more detail, see rails document http://api.rubyonrails.org/classes/ActiveRecord/Validations/ClassMethods.html#method-i-validates_uniqueness_of
uniqueness: true
なvalidationを入れてもrace conditionではすり抜けるから気をつけような、的な。あまり役には立たないがActiveRecord::RecordNotUniqueがrescueされずに突き抜けてしまった時の慰めにはなるだろう。
ちなみにいまのところ対応しているエラーはActiveRecord::RecordNotFoud
とActiveRecord::RecordNotUnique
の2種類しかない。他にも色々作る予定だったが力尽きてしまったので、ぜひPRを送って熱いエラーメッセージを追加してもらえるとうれしい。
実装部分については特筆すべき事項はなく、前出のerror_arranger
を使ってraiseされたエラーのクラスを見てそのクラスに該当するAdviserクラスがあったらAdviserクラスにメッセージを付与してもらう、ぐらいの感じである。
if PracticalErrors::ErrorAdvisers::const_defined?(exception.class.to_s) @customised_message << PracticalErrors::ErrorAdvisers::const_get(exception.class.to_s).advise(exception) else @customised_message << <<-"EOS".strip_heredoc hmm... I don't know this error :( Tell me => https://github.com/serihiro/practical_errors EOS end
Adviserがいない時は教えてくれ!っていうメセージを入れているが今の所一件も報告がないので誰も使ってないと思われる。PRお待ちしております。
トレタ Advent Calendar 2016の5日目は2回目の登場horimislimeによる「ここ最近作ってたMacアプリの話とか」の予定です。
高校数学やり直してみた時に使った教材や勉強法やあれこれ
このエントリーは 機械学習に必要な高校数学やり直しアドベントカレンダー Advent Calendar 2016の2日目です。
1日目は現役高校生の方のエントリーでした。自分もこういう話を現役の頃に先生や同級生としたかったですね。現役の頃は数学って大学に行くための手段程度にしか思ってなくて、今考えたら非常にもったいなかったなと思います。。
これは何か
きっかけ
- もともと機械学習に興味があったのだが、いい加減仕事でちゃんと使えるレベルになって
Railsしか能がないおじさん
から脱却しようと思い立ち、2016年5月ぐらいから「データサイエンティスト養成読本 機械学習入門編」を読み始めた
- のだが、途中途中で出てくる数式の意味が理解できなくてモヤモヤした。
機械学習の本読んでると数2Bあたりから数学やり直す必要性をひしひしと感じる…ロジスティック損失の計算式を導く途中計算式を読んでも、単純に対数の計算方法を忘れてる為にでどうしてそうなるのか分からないのでモヤモヤする。
— Kazuhiro Serizawa (@seri_k) 2016年5月14日
- わからない所は飛ばしつつ、まずは大枠を理解しようと頑張って読んでいたのだがやっぱりモヤモヤする
- なので数学をちゃんとやり直すことにした
- 機械学習でよく出てくる線形代数、等比級数、確率、みたいにピンポイントで勉強し直せばいいかなと思ったけど、いい機会なので高校数学をまるっとやり直すことにした。
Railsおじさん脱却してデータ分析もできるようになるぞ!→機械学習勉強するぞ!→本に書いてあることが理解できない→統計勉強するぞ!→本に書いてある数式が理解できない→線形代数と微積だけやり直すぞ!→高校数学レベルがもはや理解できない→数学ⅡBやるぞ!←イマココ
— Kazuhiro Serizawa (@seri_k) 2016年7月22日
やったこと(時系列順)
高校数学をざっとやり直す
- まずは高校数学一通りやり直そうと思ってことでこれを買って一通り練習問題を手で解いた。
- 主に平日に出社前と帰宅後にちょっとずつ解いていき、大体2ヶ月ぐらいで一通り最後までやり終わった。
- 仕事が忙しかった時期と被ってたりもしたので平日1日の勉強時間は平均して1時間にも満たない程度だったと思う。平日全然できなくて休みの日にガッツリやったりしたときもある。
- この本にも書いてあるが、テキストを読むだけでは頭に入ってこない。実際にペンと紙で問題を解くことが重要だと感じた。(当たり前だけど)
その時の勉強ノート。字の汚さは昔と全く変わっていない…*1
12年ぶりに高校数学を勉強してみた気づき
- 高校数学なんて高校卒業以来12年近く使ってなかったのに、手を動かして問題解き始めたらすぐ思い出せたりして人間の記憶ってすごいなーと思った
- 高校時代よりかはゆっくりしたペースで勉強できるので一個ずつ自分のペースで理解できてとても楽しい
- 特に、高校時代はただ丸暗記していただけの公式を、導き方含めてその意味をじっくり考える良い機会になった
高校数学をやり直した成果を形に残したいと思って数学検定を受けてみた
- 勉強中に、調べたら数学検定という検定試験があったので、まずは高校2年生レベルの2級を受けてみることにした。
- 調べたら直近の試験日まで1ヶ月程度しかなかったが勢いで受けてみることにした。
- 教材として上記の本に加えて過去問集を買って解きまくってみた。
- 過去問の正答率はギリギリ受かるか受からないかといったライン。何度も繰り返し勉強した。
結果
そういえば以前、実用数学検定2級というのを受けてみたんだが、自分の手ごたえ通り一次試験のみ合格、二次試験不合格だった。10年以上振りに1か月だけ適当に勉強した割にはまぁまぁの結果といったところだが、二次試験は確実に合格するには青チャートぐらいやっとかないとキツいと感じた。
— Kazuhiro Serizawa (@seri_k) 2016年8月22日
- センター試験レベルの一次試験は受かったが、二次試験は大問を合計5問説いて各1点満点という配点だったのだが、計算ミスって0.2点足りなくて不合格だった。
- ので、来年リベンジしたい*2
- 追記: 2017年11月に合格.なお准1級と1級はいまだに取れていない...
数学検定2級、webで結果確認したら受かってたっぽいので高校2年生レベルの数学力があることが証明された。来年は準一級と一級取って大学卒業レベルの数学力を身に着けたい。
— Kazuhiro Serizawa (@seri_k) 2017年11月19日
- 二次試験の応用問題は青チャートの例題レベルをやっておかないと厳しいかと感じた。過去問で出てないパターンの問題が1パターンずつぐらいは毎回増えていっているように見える。
- ので、これまた15年近くぶりに青チャート買った。昔は数学は基本的に青チャートシリーズだけで勉強してたが、まさかおっさんになってから改めて買い直すとは思ってなかった。
- 作者:チャート研究所
- 発売日: 2012/11/01
- メディア: 単行本
高校数学を改めて勉強してみて思ったこと
- 現役高校生の頃はセンター試験対策の勉強しかしてなくて、公式丸暗記して問題を解く方法しか練習しておらず「数学が楽しい!」なんて全く思わなかったのに、「機械学習でデータ分析ができるようになる」ことを目標を持って勉強してみるとすごく楽しく感じた。
- また、数学検定受ける際に時間がなかったので、必要な公式をすべて丸暗記することはできないと分かっていたので、最低限の公式から必要な公式を導けるように勉強してみた。その結果、12年越しに現役高校生の頃にやってたことの意味が理解できるようになったりして新たな発見が多かった。
- あと特に三角関数、複素数平面、ベクトルの辺りの横のつながりや、行列で計算することの意味を少しは理解できるようになった。
- 昔はこれらの繋がりなんてまるで考えてなかったが、社会人になってプログラミングするようになってから「どういうデータ構造でデータを表現して問題を解決するか」という考え方が身に付いたことも関係しているのかもしれない。
まとめ
- 12年ぶりに再開した数学は思ってた以上に楽しく実用性を感じる世界だった
- 歳取ってから、しかも仕事しながら仕事と全然関係ない勉強するのは辛いかなと思ってたけど意外となんとかなるという自信につながった
- 機械学習に必要な高校数学やり直しアドベントカレンダー Advent Calendar 2016の3日目はmash0510さんです。
PageRankについて調べてみた
この記事はトレタ Advent Calendar 2016の2日目です。
1日目は弊社iOSエンジニアのhorimislimeによるリリース自動化だけじゃないfastlane活用方法でした。恥ずかしながらfastlane初めて知ったんですが便利ですね。あと関係ない話ですがなぜか弊社のiOSエンジニアは普通にruby書けるのでビビります…
概要
- Googleの検索エンジンが長らく使ってきたPageRankがどういうものなのか気になっていたので、Google PageRankの数理―最強検索エンジンのランキング手法を求めて― という本の情報をベースにまとめてみた
- ついでにべき乗法でスコア計算するRubyの参考実装を書いてみた
PageRankについて
- ページをランク付けするための「ページの重要度」を数値化するためにLarry PageとSergey Brinによって考案されたアルゴリズム
PageRankが生まれた時代背景
- Googleの前身であるBackRubが開発された1996年当時、他の商用検索エンジンは転置インデックスを用いた全文検索を主な検索の手段としていたケースが多かった(AltaVistaなど)
- しかし、それらの商用検索エンジンは、人間から見て実用的な検索結果を表示することが非常に困難な状態にあった。単純に検索クエリとページに含まれるキーワードの一致数などを使って表示順序を決定していたため、そのページに価値があるかどうかを評価することができなかった。
- また、特定のタグに同じキーワードを沢山いれるなどするだけで簡単に任意のページの検索ランキングを操作することができ、スパマーの攻撃の的にされるという問題も抱えており、ますます実用性からはかけ離れていた。*1
- その一方で、webサイト上のリンクのつながりから自律的にページの重要度を学習するBuckRubは、検索結果の表示順序を決定する際にPageRankによって算出された「ページの重要度」を用いていたため、他の商用エンジンと比べ「実用的な」検索結果を表示することができた。
- 2016年8月現在においてもGoogle内部でページランクが「ページの重要度」を評価するために用いられていると公表されている。
基本的なアイデア
PageRankの基本的なアイデアは下記がベースとなっている(後述するが実用的なスコアを算出するためには若干の調整が必要になるので単純に実際のリンク数だけで決定している訳ではない)
- 沢山のページからリンクを貼られているサイトほど重要(以後本記事ではこのリンクを
入リンク
と呼称) - 他のページにリンクを貼る時、重要なサイトから貼られたリンクの方が価値がある(以後本記事ではこのリンクを
出リンク
と呼称) 出リンク
の価値は1つのサイトから貼られている出リンク
の数に反比例する
webサイトのPageRankスコアを計算してみる
以下のように6つのページが互いにリンクを貼っている状況を考える(それぞれのノードが1つのWebサイト)
Lawrence Page とSergey Brinは、当初下記の計算式によりPageRankスコアを求めた。*2
ここで
この数式を反復法で繰り返し計算することでPageRankのスコアを求めることができると考え、k+1回目の繰り返しで求められるスコアを
とすると
となる。
ここで、当然ながらk=0の時の値(つまり初期値)を何の値とするかという問題が発生するが、Lawrence Page とSergey Brinは初期値として集合Pに含まれるページ数の逆数を用いたとされる。今回の例で言えば、Pにはページが6個含まれるので、k=0の時は一律で 1/6
となる。
単純なアプローチによるスコア計算
上記の数式を用いて実際にスコアを計算してみる。*4
から計算してみる。
つづいてk=1の時のスコアを使ってk=2のスコアを反復的に求めてみる。texで書くのがめんどくさくなってきたので細かい計算は省略する。
k = 2の時点でスコアを降順ソートすると
となり、6ページ間のランキングが作成できる。*5
総和計算から行列計算に置き換えて考える
ここで、最終的に得られるPageRankのスコアのリストを、n次元ベクトル(nは集合Pに含まれるページ数)と捉えると、上記の計算はn * n行列とn次元ベクトルの積として考えることができる。*6
具体的には、総和式の代わりに以下の行列を導入することで、先に行ったPageRankスコアの計算を単純な行列計算として考えることができる。
Hi
行の要素は、ページ Pi
が持つの出リンクの有無を示す。
例えば H[1]
行においては H[1][2]
と H[1][3]
のみが非0で、それ以外は0になっている。これは、 P1
が P2
と P3
に対する出リンクを保持しており、それ以外のページに対してはでリンクを保持していないことを示している。*7
要素の値がそれぞれ 1/2
となっているのは P1
の持つ出リンクの個数で除している為である。これは、先に示した総和式でPageRankスコアを計算した時、各ページのスコアを |Pj|
で除した処理に対応した前処理である。
Hj
列の要素は、ページ Pj
が持つ入リンクの有無を示す。
例えば H[1]
列においては H[3][1]
のみが非0で、それ以外は0になっている。これは、 P1
が P3
からの入リンクを保持し、それ以外のページからの入リンクを保持していないことを示している。H[3][1]
要素が1/3
なのは、先に説明したとおりP3
の出リンクの総数で除されている為である。
この行列H
を用いると、先に掲載した
は以下のように書き換える事ができる。
ここで、
と定義される行ベクトル を導入すると、
と置き換えられる。
なお、実際に行列計算をする時は
として、Hの転置行列に右から列ベクトル を乗じる必要がある(と思うのだが、なぜか参考にした書籍ではこの辺のことが記載されていなかった。。そんなもんは数学者の間では常識なんだろうか?)
単純なアプローチをそのまま用いて計算する場合の問題点
しかしこの式には以下のような問題があると参考にした書籍では指摘されている。
- いつか は収束するのか?
- 計算を繰り返す回数は何回が最適なのか?10回か?20回か?それ以上か?
また、実際、先に掲載した式で ぐらいまで求めると `(0 0 0 2/3 1/3 1/5) となり、一部のページにスコアが隔たってしまうという問題もある。
これらの問題を解決するためにLarry PageとSergey Brinは以下の調整を行った。以下の調整を行うことで がある定常ベクトルに収束することがべき乗法の考え方から収束することが保証される*8
ハイパーリンク行列を調整する
Larry PageとSergey Brinが行った調整は下記の2つ。
出リンクを1つも持たないページには他のページに出リンクがあることにする
出リンクがないページに到達したらどっか適当なページに飛ぶじゃろ、という前提で他のページに対する出リンクが同確率で「あること」にする。
例えば P(2)
は出リンクを持たないページなので、 H[2]
の行において、全ページに対して出リンクを持つことにする。
つまり一定の確率で他のページにジャンプする、という概念を導入することになる。Larry PageとSergey Brinの論文では ランダムサーファー
と呼称されている。
この調整により先の数式で出てきた行列 H
を用いて新たな確率行列 S
が定義される。
ここで a
は出リンクを1つでも持つP
は0、ないP
を1とする2値ベクトルとする。
全てのページから関係のないページに一定の割合で他のページに出リンクがあることにする
出リンクがあるページを閲覧していたとしても突然関係ないページに飛ぶじゃろ、という前提で、全ページに対する出リンクが同確率で「あること」にする。
その結果、更に調整を行った新たな行列 G
が登場する。
は0と1の間のスカラーである。googleでは長い間 0.85
が使われていたらしい。
実際に先に挙げた例で G
を計算すると以下のようになる。
はGに対する定常ベクトルで、以下のようになる。参考書籍よりそのまま抜粋。参考書籍掲載のMATLABの参考実装で計算したものらしい。
参考書籍に掲載されていた参考実装では π(k)T
と π(k-1)T
のノルムの差が一定数値以下になるまで計算を繰り返した最後の π(k)T
を定常ベクトルとして扱っているらしい。要するに、1回前の計算値と最後の計算値の差が十分小さくなったら収束した、と見なすというアプローチらしい。
は以下の固有ベクトル問題を解くことでべき乗法で繰り返し計算しなくても近似的に求める方法があるらしいが、自分の数学力と時間が足りなくて固有値問題についてよく理解できないので誰か教えてほしい…(要勉強)
自分でもrubyで実装してみた
最後に、自分がrubyで実装したpagerankのスコアをべき乗法で求めるコードを掲載しておく。
なるべく参考書籍の数式がそのまま動く感じになるように実装した。
実際にべき乗法で繰り返し計算するループは下記のような感じ。本文でも記載しているが、G
行列を転置して列ベクトルである pie
を右から乗じて計算している。行列計算においてはrubyのMatrixクラスが非常に便利だった。
収束したかを判定する @residual_erorr
は参考書籍の参考実装から持ってきた 1e-8
を使っている。
_transposed_google_matrix = google_matrix.transpose loop do previous_pie = pie pie = _transposed_google_matrix * pie if pie.norm - previous_pie.norm < @residual_erorr break end end
まとめ
- ページランクの概要はざっくり知っていたが、いざ書籍を一冊読んでちゃんと調べると数学的な奥深さが半端なく、その辺のバックグラウンドがない自分には難解でほとんど理解できてないように感じる。実際、参考書籍は前半においてはオリジナルの論文の解説といった感じだが、後半は収束速度とパラメータの数値の調整に関する議論やPageRank以外でのランキングについて記されているのだが、その辺の内容が高度すぎてまだ理解できていない。
- これをきっかけ確率過程やマルコフ連鎖について勉強していきたいと感じた。実際、確率過程についてはネットで拾った大学講義の資料とかで調べてみたらかなり面白く、自然言語処理や機械学習の分野でもこれが理解できないといつか詰みそうな内容だったので、いつか単独でブログネタにしたい。*9
- トレタ Advent Calendar 20163日目はmasuidriveによる「Railsで新規サービスを作る時に使うべきサービス」です。
参考資料
- Google PageRankの数理―最強検索エンジンのランキング手法を求めて―
- PageRank アルゴリズム およびそれに関連する研究について
- The Anatomy of a Large-Scale Hypertextual Web Search Engine
- グーグル ネット覇者の真実 追われる立場から追う立場へ
- 東京農工大の「情報理論」の講義資料
*1:CCCメディアハウス「グーグル ネット覇者の真実 追われる立場から追う立場へ」より
*2:この数式は書籍 「Google PageRankの数理」に記載されていた通りのものだが、書籍中では出典が明らかになっておらず、また、オリジナルの論文である 「The Anatomy of a Large-Scale Hypertextual Web Search Engine」 にはこの数式は書かれていない。Lawrence Page と Sergey Brin によるもう一つの論文 「PageRank, an Eigenvector based Ranking Approach for Hypertext」 の方に記載があったのかも知れないが、この論文はweb上で本文が見つからなかったため確認できなかった。無念。
*3:Lawrence Page とSergey Brinらが入リンクのことをBacklinkと論文の中で記述していたのでBを使っているのだろう
*4:このあたりから段々tex記法で数式書くのが辛くなってきた…ので段々サボり出しているがはてなブログにおけるmarkdownとtex記法の組み合わせが最悪なのでご了承いただきたい
*5:ページ1とページ3のスコアが同値なので、2つのページが同じ検索結果に含まれる場合にどう並べるかという問題に対しては、別の評価パラメータを用いて総合的に優劣を決定しているものと考えられる。
*6:実際は行列と行ベクトルの積は直接計算できないので(懐かしの数Cでやったことを思い出そう)それぞれの転置行列同士の積を取ることになるのだが、アカデミックの世界ではその辺をよしなにやってくれる計算ライブラリを使うのが常識なのかどうかは分からないが「PageRankの数理」においてはその辺の説明を端折っている
*7:ここでtex使わないで書いているのは、同じ行にtex記法で書くとはてなブログが展開してくれないからである。。
*8:なぜ保証されるかは参考書籍を読んでも良く分からんかったが、調整したH行列の固有値を用いることで収束することが証明できるらしい…要勉強
*9:公開されている大学の講義資料にいつも助けられている。機械学習や自然言語処理の方で調べ物するときも信頼のおける情報ソースとしていつも使わせていただいている。工学系の学位取ってない自分にとってはホントありがたい。
エンジニアの立ち居振舞い:過度に仕組みを作らない
特に仕事でコードを書く場合で意識してることだけど、過度に仕組みを作らないというのを大事にしている。
ここで、過度な仕組み
とは例えば最初から以下のような実装をすることを指すことにする
- 1つのクラスでしか使われないコンテキストの上に成り立つ実装をグローバルなクラスに切り出してそのクラスを他のクラスからも使えるように実装する
- テンプレートメソッドパターンを適用して部分的に実装を差し替えられる用に実装する
- 例えばjavaとかで実装クラスは現時点で一つしかないのに最初からインターフェースを用意する
要するに、万人が使うようなフレームワークやライブラリを実装するかのように拡張性の高い
コードを実装してしまうことを指す。
過度な仕組みを作れば作るほど、仕組みの動作を保証するのに必要なUTの量は増加し、実装量も増えてレビューは大変になり、またその部分を修正する人はロジックそのものに加えて仕組みそのものの仕様理解にも時間を取らされたりと、色んな人の工数を大量に消費する。
それでもまだ本当にそんな仕組みが必要だろうか?自分たちが今必要としているのは動く実装でありフレームワークではない。
自分が過度な仕組み
を持つ実装をする場合は、今から作ろうとしている実装において、明らかにコピペできるレベルの実装がいくつもあるなーと感じた時だけにしている。これもしかしたら他でも使うかもなーと思うこともあるのだが、それでも一箇所でしか使われないコードならグッと我慢してベタッと実装する。
もちろん機能的な分解点やUTの書きやすさを意識してメソッド自体はあれこれ分割したりスコープを考えたりクラスを分けたりといったことはするが、しょっぱなからサブクラスを作ってそのクラスをオーバーライドするところから実装を始めたりはしない。
なぜか?今作ろうとしている目の前の機能こそが一番大事だからだ。
今作ろうとしている機能を過不足なく、他のメンバーが理解しやすい形の落とし所に納めて、リリースすることこそが一番大事だからだ。だから無駄なことはしない。早く作って早くリリースする。
そして時が経って、必要になったらその時初めて抽象化でもなんでもする。
大事なことは常に「今」必要最低限のものだけで始めて、「必要なとき」に素早く拡張できることだと思う。
今読んでる本とか
完全に自分用のメモ。
平行してその時の気分で読む本を選んで読む癖があるのでたまに何読んでたか忘れて最初から読み直すハメになったりする。
今読んでる
Google PageRankの数理 ―最強検索エンジンのランキング手法を求めて―
- 作者: Amy N.Langville,Carl D.Meyer,岩野和生,黒川利明,黒川洋
- 出版社/メーカー: 共立出版
- 発売日: 2009/10/10
- メディア: 単行本
- 購入: 4人 クリック: 249回
- この商品を含むブログ (29件) を見る
Googleを支える技術 ?巨大システムの内側の世界 (WEB+DB PRESSプラスシリーズ)
- 作者: 西田圭介
- 出版社/メーカー: 技術評論社
- 発売日: 2008/03/28
- メディア: 単行本(ソフトカバー)
- 購入: 47人 クリック: 1,166回
- この商品を含むブログ (374件) を見る
- 作者: ジョン・L.ヘネシー,デイビッド・A.パターソン,成田光彰
- 出版社/メーカー: 日経BP社
- 発売日: 2014/12/06
- メディア: 単行本
- この商品を含むブログ (2件) を見る
- 作者: マイケルマローン,Michael S. Malone,土方奈美
- 出版社/メーカー: 文藝春秋
- 発売日: 2015/09/12
- メディア: 単行本
- この商品を含むブログ (1件) を見る
積んでる
- 作者: 渡辺佑基
- 出版社/メーカー: 河出書房新社
- 発売日: 2014/04/14
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (5件) を見る
ゼロから作るDeep Learning ―Pythonで学ぶディープラーニングの理論と実装
- 作者: 斎藤康毅
- 出版社/メーカー: オライリージャパン
- 発売日: 2016/09/24
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (18件) を見る
ハイパフォーマンス ブラウザネットワーキング ―ネットワークアプリケーションのためのパフォーマンス最適化
- 作者: Ilya Grigorik,和田祐一郎,株式会社プログラミングシステム社
- 出版社/メーカー: オライリージャパン
- 発売日: 2014/05/16
- メディア: 大型本
- この商品を含むブログ (4件) を見る
HTTP: The Definitive Guide (Definitive Guides)
- 作者: David Gourley,Brian Totty,Marjorie Sayer,Anshu Aggarwal,Sailu Reddy
- 出版社/メーカー: O'Reilly Media
- 発売日: 2002/09
- メディア: ペーパーバック
- 購入: 1人 クリック: 34回
- この商品を含むブログ (1件) を見る
- 作者: 平井有三
- 出版社/メーカー: 森北出版
- 発売日: 2012/07/31
- メディア: 単行本(ソフトカバー)
- 購入: 1人 クリック: 7回
- この商品を含むブログ (5件) を見る
今年読んだ本で面白かったやつ(ソート順は適当)
- 作者: スティーブン・レヴィ
- 出版社/メーカー: CCCメディアハウス
- 発売日: 2012/08/31
- メディア: Kindle版
- 購入: 1人 クリック: 16回
- この商品を含むブログを見る
- adwordsのアイデアは最初からあったと思ったんだけど、当初はマネタイズ手段としては検索エンジンのライセンスビジネスを考えていたというのと、adwordsと似たようなアイデアが他社検索エンジンにすでにあったのは初めて知った。
- googleのproductの強みはオリジナリティよりも泥臭い努力に裏打ちされた愚直な性能の高さにあるんやなってはっきりわかるんだね。
- googleの中国撤退の話は多分ほかのメディアよりずっと詳しかったのではと思った。
サーチ・インサイド・ユアセルフ――仕事と人生を飛躍させるグーグルのマインドフルネス実践法
- 作者: チャディー・メン・タン,ダニエル・ゴールマン(序文),一般社団法人マインドフルリーダーシップインスティテュート,柴田裕之
- 出版社/メーカー: 英治出版
- 発売日: 2016/05/17
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (6件) を見る
- googleの宣伝的な文章が結構多くて最初の方はもどかしく感じたが、その後に続くマインドフルネスの具体的な内容については割と詳細に書かれている。
- 個人的な感想としては瞑想に対する敷居がかなり下がった感じ。今でも忘れない限りは寝る前に瞑想をしている。
- 運動と瞑想の習慣がない者の末路は(ry
データ解析のための統計モデリング入門――一般化線形モデル・階層ベイズモデル・MCMC (確率と情報の科学)
- 作者: 久保拓弥
- 出版社/メーカー: 岩波書店
- 発売日: 2012/05/19
- メディア: 単行本
- 購入: 16人 クリック: 163回
- この商品を含むブログ (29件) を見る
- 作者: ジョン・ソンメズ
- 出版社/メーカー: 日経BP社
- 発売日: 2016/06/02
- メディア: Kindle版
- この商品を含むブログ (7件) を見る
- 作者: 五木田和也,青木健太郎
- 出版社/メーカー: 技術評論社
- 発売日: 2016/09/27
- メディア: 単行本
- この商品を含むブログ (3件) を見る
- 作者: 川上量生
- 出版社/メーカー: KADOKAWA / 中経出版
- 発売日: 2013/10/10
- メディア: Kindle版
- この商品を含むブログ (21件) を見る
- 作者: 齋藤ウィリアム浩幸(さいとう・ウィリアム・ひろゆき),William Hiroyuki Saito
- 出版社/メーカー: 日経BP社
- 発売日: 2012/10/04
- メディア: 単行本
- 購入: 2人 クリック: 6回
- この商品を含むブログ (6件) を見る
- 作者: 山田胡瓜
- 出版社/メーカー: 秋田書店
- 発売日: 2016/04/08
- メディア: Kindle版
- この商品を含むブログ (6件) を見る
- 作者: 得能正太郎
- 出版社/メーカー: 芳文社
- 発売日: 2015/03/27
- メディア: Kindle版
- この商品を含むブログ (13件) を見る
- 作者: 森井ユカ
- 出版社/メーカー: 主婦と生活社
- 発売日: 2015/08/28
- メディア: 単行本
- この商品を含むブログ (1件) を見る
チームが機能するとはどういうことか――「学習力」と「実行力」を高める実践アプローチ
- 作者: エイミー・C・エドモンドソン,Amy C. Edmondson,野津智子
- 出版社/メーカー: 英治出版
- 発売日: 2014/05/24
- メディア: 単行本
- この商品を含むブログ (3件) を見る
- 作者: 石塚千尋
- 出版社/メーカー: 講談社
- 発売日: 2013/12/09
- メディア: コミック
- この商品を含むブログ (20件) を見る
- 作者: サカーイ
- 出版社/メーカー: サカーイ
- 発売日: 2013/02/09
- メディア: Kindle版
- この商品を含むブログを見る
- 作者: 森博嗣
- 出版社/メーカー: 幻冬舎
- 発売日: 2015/12/18
- メディア: Kindle版
- この商品を含むブログ (10件) を見る
- 作者: 板垣政樹
- 出版社/メーカー: 秀和システム
- 発売日: 2016/03/09
- メディア: 単行本
- この商品を含むブログ (1件) を見る
Java 謎+落とし穴 徹底解明 (標準プログラマーズライブラリ)
- 作者: 前橋和弥
- 出版社/メーカー: 技術評論社
- 発売日: 2001/12/01
- メディア: 大型本
- 購入: 8人 クリック: 40回
- この商品を含むブログ (21件) を見る
- 作者: アラン・W.ビアマン,Alan W. Biermann,和田英一
- 出版社/メーカー: ASCII
- 発売日: 1993/06
- メディア: 単行本
- 購入: 6人 クリック: 184回
- この商品を含むブログ (30件) を見る
cでwebサーバを書き始めた
趣味でcでwebサーバを書き始めた。 8月末ぐらいからちょっとずつ作業を進めていたのだが、とりあえずhtmlファイルをレスポンスするところまでは実装できたのでgithubに公開した。
名前の由来は旧日本海軍が第二次大戦時に開発したオートジャイロの名前を拝借した。何となく、サーバー系プログラムには空を飛んでる何かの名前を付ける習慣があると思っているのでその習慣に倣ってみた。
書き始めた理由は今年開催のいくつかのカンファレンスでOku Kazuhoさんのhttp2のセッションを聞いてhttp2の実装に興味が湧いたからなのだが、それ以前にhttpもよく分かってない。ということでhttpの勉強も兼ねてまずはhttp1.1サーバを書いてみようと思った。また、せっかく新しいものを書くなら使ったことがない言語にしよう、ということでcで書くことにした。あとパタヘネ読んでたら低レイヤーを触れる言語を1つはちゃんと書けないと理解できないことが沢山あるという危機感を感じたという理由もある。
今はまだhtmlファイルしか返せない(.htmlか.htm以外の拡張子を指定すると415を返す)し、 ../../tmp/hoge.html
みたいなパスにアクセスされると一発でアウトみたいなセキュリティホールだらけなのだが 、一般的な静的ファイルを置いて使う程度には困らない程度のものに仕上げたいと思っている。実装予定のfeatureはREADME.mdに記載した。
あとcのノウハウが全然ないので手探りで書いてる感が半端ない実装状態である。char配列のバッファサイズとかかなり適当だし、どういう時にmalloc使うべきでどういう時に配列使えばいいかもよく分かってない。どう最適化すればよいのかも併せて勉強していく必要がある。あとMakefileも適当に書いているしgccのオプションも言われるがままにホイホイコピペしてきたものである。とりあえずgdbでデバッグするために-g o0
は付けているが、これもホントはmake debug
みたいなdebug用taskに分離して置いた方がいいのだろうか。周りにcでプロダクト書いてる人がいないのでこの辺の知見が得られなくて中々に辛い。
余談だが、趣味プロダクトが一つでもあると心が落ち着くというか、仕事で辛いことがあったり退屈していても、家に帰ってからあのバグを直そうとかあれを実装しようというポジティブな予定が持てて、精神衛生上良いのでオススメである。
自分にはもう一つの趣味プロダクトslidesearch.jpというwebサービスもあるので、こちらについてもたまにrailsとかgemのバージョンを上げたり細かいバグを直したりという作業を日課としている。大したUIはないのだが、自分の勉強のためだけにフロントをangular2で書き直してSPAにするかとか色々考えている。