THINKING MEGANE

『強化学習アルゴリズム入門』第1章〜第2章の学習メモ

書籍『強化学習アルゴリズム入門』について第1章〜第2章を読んでの学習メモをまとめる。

強化学習は一連の行動によって得られる報酬を最大化する行動基準を学習する。 そのために、「一連の行動」を状態の遷移と捉えて、その状態に対する価値(状態価値)を求める。 また、各状態には取りうる複数の行動があると考え、その状態の価値を、これらの行動ごとの価値(行動状態価値)から求める。

強化学習アルゴリズムごとの価値関数

はじめに、第1章〜第2章までで学ぶ各強化学習アルゴリズムの状態価値関数と行動状態価値関数をまとめておく。

状態価値関数 $V(S_t)$行動状態価値関数 $Q(S_t,a_t)$
動的計画法$V(S_t)=\sum_{a} \pi (a \mid S_t) Q(S_t, a_t) \tag{1}\label{1}$$Q(S_t,a_t)=r_{t+1}+\gamma V(S_{t+1}) \tag{2}\label{2}$
モンテカルロ法$V(S_t)=\sum_a Q(S_t,a_t) \frac{N_a}{N} \tag{3}\label{3}$ $V(S_t)=max\{Q(S_t,a_t)\} \tag{4}\label{4}$$Q(S_t,a_t)=\frac{1}{m}\sum_{i=1}^{m} G^i(S_t,a_t) \tag{5}\label{5}$ $Q(S_t,a_t) \gets Q(S_t,a_t)+\alpha[G(S_t,a_t)-Q(S_t,a_t)] \tag{6}\label{6}$ where $G(S_t,a_t)=r_{t+1}+\gamma G(S_{t+1},a_{t+1}) \tag{7}\label{7}$
TD(0)法同上$Q(S_t,a_t) \gets Q(S_t,a_t)+\alpha[\{r_{t+1}+\gamma(Q(S_{t+1},a_{t+1}))\}-Q(S_t,a_t)] \tag{8}\label{8}$

以下、各強化学習アルゴリズムについて捕捉する。

動的計画法

確率型ベルマン方程式\eqref{1}に従い行動状態価値を更新する手法。 ここで$\pi (a \mid S_t)$は行動確率であり、方策$\pi$に従い状態$S$において行動$a$を選択する確率を示す。 また、$Q(S_t, a_t)$は行動状態価値関数であり\eqref{2}によって求める。

行動状態価値関数\eqref{2}は状態$S$において行動$a$によって遷移する状態$S$で得られる報酬$r$とその状態の価値$V$の和によって求められる。 ここで$\gamma$は価値の割引率である。

書籍ではこの価値の求め方を「将来に対する平均($X_{t+1}$ から$X_N$ までの平均$\bar{X}$)の逐次的な計算」との類似性によって説明している。 \[ \bar{X_t}=\bar{X}_{t+1}+\frac{1}{N-t}(X_{t+1}-\bar{X}_{t+1})
=(\frac{1}{N-t})X_{t+1}+(\frac{N-t-1}{N-t})\bar{X}_{t+1} \]

動的計画法における学習プロセスは以下のようになる。

方策反復法

1. 状態価値が収束するまで以下のステップを繰り返す
2. 各状態において方策(行動ごとの行動状態価値Qによるepsilon-greedyなど)に従い行動確率を求める
3. 各状態において行動ごとの行動状態価値を遷移後の状態の報酬と状態価値から求める
4. 2と3よりその状態の状態価値を更新する
5. 全ての状態で状態価値の更新が終わったら次の学習イテレーションへ

価値反復法

$\epsilon$-Greedyの探索率$\epsilon=0$の場合は方策に依存しない価値反復法となる。

1. 状態価値が収束するまで以下のステップを繰り返す
2. 各状態において行動ごとの行動状態価値を遷移後の状態の報酬と状態価値から求める
3. 2のうち最大の値で状態の状態価値を更新する
4. 全ての状態で状態価値の更新が終わったら次の学習イテレーションへ

モンテカルロ法

動的計画法は環境情報が既知の場合に使えるが未知の場合、環境も含めて手探りで行動基準を学習しなければならない。 そのような場合はモンテカルロ法を利用する。

モンテカルロ法の価値の学習には総報酬$G$\eqref{7}を用いる。 総報酬は一連の行動が終わり得た報酬$r$から遡って状態(と行動)に対して価値を算出する。 書籍ではこの価値の求め方も「将来に対する平均」で表現している(tの値をt+1から求める)。

なお、行動状態価値は\eqref{5}により試行数$m$での平均とする(学習ステップにおいて\eqref{3}\eqref{4}\eqref{6}は使わない)。

モンテカルロ法における学習プロセスは以下のようになる。

1. 任意の試行回数だけ以下のステップを繰り返す
2. 最初の状態から報酬rを得るまで以下のステップを繰り返す
3. 現在の状態において方策(行動ごとの行動状態価値Qによるepsilon-greedyなど)に従い行動aを決定する
4. 次の状態へ遷移
5. 報酬を得たら行動を遡り各状態(と行動)の総報酬Gを求め、試行回数での平均によって行動状態価値Qを更新する

TD(0)法

モンテカルロ法は総報酬$G$を求めるために必ず一連の行動を終える必要がある。 そこで、逐次的に行動状態価値を求めることでモンテカルロの探索行為を効率的に行おうとするTD(0)法がある。

TD(0)法では、行動状態価値$Q$を\eqref{8}によって求める。 これは、モンテカルロ法の行動状態価値関数\eqref{5}を逐次計算表現にした\eqref{6}の$G(S_t,a_t)$を動的計画法の行動状態価値関数\eqref{2}で置き換えたものと考えることができる。 つまり、総報酬$G$を$t+1$の報酬と状態価値で近似するものである。

TD(0)法における学習プロセスは以下のようになる。

SARSA (方策反復法)

1. 任意の試行回数だけ以下のステップを繰り返す
2. 最初の状態から報酬rを得るまで以下のステップを繰り返す
3. (S) 現在の状態において方策(行動ごとの行動状態価値Qによるepsilon-greedyなど)に従い行動aを決定、Q(S_t,a_t)を得る
4. (A) 行動aに従い状態を遷移
5. (R) 遷移後の状態で報酬rを得る(得られない時もある)
6. (S) 遷移後の状態において方策に従い行動aを決定、Q(S_t+1,a_t+1)を得る
7. (A) 行動aに従い状態を遷移
8. 5の報酬rと3と6の行動状態価値QでQ(S_t,a_t)を更新

Q学習 (価値反復法)

$Q(S_{t+1},a_{t+1})$を$max\{Q(S_{t+1},a_{t+1})\}$で求めることで方策に非依存とする。

1. 任意の試行回数だけ以下のステップを繰り返す
2. 最初の状態から報酬rを得るまで以下のステップを繰り返す
3. 現在の状態においてランダムに行動aを決定、Q(S_t,a_t)を得る
4. 行動aに従い状態を遷移
5. 遷移後の状態で報酬rを得る(得られない時もある)
6. 遷移後の状態においてランダムに行動aを決定、Q(S_t+1,a_t+1)は全行動状態価値のうち最大の値とする
7. 行動aに従い状態を遷移
8. 5の報酬rと3と6の行動状態価値QでQ(S_t,a_t)を更新

学習書籍

テッド・チャン『息吹』と「なめらかなシステム」

昨年末にあんちぽさんからお勧めされていた、テッド・チャン『息吹』をようやっと読み終えた。

本書を通して所属する研究所のビジョンである「なめらかなシステム」の世界観について理解が深まったように感じたのでメモしておく。

本書は表題の「息吹」を含むSFの短編集である。全部で9編の作品から成る。 多くの作品は、現在の地球の水準より進んだ技術とそれを扱う知性体が登場する。 登場人物は世界を左右するような運命や世界をまたにかける使命など帯びていないどこにでもいるような人々であることが多い。 (『イブの時間』などが雰囲気としては近いかもしれない) 彼ら彼女らはただ、彼らにとっては当然となった新しい技術に起因する変化に彼ら彼女らなりに適応していく。 この技術と変化の設定がリアリティを持っているがゆえに、読者はそう遠くない未来に地球の技術水準が到達した後に発生するであろう変化に対して自分ならばどうするかと没入感を持って作品にのめり込む。

さて研究所のビジョンとしての「なめらかなシステム」であるが、情報システムとこれを取り巻く要素が互いに影響を及ぼし合う総体としてのシステム観である。 これに対し、以前に「なめらかなシステムの見据えるもの。個人的考察」のエントリで、なめらかであることの必然性を問いの発端としてその未来像を検討した。 その際は、「個性」というキーワードで、システムと接する要素が多様かつ継続的に変化することを前提としてこれにシステム側が適応することがこの必然性につながると考えた。 いわば、システムを利用する要素(特に人間)が主でシステムが従のような捉え方であった。 ここで、「なめらかなシステム」自体は、要素間に主従の考えは導入していないにも関わらず、個人の感性としてバイアス的にこのような考えが導入されてしまったと思う。 そのためか、互いに影響を及ぼし合うと言いつつも、システムの利用側としては、そのシステムとそのタスクに限定された影響(例えば、情報要求の前進、あるいは具体化など)程度に収まると考えていた。

一方で、今回の読書を通して、一段階規模を広げたシステム観に思い至れた。 もし、個別のシステムを超えて、全体としての技術水準やパラダイムのような圧倒的な変化があれば、主従が変化し、そのような技術に追従するために人生観や哲学でさえも(好むと好まざるに関わらず)そこに適応しなければならない。 「なめらかなシステム」においては、ある意味、これまでであれば受け手側が制御不能なレベルでの変化をも適応していきたい。

今回、単一のシステムから技術、パラダイムの変化にまで拡大してシステム観を適用して考える契機になったと思う。 僕にとって発想を広げるのはSFを読む醍醐味であり、今回の作品は大いにこれが達成されて満足している。 興味を持った方は是非読んで欲しい。 短編集なので1時間程度の空きがあれば少しづつ読み進めることができると思う。 代表作の「息吹」だけでも読んで欲しいし、「ソフトウェア・オブジェクトのライフサイクル」「偽りのない事実、偽りのない気持ち」「オムファロス」「不安は自由のめまい」もお勧めしたい。

2019

今年は研究とGo言語三昧だった。 特にGo言語については、福岡でGoConを開催し、GopherCon2019で初の海外カンファレンスに登壇した。 大規模カンファレンスの主催も海外の大きなカンファレンスでの登壇も初めての経験で準備もプレッシャーも大変だったが、多くの人と笑いながら協力しながらなんとか達成することができたと思う。 これらの経験は自分の行動の幅を世界基準に広げるにあたって大きな自信につながった。 加えて、コミュニティ活動として主催するFukuoka.goを他の地方コミュニティと同時開催したり、Go言語教室を招いたり、OSS Gateのメンター、Fukuoka.LTの運営をやったりと精力的に福岡のコミュニティを全国とつなげ、盛り上げることができた。 来年もGo言語を武器にどんどん活動していきたい。

研究については、当初目標だったジャーナルには残念ながら不採録となったものの、改めて研究を発展させ年内に再度投稿することができた。 今年執筆した論文とそのフィードバックから、研究の背景(動機、位置付け、従来課題の整理)は一定のレベルで書けるようになったのではないかと感じる。 一方で、提案手法とその評価に関する指摘の割合が多くなってきており、改めて提案手法の貢献を明確にできるよう考え抜いていかなければならない。 これまでの研究を通して「常に変化しうる多数の環境に対する自律適応的なシステムとその仕組み」が背景にあるのではないかと考えており、来年はこの観点でのサーベイと体系化を進めていきたい。

2019年をかけて、多くのことを達成することができた。 特に精神的な面では強くなれたのでないかと思う。 上期の前半は、研究で実績が出ないことに対する焦りや力不足でまたも袋小路に入ってしまったが、アドバイスや助力いただけたことで立て直すことができた。 それでも、何かをやることに対する漠然とした恐怖や、過度な専念などいくつかの弱体化がかかっていたように思う。 結局は、無能だと判断されたくないだとか、集中することができれば大きな成果を出せるはずだとか、心の奥底に対外的な評価が中心に据えられて、自己評価とのギャップと相まって動けなくなっていたことが原因だと思い至り、過去の理性の人のエントリを見返しつつ、自分を大切に、なすべきことをやっていけるよう少しづつ冷静になれた。 周りからの評価を恐れてやるべきことを見失ったり曲げてしまうのはとても悲しいことだし、 生きている以上、やることは常に発生するのだから、これらを後回しにすることは長期的には専念にはならないし、 色々なことに向き合う必要があるのだから、人や結果に過度にひきづられることを言い訳にせずに個々の事象をある程度独立させて淡々とこなして行くのが良いのだろう。

来年は、数学、英語、サーベイを継続的にこなしつつジャーナルを通して博士課程に挑戦する。 また、トップダウンの視点をもって行動の意義を共有することで影響力を高めていこうと思う。 2020年もよろしくお願いします。

実績

以下、実績を列挙する。

論文

国内査読無し論文が2本と国内査読付きポスター発表が1本。執筆としては査読付き論文が2本。うち1本が不採録で、投稿中が1本。

  1. 三宅 悠介, 栗林 健太郎, Kaburaya AutoScaler: 多環境での運用性を考慮した自律適応型オートスケーリング制御系, インターネットと運用技術シンポジウム論文集, 2019, pp.114-115, Nov 2019. [論文] [発表資料]
  2. 三宅 悠介, 阿部 博, 栗林 健太郎, なめらかなセキュリティを目指して, 研究報告インターネットと運用技術(IOT), Vol.2019-IOT-47, pp.1-7, Sep 2019. [論文] [発表資料]
  3. 三宅 悠介, 松本 亮介, 利用者の文脈に応じて継続的に推薦手法の選択を最適化する推薦システム, 研究報告インターネットと運用技術(IOT), Vol.2019-IOT-45, pp.1-7, May 2019. [論文] [発表資料]

国外発表

初の海外カンファレンス登壇。めでたい!

国内発表

技術イベント、研究会での発表で計6回。

  1. 三宅 悠介, コマンドラインオプションをパースするコードをコマンドラインオプションから生成するツールをつくった, Fukuoka.go#14+Umeda.go, 2019年10月.
  2. 三宅 悠介, Kaburaya AutoScaler: 多環境での運用性を考慮した自律適応型オートスケーリング制御系, 第五回 Webシステムアーキテクチャ研究会, 2019年9月.
  3. 三宅 悠介, 「エンジニアコミュニティの運営について」パネルディスカッション, Engineer Friendly Space, 2019年7月.
  4. 三宅 悠介, AI(機械学習)ワーキンググループ 成果報告, ペパコンナイト, 2019年5月. [動画]
  5. 三宅 悠介, Ebira: アクセス負荷に応じて継続的にスケーリング基準を最適化する汎用オートスケーリング機構, 第四回 Webシステムアーキテクチャ研究会, 2019年4月.
  6. 三宅 悠介, Go language serverを理解する, Go 1.12 Release Party in Fukuoka, 2019年2月. [動画]
  7. 三宅 悠介, dragon-importsで爆速goimports生活 - プロジェクト Go modules, Fukuoka.go#13+Okayama.go, 2019年2月.

OSS

Kaburayaを中心に自律適応的な仕組みに向けての知見を深めていった。また、研究系のシミュレーションが増えてきた。

コミュニティ活動

Goを中心に精力的に活動できた。特に全国規模のカンファレンスを福岡で主催したり、地方のGoコミュニティ同士を繋いだり福岡以外へも活動の幅が広がっている。 また、OSS GateやFukuoka.LTへの参加を通して福岡全体の盛り上げにも協力できたかなと思う。

出版物等への寄稿

前作に引き続きガッツリと査読に関わらせていただいた。

  • 書籍査読: スマートニュース株式会社 立石 賢吾, やさしく学ぶ ディープラーニングがわかる数学のきほん ~アヤノ&ミオと学ぶ ディープラーニングの理論と数学、実装~, マイナビ出版, 2019年07月31日. ISBN:978-4-8399-6837-3

ブログ

13本。一時期は日記を書いていたが、考えをまとめる練習にはつながらなかったかもしれない。 実績に加えてどうしてそのような活動に至ったのかについてもトップダウンの視点で書いていきたい。

論文執筆の道しるべ

論文執筆にあたり自分向けの指針のようなものがまとまってきたのでメモしておく。 以下の内容の一枚もののサマリがあると良いのではないか。

  1. 背景: なぜその課題に取り組むか
  2. リサーチクエスチョン: 何を解決したいのか
  3. 従来手法の整理: これまではその課題をどう解決していたのか、これまでのやり方に残った課題は何か
  4. 提案手法: 残った課題をどう解決したか
  5. 評価: 残った課題は定量的にどの程度解決したか

ここで

  • 2.のリサーチクエスチョンと3.従来手法の課題を混同しない。
  • 3.従来手法の課題、4.提案手法、5.評価はもれなく対応する。つまり、課題が3つであれば提案手法もそれらに対する解決アプローチを提示し、それぞれに評価が行われている。もしくは課題のうち、いくつを解決するものかを明示する。
  • これらは一枚まとめにすると良い。シーケンシャルな文章とこのまとめを交互に見直すことで道筋を外れずに具体と抽象を行き来できる(といいな)

上手な査読者のレビューは提案内容を除けば上記の観点での過不足を指摘しているように思える。 指摘事項に対する個別対処では、論文執筆力の向上はのぞめないのでこのような枠組みも意識して一定の水準での論文を執筆できるようにもなっていきたい。

また、議論から多くを得るためには

  • 分野のやや異なる人とは1.背景の説明を長めに取ることで自分の思い込みや暗黙の前提が浮き彫りにされ読み易い論文になる
  • 分野の同じ人とは同じ課題意識を持つとみなし、従来手法の整理と提案手法のアプローチを中心に議論する
  • 差読者目線を持つ人とは、リサーチクエスチョンを一言で伝わるか、それが解決したかをできるだけ手短に説明する

のような感じに使い分けると良いのではないかなと考えている。

コマンドラインオプションをパースするコードをコマンドラインオプションから生成するツールをつくった

コマンドラインオプションの形式は決まったけれども、パース処理を実装するために各言語やライブラリのドキュメントを読むことを繰り返していたので、この手間を省くためのツールをつくりました。

flagenは、先に決めたコマンドラインオプションから、これを解析するための各言語用のコードを出力するツールです。 オプション名から変数名や変数の型、デフォルト値が決定されるため、汎用的なボイラーテンプレートと比較して編集の手間が少なくなります。 また、テンプレートによって任意の出力を行えるため、エディタや自前のボイラーテンプレート出力ツールとの連携が容易です。 使いやすくするため、プリセットのテンプレートとしてGo、Ruby、Python、Shellのものを提供しています。

使い方

使い方は、テンプレートと実際に使う時のコマンドラインオプションを渡すだけです。

$ flagen YOUR_TEMPLATE YOUR_COMMAND_LINE_OPTIONS...

例えば、

$ flagen go --dist erlang -e k/l --lambda 1.5 -k 1 -v

と指定すると、Go用のコマンドラインオプションの解析処理を出力します。

var (
	dist	string
	e	string
	lambda	float64
	k	int
	v	bool
)

func init() {
	flag.StringVar(&dist, "dist", "erlang", "usage of dist")
	flag.StringVar(&e, "e", "k/l", "usage of e")
	flag.Float64Var(&lambda, "lambda", 1.5, "usage of lambda")
	flag.IntVar(&k, "k", 1, "usage of k")
	flag.BoolVar(&v, "v", false, "usage of v")
}

指定されたコマンドラインオプションから変数名、オプション名、型、デフォルト値が設定されることで編集の手間が極力ない状態になっています。

Python、Ruby、Shellの例はGodocのExamplesを参考にしてください。

テンプレート

テンプレートはGoのtext/templateを利用して解析されます。 テンプレート内では、.Flags(解析したオプションの情報)と.Args(残りのコマンドライン引数)が利用可能です。 .FlagsNameValueをもち、Valueは更にTypeGetをもちます。

以下は、解析したオプションの情報を列挙するシンプルなテンプレート(my.tmpl)です。

{{ range $flag := .Flags -}}
  {{ $flag.Name }}={{ $flag.Value.Get}}({{ $flag.Value.Type }})
{{ end }}
$ flagen my.tmpl --dist erlang -e k/l --lambda 1.5 -k 1 -v

このテンプレートから以下の出力を得ることができます

dist=erlang(string)
e=k/l(string)
lambda=1.5(float)
k=1(int)
v=false(bool)

また、テンプレート内では文字列のケース変換のための関数を利用することができます。 主に変数を言語の命名規約に合わせるのに使えます。 使える関数は、こちら で確認ください。

連携

Vim

flagenの結果は標準出力を使っているため、エディタとの連携も容易です。 例えば、Vimでは以下により、カーソル位置に結果を挿入することができます。

:r!flagen YOUR_TEMPLATE YOUR_COMMAND_LINE_OPTIONS...

ボイラーテンプレート出力ツール

flagenはライブラリとして利用することができるため、自前のボイラーテンプレート出力ツールがGo製であれば以下のように呼び出すことができます。

	tmpl, err := flagen.NewTemplate(args[0])
	if err != nil {
		return err
	}
	return tmpl.Execute(outStream, args[1:])

また、独自の関数が必要な場合は flagen.TemplateFuncMapに設定することでテンプレート内で利用することができます。

ワークアラウンド

曖昧なフラグ

flagenはオプションに値が指定されていないときにboolだと見なすため、以下のようにboolフラグで終わって引数がある場合に判断がつきません。

$ flagen TEMPLATE --bool-flag arg1

想定どおりにするためには値としてtrue or falseを受け取ることを明示する必要があります。

$ flagen TEMPLATE --bool-flag=false arg1

まとめ

様々な実装が提供されているコマンドラインオプションの解析処理を利用形式から動的に生成するジェネレーターとしてflagenをつくりました。実際にいくつかの言語のテンプレートを用意してエディタと連携させることでCLI開発の効率が改善しています。

今後はflagen自体のオプションとしてprefixなどを提供すれば構造体の変数に設定する用途などのテンプレートとの相性もよくなりそうだと考えています。 便利なテンプレート追加のプルリクエストやイシュー、ボイラーテンプレートのツールへ組み込んだ報告などお待ちしています。

Fukuoka.go

このツールはFukuoka.go#14+Umeda.goで発表しました。 発表資料はこちらです。

待ち行列理論に使われる分布に従う乱数をGo言語で生成する

待ち行列理論をシミュレーションする際にいくつかの分布に従う乱数を生成する必要があったのでメモ. また,確率まわりの用語と分布についても理解が曖昧な点があったのでこの機会にまとめておく.

用語の整理

確率

確率は,

\[ \frac{ある事象の起こる場合の数}{全ての事象の起こる場合の数} \]

で求められる.

確率変数

確率変数は,事象に対応した実数のこと. 確率変数には,離散型と連続型の二種類がある. サイコロの出目のようなものは離散型で,身長や体重のような(原理的には)連続の値になるものは連続型.

確率分布

確率分布は確率と確率変数との対応付け. そもそも辞書的な意味での「分布」は「粗密の程度を含めた,空間的な広がり具合」を表す. 度数分布では階級と度数(階級に含まれる変量の数)の対応付けであった. また,これらの分布は,度数分布と同様に確率分布表や確率分布グラフとして表すことができる.

確率を返す関数

ここで,ある確率変数を入力に,対応する確率を出力する関数を考える.

確率質量関数

離散型の確率変数であれば,確率分布表を照会し,対応する確率を得ることができる. 確率変数を入力に,対応する確率を出力する関数を確率質量関数(または確率関数)[1]と言い,サイコロの出目を確率変数$X$とした時に1が出る確率を$P(X=1)=\frac{1}{6}$のように書ける. もちろん確率の総和は1である.

確率密度関数

連続型の確率変数の場合は,ある一点の値を入力とすると対応する確率は常に0となる. これは,ある範囲においても実数は無限個あるため,全事象が無限になることから,確率の定義より$\frac{1}{\infty}=0$となるためである. このように連続型の確率変数からは直接的に確率を求めることができないので,この連続型の確率変数を対応する「何か」に変換する必要がある. また,その「何か」は確率に変換できる必要がある. 確率の定義から,総和は1である. また,連続型の確率変数であることから,和は積分で求めることになる.

連続型の確率変数をx軸に,この連続型の確率変数を対応する「何か」をy軸にプロットした時に,ある範囲の割合は該当範囲の定積分によって導くことができる. そして,全体の積分が1で,その中のある範囲の定積分が,事象がその範囲に含まれる確率に従うような「何か」があれば,それを連続型の確率変数の確率に用いることができる. そのような「何か」が存在するとき,「何か」は「確率密度」と呼ばれ,連続型の確率変数を入力とし,確率密度を出力する関数を「確率密度関数」と呼ばれる[2].

このとき,確率密度関数$f(x)$に従う確率変数$X$が$(a \leqq X \leqq b)$となる確率は\[\int_a^b f(x) dx\]のように書ける.

確率密度は,その確率変数の相対的な発生のしやすさを表すに過ぎないので,部分的にy軸(確率密度関数の返す値)が1を超えても構わない(全体の面積として1になれば良い.例えば,確率密度関数が$f(x)=2x (0 \leqq X \leqq 1)$のときなど).

待ち行列理論で使う分布

待ち行列理論では待ち行列のモデルの構造を以下のようなケンドール記号を用いて記述する.

  • X/Y/S(N)

ここでXは到着過程の種類,Yはサービス過程の種類,Sは窓口数,Nは待ち行列の長さの制限数が入る. 過程の種類は以下の通り.

種類説明備考
Mマルコフ過程到着過程ならポアソン分布,サービス過程なら指数分布
D確定分布到着間隔やサービス時間が一定
G一般の分布平均値と分散が既知の任意の分布
$E_k$アーラン分布k個の指数分布の和の分布

ポアソン分布

単位時間に平均$\lambda$回起きる事象が単位時間に$k$回発生する分布[3].

平均が$\lambda$のポアソン分布を表す確率質量関数は\[P(X=k)=\frac{\lambda^{k}}{k!}\cdot e^{-\lambda}\]であり平均$E[X]$は$\lambda$となる.

指数分布

平均$\theta$時間に一回発生する事象の発生間隔を表す分布[4].

平均が$\theta$の指数分布を表す確率密度関数は\[f(x)=\frac{1}{\theta}e^{-\frac{x}{\theta}} (x \geqq 0)\]であり平均$E[X]$は$\theta$となる.

待ち行列とマルコフ過程

あるランダムに起きる事象を発生回数から見たのがポアソン分布,発生間隔(または時間)から見たのが指数関数とみなすことができる. マルコフ過程は未来の挙動は過去の挙動とは無関係であるとする性質を持つ確率過程であり,これらの分布が適合するため利用されている.

単位時間に$\lambda$回到着するとした到着過程はポアソン分布が利用されるが,シミュレーションにおいては平均到着間隔を知りたい. この場合は,$\frac{1}{\lambda}$を到着間隔とした指数分布で求めることができる(1時間に平均5人くる場合,平均1/5時間(12分)の間隔で到着する). つまり,$\theta=\frac{1}{\lambda}$として,確率密度関数は\[f(x)=\lambda e^{-\lambda x} (x \geqq 0)\]であり平均$E[X]$は$\frac{1}{\lambda}$となる.

なお,ポアソン分布と指数分布の関係の理解には[5]が参考になる.このサイトでは時刻$t$を導入したポアソン分布の累積分布関数から指数分布の確率密度関数を導いている.

アーラン分布

まず,ガンマ分布は平均$\theta$時間に一回発生する事象(指数分布)が$k$回発生するまでの時間の分布[6]である. ガンマ分布の$k=1$のとき,指数分布と等しく,$k$が整数の場合にアーラン分布と呼ばれる.

ガンマ分布を表す確率密度関数は\[\frac{1}{\Gamma(k)\theta^{k}}x^{k-1}e^{-x/\theta}\]であり平均$E[x]$は$k\theta$となる.

また,前述のポアソン分布のパラメタから指数分布の確率密度関数を求めたのと同様に,$\theta=\frac{1}{\lambda}$として,確率密度関数は\[\frac{\lambda^k}{\Gamma(k)}x^{k-1}e^{-\lambda x}\]であり平均$E[x]$は$\frac{k}{\lambda}$とも書ける.

ここまで,$k$回の$\theta=1/\lambda$の指数分布を場合を見てきたが,待ち行列理論の書籍においては,$k$回の$\frac{\theta}{k}=\frac{1}{k\lambda}$の指数分布としている場合がある. すなわち,一つのサービス時間$\theta$が$k$個の工程(1工程あたり$\frac{\theta}{k}$)からなるとみなしている. この場合,確率密度関数は\[\frac{(k\lambda)^k}{\Gamma(k)}x^{k-1}e^{-k\lambda x}\]であり平均$E[X]$は$\theta=1/\lambda$となる.

待ち行列理論で使う分布に従う乱数

ここでは,ある分布に従う乱数をGoでの生成する.

指数分布

指数分布に従う乱数はGoの標準パッケージmath/randで提供されている.

func Exponential(rnd *rand.Rand, lambda float64) float64 {
        return rnd.ExpFloat64() / lambda
}

パラメタ$\theta=1/\lambda$に合わせるためには結果を$\lambda$で割る(平均到着率が増えるほど平均到着間隔は狭くなる).

動作確認のため,生成した乱数のヒストグラムと指数分布の確率密度関数を重ねてプロットした.

hist_and_pdf_exponential

ポアソン分布

ポアソン分布に従う乱数はGoの標準パッケージで提供されていない. そこで指数分布とポアソン分布の関係性を利用して,指数分布で得られた乱数の和が1を超えるまでの最小のカウント数を用いる方法がある[7][8]. 例えば平均到着率($\lambda$)が5人であれば,平均到着間隔($1/\lambda=0.2$)である. ここでカウントは$0.2*5$が平均して得られると考えられる.

func Poisson(rnd *rand.Rand, lambda float64) float64 {
        p := 0.0
        for i := 0; ; i++ {
                p += Exponential(rnd, lambda)
                if p >= 1.0 {
                        return float64(i)
                }
        }
        return 0.0
}

生成した乱数のヒストグラムとポアソン分布の確率質量関数のプロット.

hist_and_pmf_poisson

アーラン分布

アーラン分布もしくはガンマ分布に従う乱数はGoの標準パッケージで提供されていない. しかし,ガンマ分布の定義(k個の指数分布の和の分布)[6]から以下の実装が可能である.

func ErlangKL(rnd *rand.Rand, lambda float64, k int) float64 {
        g := 0.0
        for i := 0; i < k; i++ {
                g += Exponential(rnd, lambda)
        }
        return g
}

ここで,KLは平均が$\frac{k}{\lambda}$であることを表している.

生成した乱数のヒストグラムとアーラン分布の確率密度関数のプロット.

hist_and_pdf_erlangkl

待ち行列理論の参考書にあるようなサービス工程を$k$個に分割するアーラン分布では$k$回の$\frac{\theta}{k}=\frac{1}{k\lambda}$の指数分布となることから以下の実装となる.

func Erlang1L(rnd *rand.Rand, lambda float64, k int) float64 {
        g := 0.0
        for i := 0; i < k; i++ {
                g += Exponential(rnd, float64(k)*lambda)
        }
        return g
}

ここで1Lは平均が$\frac{1}{\lambda}$であることを表している.

生成した乱数のヒストグラムとアーラン分布の確率密度関数のプロット.

hist_and_pdf_erlang1l

動作確認用のコード

動作確認用のコードは以下にある.

このような感じで利用できる.

go run main.go -size 100000 -dist erlang -e k/l -lambda 0.5 -k 2 > data.txt && python plot.py --dist erlang -e k/l --lambda 0.5 -k 2

参考

Kaburaya AutoScaler: 多環境での運用性を考慮した自律適応型オートスケーリング制御系

このエントリは、第五回 Web System Architecture 研究会 (WSA研)の予稿です。

はじめに

Webサービスの運用において,急激なアクセス頻度の上昇に対する安定性を保つため,Webアプリケーションにスケーラビリティの仕組みが一般的に求められるようになった. これを支援するためにWebアプリケーションを稼働させるクラウドサービスやオーケストレーションツールから,オートスケーリング機能が提供されている. これらのオートスケーリング機能では,開発運用者が予め定めた条件を元にWebアプリケーションの状況が監視される. そうして,条件を満たせば,開発運用者が予め定めたスケール方法とその実施量に従いWebアプリケーションをスケールさせる.

このようにオートスケーリングによって,ユーザからのリクエスト数の増減に応じて最適なサーバ台数を調整されることで利用者の快適さと情報システムの運用コストを両立できるようになった. 一方で,オートスケーリングを導入し,継続的に安定した運用するためには開発運用者の運用努力が必要であるが,これらは管理する環境の増加に従い困難になる. そのため,多環境での運用性を考慮した自動化可能なオートスケーリング戦略が求められる.

オートスケーリングの継続的に安定した運用に向けた課題は大きく二つある. 一つ目は,アプリケーション特性の把握,二つ目は,“遅れ”の考慮である.

課題1: アプリケーション特性の把握

スケールにはWebアプリケーションを稼働する仮想サーバへリソースを追加する垂直スケール(スケールアップ),稼働する仮想サーバを追加する水平スケール(スケールアウト)の2種類の方法がある. しかしながら,どちらの方法を用いるにせよ,開発運用者はWebアプリケーションの特性に応じたオートスケーリングの条件やその実施量を予め定める必要がある. 例えば,時刻ベースであればアクセス頻度の時系列的傾向や,リソース変動ベースであればボトルネックとなるメトリクスである. また,これらの条件に対する必要台数の算出も必要となる. Webアプリケーションは常に変更が加わることから,手動での継続的な特性の把握と決定は運用負荷の面で現実的ではない.

そこで,特性把握の自動化が行われている. 三宅らは,過去のアクセス頻度のデータからLSTMを用いて24時間先までの1時間単位のアクセス頻度を予測するモデルを構築し,予測アクセス頻度を元に経験から得られたサーバ単位のスループットにより必要なサーバ台数を求めた[1]. スループットの把握では,パラメタを連続的に変化させながら最良の結果を得る値を探索的に求める方法も提案されている[2]. これらの予測的,探索的なアプローチによる特性把握の自動化により,変化する環境に対する追従性は向上する. 一方で,事前的なアプローチであるため,予測の誤差,探索を行った環境と本番環境の誤差に対処できないという課題が残る.

そのため,三宅らはフィードバック制御による個別の特性把握を必要としないアプローチ[3][4]を提案した. この手法では,直近のレスポンスタイムが均衡する点に収束するような台数調整によって特性把握が不要で実行時に誤差を修正することができる. ただし,フィードバック制御を用いるため,制御量であるサーバ台数の決定は探索的である. 待ち行列理論によれば窓口利用率が1を超えると待ち行列は収束しないとされていることから,サーバ台数は即時かつ決定的に求められることが望ましい.

課題2: “遅れ”の考慮

オートスケーリングでは,本番環境の誤差に対応するための即応的なアプローチを採用すると”遅れ”の課題が発生する. 一つ目の遅れは,負荷上昇からサーバ台数を見積もるまでの時間差である. 本稿ではこれを「入力の遅れ」と呼ぶ. 次はサーバ台数の変更指示から起動までの時間差である. 本稿ではこれを「出力の遅れ」と呼ぶ. 待ち行列理論によれば窓口利用率が1を超えると待ち行列は収束しないとされていることから,これらの遅れに対して発生した待ちリクエストが系の安定性を崩す. 安定性の低下は開発運用者による不定期な対応を要請し,運用負荷につながることからこれを回避する必要がある.

そのために,遅れを最小化する手法が適用される. 入力の遅れでは,変化点検出などにより負荷上昇を即時に察知する方式がある. また,出力の遅れではCRIUを利用することで起動までの時間を短縮する方式[5]がある. しかしながら,精度の観点やシステム制約によって遅れを0にはできないため,遅れそのものに対する対策は必要となる.

遅れを踏まえた準備では,前述の予測的なアプローチが考えられる. 三宅らの手法[1]では,予測と事前起動によりこれらの遅れを考慮するが,本番環境の誤差への課題が残る. そこで,スミスの予測法[6]のようにフィードバック制御において遅れによる影響を踏まえた制御量を算出する手法がある. 一方で,予測のためには精度の高い予測モデルの構築が必要であり,追従にはここの自動化が必須となる.

提案手法

多環境での運用性を考慮したアプリケーション特性の把握の自動化と安定性の両立のためには,以下の要件が必要となる.

  1. Webアプリケーション特性として負荷に対する実施量の関係が把握できる
  2. これを不必要な負荷をかけることなく実行時に自動で把握できる
  3. 把握したWebアプリケーション特性と実環境に誤差が生じた場合に修正できる
  4. これを実現するリアクティブなアプローチで発生する”遅れ”へ対処できる

そこで,フィードフォワード制御を中心とし,実環境の特性把握・追従のためにフィードバック制御を組み込んだ2自由度のオートスケーリング制御系を提案する. 提案手法により,特性把握・追従の自動化ならびに待ち行列理論を用いた決定的な台数算出・遅れ補償による安定化が見込める. なお,本提案手法の実装はKaburaya AutoScalerとして,OSSでの公開・開発を続けている.

提案手法では,Webアプリケーション特性を求めるにあたって低負荷時では理想的なレスポンスタイム,高負荷時ではスループット限界を用いることで対象のWebアプリケーションに不必要な負荷をかけることなく現状に即したWebアプリケーション特性を把握することができる. また,仮想サーバ起動までの遅れに伴う負荷状況を予測し,これを見越した実施量を見積もる遅れ補償機構を設けた.

提案手法のアーキテクチャを以下に示す.

Kaburaya AutoScaler Architecture

ここで$F$はフィードフォワード制御部である. 現状の負荷状況に応じて実施量であるサーバ台数を算出する. 算出には待ち行列理論の窓口利用率を求める式を変形した$\lambda/\rho\mu$を用いる. なお,$\lambda$は平均到着率(req/単位時間),$\mu$は平均サービス率(req/単位時間),$\rho$は窓口利用率を表す. 提案手法では$\rho$には0より大きく1未満の任意の値を設定することができる.

$P$はプラントであり,$F$で求めたサーバ台数を用いて実際にWebサービスを運用する実環境である. 提案手法では実環境の計測誤差をフィードバックすることで自動かつ継続的な安定性を保つ. $P$は計測結果として単位時間での平均レスポンスタイムである$T_s$と単位時間での1台あたりの処理数である$\mu$を返却する. これらの値は,$F$における新しい$\mu$に用いられる.

提案手法では仮想サーバ起動までの遅れに伴う負荷状況を予測し,これを見越した実施量を見積もる遅れ補償機構を設けた. 待ち行列理論では無限時間の平均した待ち時間を求めるため,窓口利用率が1以上の場合に発散し,理論を適用することができない. 一方で,遅れ時間は有限であることから,窓口利用率が1以上の場合であっても待ち行列の長さを求めることができると考えた. そこで$(\lambda^{t-1}-s^{t-1}\mu^{t-1})\gamma$のように不足処理能力による待ち行列の長さとて加えて,これを捌くことができるサーバ台数を求めている.

評価

プラントのシミュレータを使って提案手法によるオートスケーリングの自律・適応の性能を評価した.

Evaluation

右下のグラフにより$\mu$の推定・追従が行えていること,左上のグラフにより遅れ補償が働きアクセス増加時に一時的に多いサーバを投入することで収束できていることが確認できる. 個別の評価についてはスライドを参照されたい.

発表スライド

まとめ

本研究会ではオートスケーリングと開発運用者間の関係をなめらかにするための多環境での運用を考慮した自律適応型オートスケーリング制御系を提案した. 評価ではM/M/Sモデルを前提としたプラントシミュレータによってこれらが達成可能なことを示した. 実用化に向けて今後はプラントに実際のWebサーバ/アプリケーションサーバを適用した評価や実際の到着,サービス時間間隔に近い分布での評価が必要である. また,提案手法では入力の遅れに伴い単位時間内に待ちリクエストが必ず発生するため変化点検出などで遅れ時間自体を短縮する方式も検討したい.

発表を終えて

今回のWSA研究会もとても面白かった. Webシステムアーキテクチャという題材で色々な分野の人が集まって議論することで持ち寄ったアイディアが前進して行くのを何度も見ている. 自分自身の取り組みも研究としてWSA#3からWSA#4を通してGopherConで登壇できるぐらいに育った. 加えて,今回は,オートスケーリングの課題に着目して新しいアプローチを試してみる中で,制御工学や待ち行列理論などを学び楽しめた. このような普段の研究から少し離れた取り組みであっても,定期的に発表を促されることで形にすることができるのはとても大切で,やりっぱなし学びっぱなしではなく一つの区切りまで考え実装することで次回以降の研究への糧となる. Webシステムアーキテクチャに関する運用知見を研究的アプローチで前進させること興味がある方は次回開催の参加を検討してみてはいかがでしょうか.

リファレンス

  • [1]: 三宅 悠介, 松本 亮介, 力武 健次, 栗林 健太郎, アクセス頻度予測に基づく仮想サーバの計画的オートスケーリング, FIT 2018 第17回情報科学技術フォーラム, CL-002, Sep 2018.
  • [2]: 全自動パラメータチューニングさん https://blog.mirakui.com/entry/2013/02/20/003401
  • [3]: Yusuke Miyake, Optimization for Number of goroutines Using Feedback Control, GopherCon Marriott Marquis San Diego Marina, California, July 2019.
  • [4]: 三宅 悠介, Ebira: アクセス負荷に応じて継続的にスケーリング基準を最適化する汎用オートスケーリング機構, 第四回 Webシステムアーキテクチャ研究会, 2019年4月.
  • [5]: 松本 亮介, 近藤 宇智朗, CRIUを利用したHTTPリクエスト単位でコンテナを再配置できる低コストで高速なスケジューリング手法, 研究報告インターネットと運用技術(IOT), Vol.2019-IOT-44, pp.1-8, Feb 2019.
  • [6]: O. Smith, “Closer control of loops with dead time”, Chemical engineering progress, Vol. 53, No. 5, pp. 217-219, 1957.
Archives