THINKING MEGANE

ペパ研から研究をはじめてジャーナルでのアクセプトまでいけた日

先週の6/22、初めてジャーナルの採録通知をいただいた。

大学は情報系ではなく、大学院にも行っていないので、研究なるものを始めたのが、ペパボ研究所に入った2017年1月から。3年半もかかってしまった。

元々、サービスの運用開発をしていた経緯もあり、2017年の前半はその延長で研究報告を2本書き切った。 初めての研究報告は、論文の型みたいなのを徹底的に教えてもらえた。 今も執筆時に気をつけるところのほとんどはここで教えてもらったことが根底にあると思う。 2017年の後半から、研究の内容自体も「すごいもの」にしようとした結果、迷走が始まる。 自分のやってきたことを深堀するわけでもなく、先達の研究を調べるわけでもなく、自分の能力を高めるわけでもなく、ただ、目新しいことに挑んでは当然のように跳ね返され、焦りから近道を探し、悪循環に陥る。 研究所内で、(今にして思えばほぼ八つ当たりな)相談したり、WSA研でいろいろな人の研究に対する考え方を聞きながら、自分の中の蓄積や道標をきちんと整備していかなければと考えるようになった。

2018年は、アドバイス制度を利用して初めてジャーナル投稿に挑戦した。 当時としては全力で取り組んだ論文はあらゆる直接的間接的な表現で「よくわからないです」とアドバイスをいただき、心砕け撃沈した。 まだまだ付け焼き刃な研究は、専門性に対する脆い知識や理論構成であり、指摘に対して一気に瓦解する。 やれることは、専門性を高めることだけなのだが、分野のあまりの広さ・難しさに途方に暮れていた。 この時期は、指摘をまだアドバイスと見なすことができず辛い時期であった。

2019年の前半は、転換の兆しが見えたが苦しい時期でもあった。 わからないなりに勉強を続け、サーベイを進めた。 自分なりの方向性を見つけ、評価し、効果がある研究ができた。 それでも相変わらず研究報告を上手く書けない。 文章として形が見えていく中で、新しい前提や課題が明らかになり、議論は活発になる。 当たり前のことであり、むしろ喜ばしいことであるのだが、どこかで形を決めなければならない。 この時期は、これは、もっといけるはずだという期待に応えたい気持ちとそれを時間内に解決できない自分の無力感で悪循環に陥ることが多かったのではないかと思う。 そして、この時期の振り返りで、自分と向き合った結果、「結局は、無能だと判断されたくないだとか、集中することができれば大きな成果を出せるはずだとか、心の奥底に対外的な評価が中心に据えられて、自己評価とのギャップと相まって動けなくなっていたことが原因だと思い至」った。

2019年の後半、これを踏まえ冷静になりつつ、いろいろな人に助力をいただきながら、前に進んだ。 学術系ではないがGo言語の国際カンファレンスのトークセッションに採択された。 ポスターセッションではあるものの学術系では初めて査読ありセッションで採択された。 ジャーナルへももう一度挑戦した。結果はリジェクトであったが、査読者の判定は、条件付き採録と不採録で別れ、メタ査読者からは前半(研究の前提や既存研究に対する位置づけ)は非常に読みやすいとのコメントをいただけた。 後半の提案手法やその評価について、アーキテクチャ含め更新、年内にまた別のジャーナルに提出へこぎつけた。

2020年、3月にその論文が条件付き採録となり、これに応えて晴れて採録通知を受けたのが先週。 「ペパ研から研究をはじめてジャーナルでのアクセプトまでいけた日」は研究所の所長が言ってくれた。 本当にそうだなあとこれまでのことを思い返して、泣けた。 今にして思えば遠回りばかりして、勝手に袋小路に迷い込んで非効率極まりない反面教師の塊だと思うけれどもこの過程と振り返りがなければ、今の研究もできていないだろうし小さな人間のままだったかもしれない。 これからまた難航することがあるかもしれないが、今はこの経験が今度は乗り切れるのではないかと思わせてくれる。 なんにせよ、自分のような人間が、ジャーナルを通せるところまでたどり着くことができたのは、ひとえに見捨てずに見守りアドバイスをくれ、相談に乗ってくれる周りの方々のおかげです。 遠回りばかりしていますが、これから、改めて巨人の肩に乗ることから逃げずに真摯に向き合い一歩づつ精進していこうと思います。


今年は他にも、研究チームとしての側面も取り組んで、研究報告ではあるが、はじめて2本ラストオーサーを務めた。 研究所での論文読みや勉強会などの新しい習慣も定着し、今後が楽しみ。 また、自身の研究も前進させ、ジャーナルのアドバイスもうまく取り込めていると思う。 国際会議なども狙っていきたい。 そして、博士課程に挑戦することにした。 まだ結果はわからないが、これまで模索してきた取り組みを加速できると良いなと思う。

過去の振り返り

Go言語でシミュレーション用のシンプルなフレームワークStageをつくった

時系列に対するコンピュータシミュレーションを開発する機会が増えてきたので、共通する処理の流れをフレームワーク化した。

コンピュータシミュレーション

状況に応じたクリック数の最大化や変化点検出のような、システムの適応的な振る舞いを検証するために、時系列に対するコンピュータシミュレーションを行うことがある。 また、実環境で発生するランダムな誤差を表現する場合、乱数を用いたシミュレーション技法であるモンテカルロ法も利用することになる。

このようなシミュレーションのプログラムでは、変化する時系列を入力に、振る舞いのシミュレーション結果を出力するだけではなく、乱数によって発生する誤差を均すためにシミュレーションを数百〜数千回繰り返す必要がある。

Stage

Stageは、これらの一連の流れの実行とこれに伴う煩雑な処理(シミュレーションの並列化、乱数の管理、進捗の監視、ログ出力)を開発者から隠蔽する。 開発者は、時系列や振る舞い、ログフォーマットをGo言語で記述するだけで良い。

Stageで行っているメイン処理の「疑似コード」は以下の通りシンプルである。

for i := 0; i < iter; i++ {
    sem <- struct{}{}

    go func() {
        scenario := NewScenarioFn(rnd.Int63())
        actor := NewActorFn(rnd.Int63())

        for scenario.Scan() {
            action, _ := actor.Act(scenario.Line())
            w.Write(action.String())
        }
        <-sem
    }()
}

このフレームワークでは、メタファーとして劇場(Stage)を採用した。 劇場は、劇を開催する。 その劇は台本(Scenario)があり、演者(Actor)は台本の1行づつのセリフ(Line)に沿って演技を行い、結果(Action)を出力する、といった形だ。 そして劇は何度も繰り返される。

開発者は、時系列や振る舞いをそれぞれ、ScenarioとActorのinterfaceを実装によって記述する。 また、ログフォーマットもAction interfaceで指定するだけで良い。

type Scenario interface {
	Scan() bool
	Line() Line
}

type Actor interface {
	Act(Line) (Action, error)
}

type Action interface {
	String() string
}

あとは実装したScenarioとActorを生成する関数を指定して必要な回数実行。

dir := "log"                    // Directory for output
concurrency := runtime.NumCPU() // Number of concurrency for scenario
seed := 1                       // Seed for random
iter := 3                       // Number of iteration

s := stage.New(dir, concurrency, seed)
s.Run(iter, NewActorFn, NewScenarioFn, stage.NoOpeCallbackFn)

結果は、指定したログディレクトに出力され、実行日時や利用した乱数シードも確認することができる。

log
└── 20200530184234-1 # Timestamp-Seed
    ├── iter_00-a_7947919477105006377-s_5355116748216652230.log # Iteration log files
    ├── iter_01-a_4846631296614585111-s_2007235010091403794.log #   with seed for actor(a)
    └── iter_02-a_0610076349056253918-s_3540139325796113853.log #   and  seed for scenario(s)

なお、出力後の解析、グラフ出力については、Stageでは取り扱わない。 任意のフォーマットで出力できるのでお好みの言語やツールで操作して欲しい。

各インターフェースの具体的な実装方法についてはREADMEを参照のこと。

複数のシナリオを持つシミュレーション例

例えば、以下の青線のような変化の仕方が異なるシナリオを切り替えて、橙の線のような振る舞いの違いをシミュレーションすることができる。

Abrupt changesGradual changes
example_adwin_abruptexample_adwin_gradual

長時間かかるシミュレーション例

また、シミュレーションに時間がかかる場合は、各シナリオの完了時に呼ばれるCallback関数を指定することで、進捗の監視もできる。 お好みのProgress barライブラリを使えば進捗バーも表示できる。

$ go run _examples/progress/main.go
180 / 200 [---------------------------->___] 90.00% 40 p/s

まとめ

普段よりアルゴリズムの理解を深めるため手に馴染んだGo言語で実装を試みるので、必然的にシミュレーションもGoで書くことが多くなったことからGo言語での実装となった。 完全に自分用途でつくったフレームワークではあるが、各シミュレーションにおいてシナリオとアクターという要素のみを意識すればよくなり実装の効率が格段に上がりコードの見通しもよくなった。 また、Go言語を使うことで並列化が容易に実装できシンプルなフレームワークでありながら十分に安定して高速化を達成できていると思う。 付加的な利点として、ログ構成などが統一されたことで後段の解析やグラフ化のスクリプトも共通化が進んでおり、個人的に満足度が高いものができたと思う。

多腕バンディット問題におけるUCB方策を理解する

多腕バンディット問題における解法の一つであるUCB1方策では以下のスコアを各腕に対して求め、最大のものを選択する。

\[ \overline{x}_j+\sqrt{\frac{2\ln{n}}{n_j}} \tag{1}\label{eq-1} \]

ここで、$\overline{x}_j$は腕$j$に対して観測された平均報酬、$n_j$は腕$j$が選択された回数、$n$は全体の試行回数である。 第2項は選択された回数$n_j$が少ないほど大きくなることから、評価が不確かな腕ほど積極的に探索を行う(Optimism in face of uncertainty)。

本エントリでは、この第2項について上記の振る舞い以上の理解を進める。

確率不等式

\eqref{eq-1}式は確率不等式の一種であるヘフディングの不等式に基づいたものであるため、まず確率不等式を学ぶ。 確率不等式は、確率の分布に依らない確率の近似的な評価に利用される不等式である。 簡単には、稀に発生する事象についての確率の上限を求めることができる。

マルコフの不等式 Markov’s inequality

非負の確率変数$X\geq0$と任意の正数$a > 0$に対して

\[ Pr \left[ X \geq a \right] \leq \frac{E[X]}{a} \tag{2}\label{eq-2} \]

が成り立つ。\eqref{eq-2}をマルコフの不等式と呼ぶ。

この不等式を用いることで、確率変数$X$の実現値が$a$以上になる確率の上限を、確率分布に依らず期待値$E[X]$から求めることができる(ただし$a \leq E[X]$だと実用的な値にならない)。

マルコフの不等式を用いて例えば「期待値が10の確率変数で100以上が出る確率は10%以下」($Pr \left[ X \geq 100 \right] \leq \frac{10}{100} = 0.1$)などと求めることができる。

証明は

\begin{align} E[X] &= \int_0^\infty x f(x) dx \notag \\ &= \int_0^a x f(x) dx + \int_a^\infty x f(x) dx \notag \\ &\geq \int_a^\infty x f(x) dx \notag \\ &\geq \int_a^\infty a f(x) dx = a \int_a^\infty f(x) dx = a Pr [X \geq a] \notag \
\end{align}

となる。なお、2行目から3行目は、右辺第1項が$\geq 0$であるため。3行目から4行目は積分区間で最も小さい$a$を使うため。

チェビシェフの不等式 Chebyshev’s inequality

確率変数$X$が期待値$E[X]=\mu$、分散$\sigma^2$を持つとき、任意の正数$a > 0$に対して

\[ Pr \left[ \mid X - \mu \mid \geq a \sigma \right] \leq \frac{1}{a^2} \tag{3}\label{eq-3} \]

が成り立つ。\eqref{eq-3}をチェビシェフの不等式と呼ぶ。

この不等式を用いることで、確率変数$X$の実現値と期待値$\mu$の差が標準偏差$\sigma$の$a$倍以上になる確率の上限を、確率分布に依らず期待値$\mu$と分散$\sigma^2$から求めることができる。

証明は、マルコフの不等式に対して$X = (X-\mu)^2$と$a=a^2\sigma^2$とおいた時、

\[ Pr[(X-\mu)^2 \geq a^2\sigma^2] \leq \frac{E[(X-\mu)^2]}{a^2\sigma^2} = \frac{\sigma^2}{a^2\sigma^2} = \frac{1}{a^2} \\ Pr[\mid X-\mu \mid \geq a\sigma] \leq \frac{1}{a^2} \]

となる。なお、少し工夫して$a=a^2$とすると

\[ Pr[(X-\mu)^2 \geq a^2] \leq \frac{E[(X-\mu)^2]}{a^2} = \frac{\sigma^2}{a^2} \\ Pr[\mid X-\mu \mid \geq a] \leq \frac{\sigma^2}{a^2} \]

のように、確率変数$X$の実現値と期待値$\mu$の差を標準偏差$\sigma$を使わずに表現できる。この場合例えば「期待値が10で標準偏差が5の確率変数で100以上が出る確率は0.31%未満」($Pr[X-10 \geq 90] \leq \frac{5^2}{90^2} = 0.00308…$)などと求めることができる。

ヘフディングの不等式 Hoeffding’s inequality

独立な$n$個の確率変数$X[a,b]$において平均を$\overline{X}$、期待値を$E\left[\overline{X}\right]$とおいた時、任意の正数$u > 0$に対して

\[ Pr \left[\overline{X}-E\left[\overline{X}\right] \geq u\right] \leq \exp\left(-\frac{2n^2u^2}{\sum_{i=1}^{n}(b_i-a_i)^2}\right) \tag{4}\label{eq-4} \]

が成り立つ。\eqref{eq-4}をヘフディングの不等式と呼ぶ。

この不等式を用いることで、n個の確率変数$X$の平均と期待値の誤差が$u$以上になる(すなわち真の期待値を過大評価している)確率の上限を、確率分布に依らずに求めることができる。

同様に真の期待値を過小評価している確率の上限は、

\[ Pr \left[-\overline{X}+E\left[\overline{X}\right] \geq u\right] \leq \exp\left(-\frac{2n^2u^2}{\sum_{i=1}^{n}(b_i-a_i)^2}\right) \tag{5}\label{eq-5} \]

であり、真の期待値に対して$u$以上の誤差が生じる確率の上限は\eqref{eq-4}と\eqref{eq-5}を合わせた、

\[ Pr \left[\mid \overline{X}-E\left[\overline{X}\right] \mid \geq u\right] = Pr \left[\overline{X}-E\left[\overline{X}\right] \geq u\right] + Pr \left[-\overline{X}+E\left[\overline{X}\right] \geq u\right] \tag{6}\label{eq-6} \]

となる。

また、確率変数$X[a,b]$で$a=0,b=1$の時、\eqref{eq-4}より

\[ Pr \left[\overline{X}-E\left[\overline{X}\right] \geq u\right] \leq \exp\left(-\frac{2n^2u^2}{n}\right) = \exp\left(-2nu^2\right)\tag{7}\label{eq-7} \]

同じく\eqref{eq-5}より

\[ Pr \left[-\overline{X}+E\left[\overline{X}\right] \geq u\right] \leq \exp\left(-\frac{2n^2u^2}{n}\right) = \exp\left(-2nu^2\right)\tag{8}\label{eq-8} \]

である。証明は論文に譲る。

UCB1方策

UCB1方策では、ヘフディングの不等式\eqref{eq-8}を用いて、腕$j$の報酬の期待値の信頼区間の上側の上限である\eqref{eq-1}を求める。 \eqref{eq-1}を再掲する。

\[ \overline{x}_j+\sqrt{\frac{2\ln{n}}{n_j}} \tag{1} \]

腕$j$の報酬の期待値を$x^*_j$とすると\eqref{eq-8}は

\[ Pr \left[x^*_j \geq \overline{x}_j + u\right] \leq \exp\left(-2n_ju^2\right)\tag{9}\label{eq-9} \]

\eqref{eq-9}は真の期待値を過小評価している確率の上限であり、これを試行回数$n$が進むごとに小さくしたいと考える。そこで右辺を$n^{-m}=\frac{1}{n^m}$とすると、

\begin{align} \exp\left(-2n_ju^2\right) &= \frac{1}{n^m} \notag \\ -2n_ju^2 &= \ln{\frac{1}{n^m}} \notag \\ &= \ln{1} - \ln{n^m} \notag \\ &= 0 - m\ln{n} \notag \\ 2n_ju^2 &= m\ln{n} \notag \\ u^2 &= \frac{m\ln{n}}{2n_j} \notag \\ u &= \sqrt{\frac{m\ln{n}}{2n_j}} \notag \end{align}

が得られる。理論限界より$n$回目の試行において$1/n$の確率で各腕が選択する必要があるとされており、これに従えば$m=1$だが、論文では$m=4$としている(すなわち$u = \sqrt{\frac{2\ln{n}}{n_j}}$)。

これを\eqref{eq-9}に代入し

\[ Pr \left[x^*_j \geq \overline{x}_j + \sqrt{\frac{2\ln{n}}{n_j}}\right] \leq \frac{1}{n^4}\tag{10}\label{eq-10} \]

よって$1/n^4$の上限において、\eqref{eq-1}のスコアを用いて報酬の期待値を最も低く見積もっているであろう腕を選択することができる。すなわちOptimism in face of uncertaintyに従う。

参考

なぜ勉強会「だった」のか

主催するFukuoka.goでは2〜3ヶ月に一度の割合で登壇形式の勉強会を開催している。 昨今の状況を受けて前回こそYouTubeを使ってリアルタイム配信を行ったものの、この状況が続くあるいは当たり前になるならば、地域言語コミュニティをどう運営していくべきか考えないといけないだろうなと思う。

このエントリは、これまでの勉強会やカンファレンスではなぜ物理的に集合するのか、を自分の中で整理した上で、オンライン開催のありようを考える材料を見つけようとするものです。

なぜ物理的に集合するのか

これまでの勉強会やカンファレンスではなぜ物理的に集合していたのか。

今年、オンラインでの開催を余儀なくされた様々な勉強会やカンファレンスでは(それなりの運営の苦労はありつつも)比較的スムーズに移行できており、これはそのようなインフラが整っていたということに他ならない。 一方で、これだけのインフラがある中、必要に迫られるまでは物理的に集合していたということは、この行為になんらかの利点があると考えるのが妥当だと思う。

物理的に集合する勉強会やカンファレンスでは、登壇者の発表を聞き、質疑があり、飲食の機会が提供される。 同じ場に集ってリアルタイムに同時多発的に発生した議論によって、場には総体として大きくなった知が形成される。 参加者は、場によって増幅された知を様々な形で受け取る。 あるひとは有意義な情報として、あるひとはモチベーションとして。 想定より多くの量を得ることができる人もいれば、あまり得るものがなかった人もいるかもしれない。 主催者は、なるべくその機会を増やすべく、趣向を凝らす。

勉強会やカンファレンスというのは、興味関心を同じくするものの初対面の人たちを含む集団が限られた時間で効率よく、知の増幅を場に形成するための枠組みであると言える。

  • 発表者が資料を用意して丁寧に説明することで、「同じ事」を、
  • 日程や会場を揃えることで、「同じタイミング」で、
  • 質疑応答の機会や飲食による雰囲気を使って、「同じ立場」で、

参加者は一緒に考え、場を作っていく。

これまでは、物理的な集合を伴う勉強会やカンファレンスを開催することで、自然とこの枠組みに乗って、知の増幅を場に形成する機会を提供できていた。 物理的な集合を伴わないオンライン開催が前提になれば、これらを達成するための仕組みを意識的に演出しなければならない(あるいは目的自体を変える?)

オンライン開催は代替となるのか

せっかくオンラインでやれるのだから、漠然とこれまでの勉強会の代替ではなく、目的を明確にした上で技術的に解決できるといいなと思っている。

知の増幅を場に形成するのであれば、物理的な集合を伴わないオンライン開催であっても、登壇のリアルタイム配信によって参加者が、同じことを同じタイミングで考えることは有効だろう。 実際、難しいのは、「同じ立場」の部分だと思う。

興味関心を同じくするものの初対面の人たちが短時間で気兼ねなく議論できる状態を作りたい。 明示的な質疑応答の機会はもちろん必要だろう。 それでも、議論が深くなるとき、もしくは個別化しそうな時、同じミーティングルーム内で即座に個別かつ双方向に話せるだろうか。 昨年、登壇したGopherConでは、発表後はもちろんのこと、廊下でのすれ違うタイミングで感想や質問をたくさん受けた。そういうことを再現できないだろうか。

問題意識の方向性やレベル感が同じくする人を積極的に見つけて、同じ立場の中でクラスタリングされて、その問題を本当に考えたい人が凝縮して、それぞれの知を増幅して、総体として大きくなった知が形成される。

この辺りの、集団から始まって最終的に、個と個をダイナミックにつなげる部分をなんとか解決していきたいと思う。

Fukuoka.goはどうするのか

どうしよう。

Fukuoka.goは長期的にみて知の増幅を地域に形成できる(といいな)というあたりを狙っているので、主催者が楽しんで継続できることを大切にしています。 色々それらしきことを述べてみたものの、主催者のモチベは単純には「僕の最近のGo取り組みで面白かったものを聞いてください。よければご飯もどうですか」だったりもするので、オンライン飲みの余興で発表、とか、登壇を動画で配信とかでもいいのかもしれない。

軽量なインデックス機構を用いた全文検索ツールの高速化の検討

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

概要

コマンドラインによる全文検索ツールの検索速度は、キャッシュ機構、並列化や効率的なアルゴリズムの導入によって高速化が図られている。一方で、これらのツールは、検索対象の変更や削除への追従を避けるためインデックスの採用を行なっておらず、都度検索対象に対して全探索を行う。

全文検索ツールに対するインデックス機構の課題を整理、解決し、インデックス機構を採用することができれば、検索対象を限定した、より高速な検索が可能になると考えられることから、本稿では、軽量なインデックス機構を用いた全文検索ツールの高速化の検討を行う。

提案手法では、インデックス機構に計算量と情報量の観点で効率的に扱うことのできるブルームフィルタを採用する。 まず全ての検索対象に対してブルームフィルタを作成し、結合・転置した軽量なインデックスを生成する。 次に検索対象へのクエリを行う前にインデックスから候補を取得し、全文検索ツールがこれを検索する。 検索対象の変更や削除への追従に対しては、インデックスを都度再生成する方式を採用するが、生成の高速化により利用者が負担とすることなくこれを行える。

評価では、提案手法を組み合わせることで、全文検索ツールの検索時間が短縮することを確認する。

発表スライド

提案手法のアーキテクチャ、ならびに具体的な実装であるmonochromegane/sifterとこれによる軽量・高速・汎用性についての評価は発表スライドを参照のこと。

まとめ

本研究会では軽量なインデックス機構を用いた全文検索ツールの高速化の検討とその参考実装を評価した。 インデックス機構としてブルームフィルタを用いることで少ないメモリ使用量と問い合わせの高速化が達成でき、インデックス操作のツールに分離することで任意の全文検索ツールとの連携による汎用性を備えることができた。 結果として、評価では全文検索ツールとの組み合わせにおいて大幅な検索時間の短縮を確認した。

一方で、インデックス構築時間の長さを解消することは、利用者にとっての負担の改善の観点から最優先で取り組まなければならない。 ブルームフィルタにおけるハッシュ関数のボトルネックは多く研究されていることから、これを取り込むこと、また、ハッシュ関数の実行回数を減らしながら精度を保つことができるような効率的なトークン化を調べる必要がある。 実装面ではハッシュ関数の結果は再利用できるため、キャッシュ機構の導入も効果があると考える。

今後は問い合わせ自体にオーバーヘッドが発生するようなアーキテクチャとの連携も検討し、Webシステムの分野へ研究を発展させたい。

発表を終えて

今回のWSA研は初のリモート開催で新しい顔ぶれも揃い、6回目ながらに新鮮な気持ちで楽しめた。 自身の発表でも、あまり気負いすぎずに頭の中で温めていたアイディアを形にして議論として発展できればいいなぐらいで臨んだ。 結果的に、まずは発表に向けて形にして評価することで長所短所が明確になり、参加者から新しいアイディアのヒントをもらうことができた。 特に、これまでプラチナサーチャーでの全文検索の高速化は、システムコールやバッファ確保の効率化やタスクの並列化といったプログラミングの実装面でのアプローチがほとんどであったため、アルゴリズムの観点からの取り組むためのとっかかりを色々議論できたと思う。 この分野は先人の知恵が大量にある分野なので、色々勉強しつつプラチナサーチャーの進化系も考えていきたい(研究会終わった後の夜中に考えていた方法がSuffix Trieと同じだと気づいて、巨人の肩に乗るべく、まずは高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)を注文した)

このような普段の研究から少し離れた取り組みであっても、定期的に発表を促されることで形にすることができるのはとても大切で、やりっぱなし学びっぱなしではなく一つの区切りまで考え実装することで次回以降の研究への糧となる。 Webシステムアーキテクチャに関する運用知見を研究的アプローチで前進させること興味がある方は次回開催の参加を検討してみてはいかがでしょうか。

*次回は9月の後半のようです。

Dynamic Gamma-Poisson modelを試す

以前のADWINのように、変化する環境において適応的に振る舞うための仕組みについて調べる中で以下の論文で紹介されていたDynamic Gamma-Poissonモデルについてベイズ推定の理解を兼ねて試してみたのでメモ。

ベイズ推定

統計モデルとは

「ある確率変数$Y$の実現値$y=\{y_1,y_2,..,y_n\}$から、$Y$が本来従う確率分布(真の分布)を推定するためのもの」

とされている。 ベイズ推定はベイズの定理に基づいて観測したデータと過去の情報からデータの本来従う確率分布を推定する。

ベイズの定理 $p(\theta \mid y) \propto p(y \mid \theta)p(y)$ に対して右辺(尤度x事前確率)が具体的な確率値でかつ分布が数え上げられるような単純な場合は理解は比較的容易。

一方で、データの確率分布がパラメタによって変動するような確率質量関数や確率密度関数に従う場合、そのパラメタ(母数)の分布を推定することで、(分布の種類が分かっていればパラメタの推定が分布の特定になるので)データの従う確率分布を推定できる。 この時、データの分布の種類に応じた事前分布を選択することで事後分布が求めやすくなる(共役事前分布)。

このようなパラメタを推定するようなベイズ推定に関しては以下の資料が理解の助けになる。

以下、ポアソン分布のパラメタ推定を例にベイズ推定の理解を深め、これを拡張したDynamic Gamma-Poissonモデルを説明する。

ポアソン分布

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

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

ポアソン分布のパラメタ$\lambda$を推定する

Parameter Estimation Fitting Probability Distributions Bayesian Approachのp.19の例を元に説明する。

  • $X_1,X_2,..,X_n$ $i.i.d.$ $Poisson(\lambda)$
    • 単位時間に平均$\lambda$回起きる分布に従う確率変数の実現値を$n$回観測
    • $X_i$は0以上の整数値
  • $lik(\lambda) = f(x_1, x_2,..,x_n \mid \lambda) = \prod_{i=1}^n f(x_i \mid \lambda)$
    • 尤度はパラメタ$\lambda$において観測した値が得られる確率(この場合は上述したポアソン分布の確率質量関数$P(X=x_i)$)
    • 複数回観測した場合はその同時確率
  • $\lambda \sim Gamma(\alpha, \nu)$
    • 事前分布、つまり、$\lambda$が「ある値(の範囲)」を取る確率
    • 今回は事前分布にガンマ分布を仮定する(ポアソン分布の共役事前分布)
    • $\pi(\lambda)$
  • $\pi(\lambda \mid x) \propto lik(\lambda) \times \pi(\lambda)$
    • ベイズの定理より事後分布は尤度x事前分布で求められる
    • $P(x\mid\lambda)P(\lambda)$なので、$\lambda$の分布から観測値$x$が得られる確率と言える
  • $Gamma(\alpha^*,\nu^*)$ with $\alpha^*=\alpha+\sum_{1}^n x_i$ and $\nu^*=\nu+n$
    • 上を計算すると事後分布は観測された$x$の値の合計を$\alpha$に、観測回数$n$を$\nu$に加えたものをパラメタとするガンマ分布とみなせる
    • 観測したデータから$\lambda$の分布(確率変数が従う確率分布(分布の種類はわかっているのでそのパラメタ))を推定した

Dynamic Gamma-Poissonモデル

論文3.1によれば、クリック数$c$、閲覧数$v$、CTRを$\theta$としたときに、

  • 平均$v\theta$(=$\lambda$)である$Poisson(\lambda)$に従い観測されたクリック数から
  • $\theta$の事前分布に平均が$\alpha/\gamma$、分散が$\alpha/\gamma^2$である$Gamma(\alpha,\gamma)$を仮定して
  • $\theta$の事後分布を$Gamma(\alpha+c,\gamma+v)$として得られるとしている

ただし、実際はこの推定は$\lambda$の推定であるため、CTRとして考えるために以下のように考える。

  • $\lambda$を1閲覧($v$)の間の平均回数と考える(つまり$\lambda=1*\theta$)
  • 1閲覧に該当する期間を閲覧数分、観測した
  • これによって推定された$\lambda$は$\theta$と等しくなる

ここで、$Gamma$のパラメタはこれまでのクリック総数と閲覧総数であることから、$\lambda$の値が変化する場合に過去のデータに引きづられてしまい、速やかな追従を行うことができない。 論文では、Dynamic Gamma-Poissonモデルとして過去の観測結果に対する割引の概念を導入することでこれを解決する。 実現はシンプルで、割引率$(0< \delta \leq1)$を導入し、事後分布を$Gamma(\delta\alpha_{t-1}+c_t,\delta\gamma_{t-1}+v_t)$のように求める。 これによって累積された過去の総数を減らし、直近のデータに重み付けが行われる。 論文中では0.95から1の間ぐらいが良い結果を得たとしている。

以下、実際に同じ条件での$\lambda$の推定を通常のGamma-PoissonモデルとDynamic Gamma-Poissonモデルで行ったものを比較する。 評価では、CTRが0.4のアイテムに対して1ステップごとに7回の閲覧が行われた際のクリック数を観測データとした。 また、20ステップ目にCTRが半分の0.2になっている。

dgp

評価期間内では通常の推定の期待値0.3程度までの追従に止まったが、Dynamicな手法ではより早く実際のCTRである0.2に近づけたことが分かる。

動作確認用のコード

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

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

python dgp.py --lambda_ 0.4 --view 7 --delta 0.9

勉強会をオンライン配信するための必要最小限な環境構築

昨今の状況だけでなく、多様な働き方やコミュニティ(とそこで得られる情報)に接する機会を増やすためにも今後、オンライン勉強会は広がっていくと思います。 Fukuoka.goでも今回、初めて勉強会のオンライン配信を実施しました。 同様のモチベーションを持つイベントの主催者に向けて、勉強会をオンライン配信するためにやった最小限の環境構築についてまとめておきます。

想定する環境

オンライン勉強会には、Google Hangouts Meetなどのビデオ会議のWebサービスとYouTubeライブ配信を用います。 勉強会には、配信を行う運営者、発表を行う登壇者、発表を聞く参加者がいるとします。

登壇者はビデオ会議の画面共有によって各々のPCから発表を行います。 運営者はビデオ会議の画面と音声をYouTubeでライブ配信します。 参加者はYouTubeのライブ配信を視聴、必要に応じてコメントします。

architecture

ビデオ会議とライブ配信のWebサービスを利用することで、Macに二つオープンソースソフトウェアをインストールするだけで、最低限の配信環境環境が整ってしまいます。ありがたい時代になりました。インターネット万歳。

手順のサマリ

1. YouTubeアカウントを作成(要Googleアカウント)
2. YouTubeライブ配信を作成(初回は24時間程度待つ必要あり)
3. 配信に必要なソフトウェアをダウンロードしてインストール
  - [OBS Studio](https://obsproject.com/download)
  - [BlackHole](https://github.com/ExistentialAudio/BlackHole)
4. YouTubeエンコード配信を選択し、ストリーミングキーを発行
5. OBSにストリーミングキーを設定
6. OBSで音声ミキサーとしてBlackHoleを追加(マイク2)
  - 必要に応じてマイク(1)はミュート
7. OBSでソースにウィンドキャプチャでMeetを実行するブラウザを追加
  - ウィンドウキャプチャに必要なウィンドウが出ない場合はmacOSXのセキュリティとプライバシーでOBSが画面収録を許可されているか確認
8. macOSXの音声出力をBlackHoleに変更
9. OBSで配信開始をクリック
  - しばらく待つとYouTube側の配信ボタンが押せるようになる
10. YouTubeの配信開始をクリック
11. 配信する
  - 画面がチラつく場合はOBS Studioがウィンドウキャプチャしている画面の前面に配置されていないか確認
12. YouTubeの配信終了をクリック
13. OBSの配信終了をクリック

手順の詳細

以下、上記手順についての詳しい説明です。

なお、配信のための環境構築には配信の専用機を用意するのが一番楽でしょう。 以下、配信の専用機としてMacBook Pro (15-inch, 2019) macOS Catalina(10.15.3)を用いています。

また、配信に利用するPCは有線によるネットワーク接続をおすすめします。

YouTubeアカウントを作成

持っていなければ作成しましょう。Googleのアカウントが必要です。

YouTubeチャンネルを作成

ライブ配信をするチャンネルを作成しましょう。

YouTubeライブ配信を作成

ライブ配信を開始 ボタンからライブ配信を登録します。 初めてライブ配信を登録する場合は、24時間待つ必要があるため、余裕を持って登録しましょう。

start

エンコーダ配信 タブから、タイトル、公開範囲、カテゴリを指定します。 作成後、ライブ配信のための ストリームキー が取得できるため控えておきます。

配信に必要なソフトウェアをダウンロードしてインストール

ライブ配信をサポートしてくれる OBS Studio と仮想オーディオデバイスを作成するための BlackHole をインストールします。

*BlackHoleはmacOSから出力される音声(今回の場合ではビデオ会議の音声)をYouTubeで配信するために利用します。配信機がWindowsであればデスクトップ音声をキャプチャできるそうなのですがmacOSではできないため、BlackHoleで仮想オーディオデバイスを作成して回避します。

以下、OBS Studioは 24.0.6 (64 bit)、BlackHoleは v0.2.6を利用した場合の手順となります。

OBS Studioでストリームキーの設定

  1. 設定 -> 配信
  2. サービスにYouTube/YouTube Gamingを選択
  3. サーバーにPrimary YouTube ingest serverを選択
  4. ストリームキーに先ほど控えておいた値を入力

OBS Studioで音声の設定

  1. 設定 -> 音声
  2. マイク音声 2にBlackHole 16chを選択

必要に応じてマイク音声(1)は無効、もしくは配信時にミュートしておくと余計な音声が入らずに便利。

OBS Studioで配信ソースの設定(待ち受け画面)

配信の準備中やビデオ会議の画面を表示したくない時の待ち受け画像のシーンを準備しておくと便利。

  1. シーンを選択し、画像ソースを追加
  2. 新規作成からOKで画像プロパティが表示される
  3. 画像ファイルを選択してOK

OBS Studioで配信ソースの設定(ビデオ会議画面)

タブブラウザの場合、ビデオ会議のウィンドウは分けておくと便利。

  1. 待ち受け画面とシーンを分けるのでシーンを追加
  2. 新しいシーンを選択し、ウィンドウキャプチャソースを追加
  3. 新規作成からOKでウィンドウキャプチャプロパティが表示される
  4. ビデオ会議のウィンドウを選択

ウィンドウに起動中のアプリが表示されない場合は、macOSの設定->セキュリティとプライバシーから画面収録に対してOBSの許可がチェックついているか確認のこと。

OBS Studioの設定確認

ここまででOBS Studioの下部は以下のような設定になっているはずです。

obs

シーンは静止画用、シーン2がビデオ会議の画像用です。 僕の環境ではシーン2に、ビデオ会議の画面とTwitterの画面を二つ並べて表示するようにしたので、ウィンドウキャプチャのソースが2つあります。

また、音声ミキサーはマイク2をミュートにすれば、ビデオ会議の音声が配信に乗らなくなります。

macOSの音声出力をBlackHoleに変更

ビデオ会議の音声をBlackHole経由でOBS Studioに渡せるようにします。 macOSの設定->サウンドから出力タブでBlackHoleを選択します。

  • *macOSの音声出力をBlackHoleに変更するとmacOSからは音声が聞こえなくなります。音声も聞きたい場合は、macOSのユーティリティ->オーディオ装置から複数出力装置を作成し、MacBookのスピーカーとBlackHoleに同時に出力できるデバイスを作成してください。そしてmacOSの音声出力をBlackHoleではなく、複数出力装置を選びます(OBS StudioはBlackHoleの入力側を利用するのでそのままで良いです)。 Ref: https://github.com/ExistentialAudio/BlackHole/wiki/Multi-Output-Device 手元では、複数出力装置について外部オーディオ装置との相性が悪かったため利用していません(配信の専用機なのでここから音が聞こえる必要はなく現在のところBlackHoleを直接利用で困ってない) もし、外部オーディオ装置も含めて高度な設定が必要な場合は、LadioCastなどのソフトウェアミキサーの導入を検討してください(そして良いやり方があれば教えてください)

OBS Studioから配信開始

OBS Studio側で配信開始ボタンをクリック。 しばらくするとYouTube側の管理画面に配信のプレビューが表示され、YouTube側のライブ配信開始ボタンがアクティブになる。

YouTubeから配信開始

YouTube側でライブ配信を開始ボタンをクリック。 30秒程度で参加者にライブ配信が見えるようになる。

配信中

YouTuberとして頑張る。適宜シーンの切り替えやマイクのミュートなど操作が必要です。

  • ウィンドウキャプチャの画面がチラつく場合は、OBS Studioがキャプチャするウィンドウの前面に表示されていないかを確認しましょう。 僕の環境では、OBS Studioをこれらより背面に持っていくことでチラツキが解消しました。

YouTubeで配信終了

YouTube側でライブ配信を終了する。

OBS Studioで配信終了

OBS Studio側で配信終了ボタンをクリック。

配信後

ライブ配信の動画は自動でアーカイブとして公開されます。 アーカイブに残さない場合は、YouTubeのライブ配信の管理画面から削除が必要です。 この辺りは事前に発表者に了承をとっておく必要があると思います。

動画の編集もYouTubeの管理画面から行えるため、必要に応じて無言の時間などを取り除くことが可能です。

editor

初のオンライン配信を終えての感想など

これまでFukuoka.goでは、他の地域のコミュニティと拠点間をリモート接続する取り組みは既におこなっており、これをライブ配信に乗せるだけだろうと思っていましたが、それなりに準備や実行で大変だった点や反省点もありました。

よかった点

  • 高速な配信環境を準備できた(配信のネットワーク環境は結構重要。家のネットワーク(特に上り)が遅いと配信できないので注意)
  • 事前に発表者にアーカイブ残すことについてきちんと承諾をもらった
  • 事前にOBS Studioの設定を終わらせて、当日は起動するだけでよかった
  • 登壇者はイベント30分前にビデオ会議に集合して画面共有やミュートのルールなどの手順をおさらいした
  • 事前にオンライン配信のノウハウを仕入れることができた
  • 発表の始まりと終わりはある程度、司会者も音声オンで入っておき盛り上がりを演出できた
  • 静止画のシーンを用意することでビデオ会議の切り替えなどのもたつきがあっても配信上は見せないようにできた

反省点

  • 配信準備した環境と配信を行った環境が違ったので設定周りで当日焦った(リハーサル大切…)
    • 画面のチラつき(途中で解消してよかった)
    • 画面サイズの違い
  • 発表中の登壇者に対して、連絡をとる手段を用意していなかった
    • 打鍵音が気になる、発表時間過ぎてるなどを伝えようとするとそれも配信に乗ってしまう
  • 発表中の登壇者がコメントの盛り上がりなどを見るのが難しかった
  • Twitterの画面を共有していたが自動更新にならないので手動で更新する手間がかかった

などです。

今回の構成は、登壇形式の勉強会において、参加者が視聴する際の敷居を低くすることを目的に設計しました。 参加者にとっては個別のビデオ会議のWebサービスのアカウントが不要ですし、運営者にとってもビデオ会議のアクセス制限や人数制限を気にする必要がありません。 もちろん、勉強会の方式(双方向のディスカッション)によっては他のやり方が最適な場合もあると思います。 そのような場合についてのノウハウも共有してもらえれば嬉しいです。

Archives