ヒューリスティックコンのパラメータチューニングをGCPでやる
AtCoderのヒューリスティックコン(https://atcoder.jp/contests/intro-heuristics)のような短時間のコンペのパラメータチューニングをGCPで行ってみました。
理想のラン環境を求めて - threecourse’s blog のつづきです。
(ソースコードは、敵に塩を送りたくない整理できていないので公開せず、考え方のみまとめています。)
概要
- GCPを使って、並列でOptunaによるパラメータチューニングを行う
- Google Cloud Run(以下Cloud Run)というサービスを使うと、計算時間の短い計算を比較的簡単にスケーリングしてくれる
(他のサービスだと、クラスタの構成が面倒だったり、起動時間がかかったりする)
設定と結果
設定は以下のとおりです:
- Introduction to Heuristics Contest(https://atcoder.jp/contests/intro-heuristics)を問題とする
- 焼きなまし解法の「終了温度」「開始温度/終了温度」「2点スワップの割合(残りは1点更新)」をチューニング対象のパラメータとする
(参考:Introduction to Heuristics Contestの解法 https://img.atcoder.jp/intro-heuristics/editorial.pdf) - パラメータチューニングのために100試行を行う。
- パラメータの評価に用いるスコアは、10テストケースの平均をとする。
- 10並列 x 5バッチ(2ケースごとのバッチにする)で並列処理させる
結果は以下のようになりました:
- 並列なしだと2秒 x 10テストケース x 100試行で2000秒かかるところ、90秒程度で計算完了(なかなか実用的)
- ベストのパラメータは、(開始温度・終了温度・2点スワップの割合)=(2488, 556, 0.79)となった。 解説を参考に作成した(開始温度・終了温度・2点スワップの割合)=(2000, 600, 0.5)と同程度の結果となった。
雑感:
- AtCoder環境の方がCloud Runより2倍程度性能が良さそうなので、Cloud Runでの計算時間は2倍程度にすると良さそう。
- チューニングを繰り返すと微妙なパラメータがベストとなることもあり、「最適なパラメータチューニング」となっているかは分からない。 引き続き要検討だが、試行回数を増やすのが良いような気もする。
構成
全体の流れ
パラメータチューニングの全体の流れは、以下のようになります。
- Optunaの初期化を行う
- Google Cloud Storage(以下GCS)にテストケースとバイナリをアップロードする
- Optunaでの並列パラメータチューニングの実行を開始する
- 各パラメータの試行では、
・10個のテストケースを実行し、その結果の平均をスコアにする
・10個のテストケースの実行は、2ケースごとのバッチにしてCloud Runに計算依頼を飛ばすことで行う
・Cloud Runの計算において、GCSからテストケースとバイナリをダウンロードする
・10並列で行う(つまり、10並列 x 5バッチ = 50個の計算依頼が飛んでいる状況になる) - パラメータの試行100ケースが全て終わると、最も良いパラメータを選んで終了する
最適化プログラムの構造
パラメータを受け取り、計算結果を返せるように、最適化プログラムを組んでおく必要があります。
- 引数として「名前」「テストケース名」「各パラメータ」を受け取り、
結果である「スコア」や「焼きなましの計算回数/更新回数」などの補助情報をjsonファイルなどに出力する仕組みにします。 - こうすることで、外部からPythonなどを用いて、最適化プログラムを並列で叩いてその結果を取得できるようになります。
- このまま提出するとWrong Answerになってしまうので、コンパイル定数などを用いて手元でコンパイルしたときと提出したときの挙動を変える必要があります。
Optuna
Optunaは、改めて非常に使いやすいツールですね。
- SQLiteに結果を保持するなどで、並列でのパラメータチューニングが可能です。
https://optuna.readthedocs.io/en/stable/tutorial/distributed.html
今回は、multiprocessing.Poolで並列にし、各スレッドでStudy.load_studyからのStudy.optimzeを行うようにしました。
その他、以下の機能が便利でした。
- Study.trials_dataframeを使うと、結果をpandasのDataFrameに整形してくれます。
https://optuna.readthedocs.io/en/stable/reference/study.html#optuna.study.Study.trials_dataframe - StudyやTrialに情報を付加することもできます。
https://optuna.readthedocs.io/en/stable/tutorial/attributes.html
Cloud RunにデプロイするDockerイメージ
Cloud Runは、リクエストを処理している間のみ課金され、また自動的にスケールしてくれるという素晴らしいサービスです。
Cloud Runを使うためには、httpリクエストを受け取り、レスポンスを返すDockerイメージを作成する必要があります。
今回は、flaskでhttpリクエストの処理を行い、その中でC#の最適化プログラムを動かすため、C#とPython(Anaconda)を動かせる構成にしています。
Dockerイメージ内の処理は、以下のような流れになります。
- httpリクエストのデータとして、「ランの名前」「計算対象となるケース名のリスト」「パラメータ」を受け取る
- 「ランの名前」を基にGCSからテストケースとバイナリをダウンロードする
- 「計算対象となるケース名のリスト」の各ケースを「パラメータ」を指定して実行し、結果を取得する
- 結果のリストをレスポンスとして返す
Cloud Runの設定
最大100までインスタンスを立ち上げ、インスタンス内の同時実行数は1、実行時間制限は(一応)15分、インスタンスはCPU1個、メモリ512MBという設定にしました。
同時実行数を1にすることで、複数の計算で同時にCPUを使うことを防ぎ、正しく計測できるようにしています。 たまになぜか計算回数が半分くらいになることがあるようですが、概ね計測に問題は無さそうです。 もう少し攻めた設定にしても良いかもしれません。
なお、インスタンスがスケーリングしている最中には、429や500といったレスポンスを返すことがあるので、それらのときには少し待って再度リクエストを投げるようにする必要があります。
Cloud Runの料金はそれほどでもないのですが、ログには注意が必要です。 標準出力がログとして飛んでいってしまうので、最適化プログラムで一定間隔ごとに焼きなましの温度などを出力するようにしていると、1回のチューニングで数十GBのログが飛んでいくことがあるようです(怖)。GCPのログ取り込みで除外設定を作成するか、最適化プログラムを叩くときに標準出力・標準エラーをDEVNULLなどで抑止する必要があります。
継続的インテグレーションについてのメモ
参考資料
少し古いが、テストの分類など以下のスライドがよくまとまっている。
www.slideshare.net
また、CircleCIでチュートリアル+αをやりました。 circleci.com
(CircleCIのドキュメント、Orbs・ジョブ・アーティファクトといった用語の具体例がなかなか出てこないので、初心者には分かりづらいような・・)
その他、以下の書籍を参考にしました。
- 継続的デリバリー 信頼できるソフトウエアリリースのためのビルド・テスト・デプロイメントの自動化
https://www.amazon.co.jp/dp/B074BQQ96X - 継続的インテグレーション入門
https://www.amazon.co.jp/dp/482228395X - チーム開発実践入門──共同作業を円滑に行うツール・メソッド
https://www.amazon.co.jp/dp/B07JLQD763
継続的インテグレーションとは?
定義は上記文献や継続的インテグレーション - Wikipediaを参照。
私の理解では、常に「クリーン」な状態を保ちながら開発するために、ソースコードのバージョン管理とテスト・ビルド・デプロイを自動化して接続すること。CIと略記される。
CIサーバ
継続的インテグレーションを行うために、以下のCIサーバと呼ばれるサービスがある。
CIサーバでは、以下の設定を行うことになる。
- ビルド、テストといったジョブを定義する
設定ファイルはyamlなどで記述する - トリガーを指定する
Pushされたとき、プルリクエストが送られたときなど、ジョブを起動するトリガーを指定する
APIを叩くなどで手動実行もできる - GitHubやBitBucketなどと連携設定をする
CIサーバは、以下の機能を持つ。
- トリガーとなるイベントが発生すると、上記のジョブを実行する
ジョブは、docker imageを用いて行われる。また、並列や依存関係を考慮して実行が行われる - テストに失敗するとそのジョブは失敗する。
- アーティファクトと呼ばれるビルド時生成物を保存する仕組みがある
アーティファクトの例は、テストのカバレッジやビルドされたバイナリなど - ジョブの状況、テスト結果やアーティファクトをWeb画面から見ることができる
雑感
競技プログラミングの解説に必要な要素
AtCoderの解説についての議論があったので、考えたことを書いてみました。
最近あんまりratedに参加していない中、外からなんやかんや言うのはあれなのですが、何かの足しになれば。
(私のアカウントは https://atcoder.jp/users/threecourse です)
解説に必要な要素
解説を構成する要素は以下だと考えています。
- 解法の実装の概要
- 解法の正当性の証明
- 解法をどうやって思いつくか
この中で核となるのは、「1. 解法の実装の概要」で、これがないと解説(解答?)として不完全であるように感じます。 結局ACするには解法の実装が必要で、それに直接結びつく要素であるためです。
ABC170の解説 https://img.atcoder.jp/abc170/editorial.pdf についてtwitterが盛り上がったのは、この部分が省略されたからではないでしょうか。
手法をどのレベルまで説明するかといった粒度、手順をソースコードなどを使って詳細に説明するかどうかといった細かさは、難易度によっても変わるだろうし、
また解説を書く人の趣味や優しさで幅がありうると思います。
例えば、DPで「DPテーブルを何と何をインデックスとして持ち、以下の更新式で更新していく」くらいの記述で十分なところ、低難易度であれば丁寧にDPの概念を説明することもできますし、高難易度であれば「この部分はDPでO(N)で求めます」で良いこともあるでしょう。
また、コーナーケースもここに含まれるのが基本かなと思います。コーナーケースを処理できないことにはACできないので。
なお、「1. 解法の実装の概要」を記述する積極的な意味として、他の部分の文章を誤解したときに正しい方向に戻って来やすい点があります。
例えば「~を思いつけば簡単にできます」と書いてあったとして、なるほどとACできることもあれば、実力がある人であっても日本語の意味の取違いで明後日の方向に思考が飛んでしまうこともあります。このとき、「1. 解法の実装の概要」が書いてあれば、誤解に気づきやすいです。
「2. 解法の正当性の証明」「3. 解法をどうやって思いつくか」については、自明で書く必要がない問題も多いでしょう。
ただ、「本質」がこれらに含まれる問題もあります。「その方針は思いついたけど自信がなく、証明できなかったので実装するに至れなかった」「それで解けるのは分かったけどどうやって思いつくんだ」という参加者が出るような問題です。
この場合には、「2. 解法の正当性の証明」はないと不完全な感じがあり、「3. 解法をどうやって思いつくか」は説明した方が親切かなと思います。
解説の位置づけ
「解説(PDF)はおまけだよ」vs「解説はコンテストを構成する一要素」という認識のずれが、議論している人の間であるように感じました。
私は後者の考え方に近いです。解けなかった問題の解説がどこにもない場合、自力でACするには半日などその問題について考える必要があってつらくなることもあるので。 現状、解説(PDF)が分かりづらい場合でも、動画もありますし、コミュニティの力でどこかに分かりやすい解説が落ちているため、困ることはあまり無いですが。
フロントエンド何もわからない(その3)
しばらく経つといろいろ忘れますが、覚え直すと少しずつレベルアップしている感じはありますね。 今回は、グリッド上に情報を表示するGUIを作ってみたかったため、8クイーン問題を題材にしました。
WebページはGitHub Pagesを使って公開しています。
コードはこちらです。
Nuxt.jsの利用
Vue.jsというjavascriptのフレームワークに、さらにいろいろ盛り込んだフレームワークがNuxt.jsです。
データを保持するVuexが組み込まれているなどの利点があり、ディレクトリ構成などのお作法を統一する意味でも、Vueを使うなら最初からNuxtにしてしまった方が早いかなと思いました。 シンプルな処理ならNuxtのみで良く、 必要に応じてバックエンドサーバを立てて計算はそこに投げるような構成にすると良いでしょう。
(参考)Nuxt.jsビギナーズガイド https://www.amazon.co.jp/dp/B07J5434JB
Bulmaの利用
Bulmaは、javascriptが組み込まれておらず、比較的シンプルなcssフレームワークです。何もcssフレームワークを入れない場合と比較すると、だいぶ見た目がよくなります。
(Nuxt.jsのデフォルトのインストール方法では最新版が入るとは限らないので、npmで自分で入れる方が良いのかも)
CSS
別に凝ったものを作ろうとしなくても、CSSの理解が必要になるのはやむ無しな感じです。
セレクタ、padding/margin、FlexBoxあたりを理解しておかないと、簡単なものを作るにもググりまくることになります。
(参考)CSS Flexbox エンジニアのためのWebチートシート https://web-cheatsheet.com/css-flexbox
全体のレイアウト
自分なりのやり方で、以下はBulma前提です。
- トップにnavbarクラスを設定
- その下をcontainerクラス->columns-> [column, column] で分け、columnの左側をコントロール、右側を出力画面にする
columnの幅はwidthを指定して固定するのも良いかもしれない - ある領域を列に分割するときには、columnsとcolumnを使う
- ある列の中で縦に並べるときは、普通に要素を置いて行けば良いが、行に要素を詰めてレイアウトを構成するときはlevelとlevel-itemを使うこともできる(cssでFlexBoxの記述をする方法もある)
- 余白が気持ち悪い場合は適宜cssで記述して修正する。
spacing-helpersを使う方法もある https://bulma.io/documentation/helpers/spacing-helpers/
ヴィジュアライズしたい要素のレイアウト
(いくつか方法はあるが)Vueのv-forでdiv要素を生成し、位置はabsoluteで指定するのが簡単
absoluteの子要素のセンタリング
absolute内の要素ではvertical-alignは効かないらしい。FlexBoxを使う方法が良さそう
(参考)テキストの縦方向の中央揃えについて - Qiita
通知
通知機能をつけたい場合、toastrが良さそう
https://github.com/CodeSeven/toastr
マウス、キーボードによる操作
- マウスについては、要素に@clickなどでイベントをセットすることで、クリック操作を捉えることができます。
- キーボードについては、
window.addEventListener('keydown', this.onKeyDown, false)
のようにしてキー押下などのイベントを捉えることができます。
GitHub Pagesへの公開
静的なウェブアプリケーションを生成し、gh-pagesブランチに置いておくと、GitHub Pagesに公開されます。レポジトリをPublicにするか課金する必要がありますが、少し設定を修正するだけで割と簡単に公開できました。 ja.nuxtjs.org
理想のラン環境を求めて
Kaggleやマラソンマッチで、ランをサクッと投げたいというモチベーションのもと、GCP(Google Cloud Platform)の構成を調査していました。
以下のリポジトリにコードを載せています。
GitHub - threecourse/run-environment-public
まだ何も実戦で試していないものなので、作ったは良いものの、実際に使うときにはいろんな問題が出てきて手動でやることになりそうですが。
現時点の結論としては、
- 10分〜数時間以上かかるようなランには、Compute Engineのインスタンスを毎回立ち上げて消す
- 数十秒〜数分の比較的短いランでは、 Cloud Run + Cloud Tasksにランのリクエストを投げる
要件
1.ランを投げたい
ローカルのPCから、python run.py --param1 10
のように書いたらランがサーバ上で実行され、終わったら結果をどこかに保存してくれると嬉しいですね。
ローカルのPCで計算が動いていると、どうしても集中できなくなるので。
以下の2つのユースケースを想定します。
- 10分〜数時間以上かかるようなラン。Kaggleの画像系コンペの計算を想定。
- 数十秒〜数分のラン。マラソンマッチを想定。
(実際は多数ケースを流すので、もっと時間がかかってa.と同じ扱いで良いのかもしれない)
前者の場合だと、起動までに数分かかっても問題ないでしょう。 一方で後者の場合だと、数秒〜数十秒で起動してほしい気持ちがあります。
2.dockerを使いたい
昨今はdockerを使うメリットが大きくなってきているように思います。 環境を持ち運びできるのはさまざまな場面で便利で、 例えばローカルPCでは計算量が足りず、クラウド上のサービスに載せたくなったときもdockerで動くようにしてあると比較的スムーズです。
3.コードとの紐付けを行いたい
コードを変更したらスコアが下がったので、前のスコアの良かったランと比較してデバッグしたい、といったときに前のランのコードを参照できないとつらいです。 なので、ランにはgitのcommit idなどを紐付けしておき、ラン間のコードの差分を見れるようにしておきたいです。
ソリューション
1.構成
まず、適当なdockerイメージをビルドしておきます。 GCR(Container Registry)にpushしておくと、GCP上の他のサービスからそのdockerイメージを呼び出せます。
a. 計算時間が長い場合
計算時間が長い場合は、Compute Engineのインスタンスを毎回立ち上げ、計算終了時に消す構成がシンプルです。
gcloud compute instances create-with-container
コマンドによって、dockerイメージを呼び出してスクリプトを起動することができます。欠点として、コンテナが起動するまでにdocker イメージのサイズに応じた時間がかかることがあります。どうもdocker imageのpullに時間がかかっているようで、1GBあたり1分弱くらいかかっていました。これが気になる場合、マシンイメージを作ってからそれを起動する方法もあるかもしれません。
プリエンプティブインスタンスを利用することで課金を抑え、かつ計算中にインスタンスが落ちることに対応するには、インスタンスグループを使用する方法もあります。
(参考)https://github.com/sfujiwara/preemptible-trainer
b. 計算時間が短い場合
Cloud Run + Cloud Tasksという構成が良さそうでした。
Cloud Runは、「フルマネージド環境でステートレス コンテナを実行するサービス」らしいです。 何のこっちゃという感じですが、サーバを立ててhttpリクエストを受け付けるコンテナを作っておくと、自動的にスケールさせてくれ、また動いている間のみ課金が発生するというサービスです。
Webサービスをホストする使い方が主らしいですが、今回のような計算タスクでも使えそうでした。ただし、最大で15分までしか処理を行えないため長時間かかるタスクには不向きです。
dockerイメージは、a.に加えて、httpリクエストを受け付けて計算するサーバを立てる構成にする必要があります。
直接Cloud Runにhttpリクエストでランを投げる方法もありますが、Google Cloud Tasksを噛ませることで、
Cloud Tasksにランを投げる→キューに入れ、同時実行数などを管理しながら逐次Cloud Runに実行させる、という流れにしてくれます。マラソンマッチでは一定時間に計算した結果によるスコアを競うため、正しく評価するためにはランで使用できるCPUリソースが一定である必要があります。
Cloud Runではインスタンスあたりの同時実行数を制限することができるため、同時実行数を1にするとまぁまぁ良い・・のですがたまに誤差は出るかも。
c. その他の選択肢
- GKE(Google Kubernetes Engine)を使う方法もありますが、ちょっと設定が複雑ですね。
- 自分でインスタンスを起動・停止させるオートスケーラーを書きかけましたが、さすがにこれも面倒なので撤退。
- AI Platform Training(https://cloud.google.com/ai-platform/training/docs?hl=ja)を使う方法も有力なようです。ただ、起動時間はCompute Engineのインスタンス立ち上げと同程度にはかかると聞きました。
2. コードの投げ方
- ランを投げるときには、
code
フォルダを固めてGCS(Google Cloud Storage)に送り、GCP上のインスタンスやCloud Runからダウンロードして実行します。 ローカルでデバッグしたいこともあるので、そのときにはローカルでdockerを起動し、この場合は
code
フォルダをマウントするようにします。コードの紐付けは、以下のようにすることで、gitのcommit idで紐ついた形で管理し、また何かの事情でcommitせずにランを実行したいときにも対応できます。
- gitが綺麗な状態であれば、ランする際に
git rev-parse --short HEAD
コマンドで現在のcommit idを取得するようにします。 - gitが綺麗な状態でなければ、
--commit_id
引数を与えることを必須とします。 - gitが綺麗な状態か否かの判定は、
git status --short
で行います。
- gitが綺麗な状態であれば、ランする際に
3. 流れ
流れをまとめると、 以下のようになります。
Compute Engineのインスタンスを使う場合:
- フォルダ
code
を固めて送ることで、コードをGCSに送付する - Compute Engineインスタンスでコンテナを起動する
- コードをGCSから取得する
- 計算を実行する
- 計算結果をGCSにアップロードする
- Compute Engineインスタンスを自ら終了させる
Cloud Run + Cloud Tasksを使う場合:
- フォルダ
code
を固めて送ることで、コードをGCSに送付する - Cloud Taskを通してCloud Runにhttpリクエストを送る
- Cloud Runはhttpリクエストを受けて計算処理を実行する
- コードをGCSから取得する
- 計算を実行する
- 計算結果をGCSにアップロードする
その他のTIPS
ログ
Cloud Logging ライブラリをインストールし、setup_loggingメソッドを記述しておくと、loggingモジュールで出力したログは自動でCloud Logging上にも送られます。まぁまぁ便利。
(参考)https://cloud.google.com/logging/docs/setup/python?hl=ja
結果の保存と取得
- ランを行った結果(ラン名、計算時間、スコア、commit idなど)はGCSに送っておく
- GCS上の結果を見る場合は、何だかんだで
gsutil
コマンドを使って一度ローカルに落として分析するのが早そう - GCPのデータポータルやCloud Datalabは今回の目的だといまいちかも。
GCPのAPI
GCPのAPIには3つくらい種類がある様子で、調べるときに混乱しがち。
ここの説明が一番まとまっているか?
https://cloud.google.com/apis/docs/client-libraries-explained?hl=ja
Google Cloud SDK
いわゆるgcloudコマンドで、コマンドラインから実行するもの。一番充実しているような気がする。
https://cloud.google.com/sdk/gcloud?hl=jaGoogle Cloudクライアント ライブラリ
Pythonから呼び出せるわりと使いやすいインターフェイス。
https://cloud.google.com/apis/docs/cloud-client-libraries?hl=jaGoogle API クライアント ライブラリ
少し古いらしいが、このAPIでしか対応していないものもある様子。
https://cloud.google.com/endpoints/docs/frameworks/python/access_from_python?hl=ja
追記:
Cloud Runを使う場合は、以下に注意が必要:
threecourse.hatenablog.com
CatBoost論文のprediction shiftについて完全に理解する
CatBoostの論文における、prediction shiftについて調べる機会があったのでまとめてみました。
(CatBoost: unbiased boosting with categorical features https://arxiv.org/pdf/1706.09516.pdf )
以下は、論文の4.1 Prediction shift、AppdendicesのA Proof of Theorem 1を元に、私の理解で構成しなおしたものです。
概要
勾配ブースティングの計算において、各ブースティングで同じ学習データを使うことにより、偏りが発生する。
シンプルな以下の前提で考える。
データセットの前提
データセットの前提は以下のとおり:
- データの個数は$n$個、特徴量は $(s, t)$ の2つ
- $s, t$はそれぞれベルヌーイ分布($p=0.5$)に従う二値変数
- 目的変数 $y = c_1 s+ c_2 t$ であり、誤差は無い
つまり、このデータは以下のようになっている。
- 4種類のデータ $(s, t) = (0, 0), (1, 0), (0, 1), (1, 1)$ から構成される。
- 目的変数yの値はそれぞれ、$0, c_1, c_2, c_1 + c_2$である。$f^*(s, t)$とも表すことにする
- 分布に従ってこれらのデータを生成するとき、現れたデータの個数を $\xi_{00}, \xi_{10}, \xi_{01}, \xi_{11}$ で表すことにする
学習の前提
学習の前提は以下のとおり:
- 勾配ブースティング木で回帰タスクを解く、目的関数は二乗誤差。
- 木の数は2、木の深さは1とする。
$c_1$の方が$c_2$より大きく、1本目の木では$s$による分岐が行われ、2本目の木では$t$による分岐が行われると仮定する。
主張
1本目、2本目の木の学習に使うデータセットをそれぞれ$D_1$, $D_2$としたとき、
- $D_1$と$D_2$が独立に生成されたサンプルであれば、学習されたモデルによるデータ$(s, t)$の予測値の期待値は、
$f^*(s, t)$ となる。 - $D_1$と$D_2$が同じであった場合、学習されたモデルによるデータ$(s, t)$の予測値の期待値は、
$f^*(s, t) - \frac{1}{n-1} c_2 (t - \frac{1}{2} )$ となる。
(Threorem1の主張をまとめなおしたもの。なお、この記事では、論文中に出てくる微小な項である $O(1/2^{n})$ や、データが極めて偏った場合を除外する意味を持つAを省略する)
つまり、1本目と2本目の木の作成で同じデータセットを使うことにより、予測値の期待値に${1}/{(n-1)}$ に比例する偏りが発生する。 この偏りは、1本目と2本目の木で独立したデータを使って学習した場合には発生しない。
なお、prediction shiftの影響を受けないよう、CatBoostではデータ数が少ない場合にはordered boostingというアルゴリズムを使用するようになっている。
証明とポイント
このThreorem1の証明はそこそこの長さがあり、Appendicesの A Proof of Threorem 1に記述されている。
ポイント1
まず、この前提でデータセットが生成されていたとして、モデルを学習させたときにできる木のウェイトを求める。
1本目の木では、特徴量$s$を元に分岐が行われる。
- 特徴量 $s=1$ であるデータの目的変数の平均は、$c_1 + c_2\xi_{11} / (\xi_{10} +\xi_{11})$
- 特徴量 $s=0$ であるデータの目的変数の平均は、$c_2\xi_{01} / (\xi_{00} +\xi_{01})$
であり、目的変数の平均がその葉のウェイトとなるため、上記をまとめて、
データ $(s, t)$ に適用されるウェイト $h^{1}(s, t) = c_1 + c_2 \xi_{s1}/(\xi_{s0}+\xi_{s1})$ と表される。(論文11Pの式(7) )
2本目の木では、特徴量$t$を元に分岐が行われる。目的変数から1本目の木の予測値を差し引いた残差の平均がその葉のウェイトになる。
データ $(s, t)$ に適用されるウェイト $h^{2}(s,t)$ は、$t=0, t=1$それぞれにおいて、目的変数から1本目の木の予測値を差し引いた平均を計算し展開すると、
$t=0$のとき、 $$-c_2\left(\frac{\xi_{00}\xi_{01}}{(\xi_{00}+\xi_{01})(\xi_{00}+\xi_{10})} + \frac{\xi_{10}\xi_{11}}{(\xi_{10}+\xi_{11})(\xi_{00}+\xi_{10})}\right)$$
$t=1$のとき、 $$ c_2\left ( \frac{\xi_{00}\xi_{01}}{(\xi_{00}+\xi_{01})(\xi_{01}+\xi_{11})} + \frac{\xi_{10}\xi_{11}}{(\xi_{10}+\xi_{11})(\xi_{01}+\xi_{11})} \right ) $$
となる。(論文14Pの前半)
ポイント2
$D_1$, $D_2$に同じデータセットを使った場合の$h^{1}(s,t)+h^{2}(s,t)$ の期待値に偏りがあることを示す。
- $h^1(s,t) + h^2(s,t)$ の期待値は、
$f^*(s,t) - \frac{1}{n-1} c_2 \left(t-\frac{1}{2}\right) = c_1 s + c_2 t - \frac{1}{n-1} c_2 \left(t-\frac{1}{2}\right) $ である。
これは以下の $h^1(s,t), h^2(s,t)$ の期待値の和として導かれる。 - $h^1(s,t)$ の期待値は、$c_1 s + \frac{c_2}{2}$ である。
(Proposition1参照。特にこの時点で偏りはない) - $h^2(s,t)$ の期待値は、$\ (2t - 1) \frac{c_2}{2} \left(1 - \frac{1}{n-1}\right)$ である。
つまり、
t=0のとき、 $\ - \frac{c_2}{2} \left(1 - \frac{1}{n-1}\right)$
t=1のとき、 $\ \frac{c_2}{2} \left(1 - \frac{1}{n-1}\right)$
である。(Proposition3のProof参照。 この$h^2(s,t)$の期待値に偏りがある。)
ここで、$h^1(s,t)$ の期待値の計算は特に難しくないが、$h^2(s,t)$ の期待値の計算はやや難しい。
対称性より、 $$\frac{\xi_{00}\xi_{01}}{(\xi_{00}+\xi_{01})(\xi_{00}+\xi_{10})}$$ のみ考えれば良く、他の項にも同様に適用できる。
この項の期待値を計算すると、$\frac{1}{4} \left(1 - \frac{1}{n-1}\right)$ となり、もう一つの項も同じ値のため2を乗じ、さらに係数$-c_2$もしくは$c_2$を乗じたものが$h^2(s,t)$となる。
この項の期待値が$\frac{1}{4}$ であれば偏りはないのだが、そうでなく $\frac{1}{4} \left(1 - \frac{1}{n-1}\right)$ となっていることがポイントで、この部分が偏りの発生源といえるだろう。
この計算はLemma3に記述されているとおり煩雑だが、分子である $\xi_{00}, \xi_{01}$ と分母が独立でなく、分子の値が大きくなるときほど分母が大きくなりやすい関係性にあるため、「フラットな」期待値よりも少し小さくなる、と感覚的に理解できる。
Unityでゲームを作ってみた(その2)+ゲームレビュー
Unityで2作目のゲームを試作しました。まぁまぁ満足というか、Unity初心者としては十分なデキになったと思います。
Unityのゲーム試作2作目できた。ドミニオン+クッキークリッカーみたいな感じ。 pic.twitter.com/9xr5P2CNCv
— threecourse (@threecourse) 2020年5月10日
以下のサイトで公開しています。
ドミニオン(ゲーム紹介:ドミニオン / Dominion - ボードゲーム紹介)のようにカードを引いて回していく感覚と、クッキークリッカー(http://orteil.dashnet.org/cookieclicker/) のように何も考えずどんどん強くなっていくような感覚を出してみました。 最小限のゲーム性でカードゲームっぽいものを作ってみようと思ったのですが、なんだかんだで実装は膨らんで行きますね。
ゲームプログラミングのポイント?
Unityでゲームを作るにあたって学んだポイント
- ゲームのロジックや状態の管理は、GameManager、CharacterManagerといったシングルトンのManagerクラスを作って管理する
- キャラクタや敵といったインスタンスは、Character、EnemyといったMonoBeheviorを継承したスクリプトを作ってGameObjectにアタッチする
UIの反映は、定期的に読み込まれるUpdate関数で毎回UI要素を書き換えに行くのが楽な気がしてきた(パフォーマンスを気にしなければ)。イベントベースで制御する方法もあるが、いちいちイベントを宣言したり登録したりするのが面倒くさい。
コルーチンというものがあり、これによりメインの流れとは別に処理の流れを作ることができる。 敵を倒したときにアニメーションさせて1秒待って消す、と言った処理は、コルーチンで処理するのが基本らしい。
DOTweenといったアセットを使うと、いい感じの慣性の動きをつけることができて便利。
ビューとモデルの分離
カードを使うとき、「手札からカードを論理的に削除 ⇒ カード使用のエフェクトをかけて一定時間後にGameObjectをDestroy」という流れになる。ちゃんとビューとモデルを意識して分けないと訳が分からなくなるが、完全に分離できるわけではない。例えば、カード使用のエフェクトが発動する前にカードのドローが行われると不自然になるため。
もともとはリアルタイムのゲームを作るのは難しいのかと思っていたが、こういうことを考えるとターンベースより逆に作りやすいのかなと思った。
手札の表示
こんな感じの制御をすることで、いい感じにゲームっぽく手札の表示ができたりする
- カード枚数と選択中のカード(マウス位置でフォーカスされているカード)に応じて、それぞれのカードのあるべき位置を決める。
- 現在選択中のカードは特別扱いし、ちょっと大きくした上で最前面に出すようにする
- カードのあるべき位置が変わるときは、DOTweenで動きをつけていい感じに移動させる
- 結構大変だったのが、「カードが選択される⇒カードの位置が変わる⇒マウスを動かしていないのに違うカードが選択される⇒また位置が変わる」となって非常にうざい問題への対処。結局、カードの選択を一度行ったら一定時間は他のカードの選択をしない制御とすると解決した。
ゲームレビュー
家にいる時間も増えたのでいろいろゲームを遊んでみました。
ラトロポリス
デッキ構築タワーディフェンスみたいな感じ。最初はクソゲーだと思った。「少しでも戦力が足りないと一気に戦線が崩壊する&どう足りないのか分からないため納得感がない」のがひどい。タワーディフェンスだと通常はタワーは攻撃されないですが、このゲームはキャラクタが敵に攻撃されて倒れるので、戦線崩壊の度合いがたぶん激しくなるんですよね・・
余裕をもって戦力を強化すると結構進めるので、理解してくると結構楽しかった。ルールの枠外を突くようなコンボ(カードを強化する能力を使いまわすとか、一度使うと消えるカードをコピーするとか)じゃないと勝てないっぽく大味ですが。
Iratus Lord of the Dead
Darkest Dungeonの敵側としてプレイするようなローグライクRPG。 雰囲気はとても良いのだが・・ゲームとしては劣化Darkest Dungeonのような気がします。
Steam:Iratus: Lord of the Deadstore.steampowered.com
DIMENSION REIGN
ローグライク+デッキ構築ゲーかと思いきゃそうではなく、デッキ構築ではなくスキルとレリック(能力を付与する宝物)を上手く構成して敵を倒していくゲーム。 敵を倒す順序を組み立ててずっと俺のターンが楽しめる良ゲー。
グノーシア
ノベルゲー+人狼ゲーム。繰り返して人狼ゲーを遊んでいく中でストーリーが進んでいく。キャラクタの良さとゲームシステムの新しさからなる素晴らしいゲーム。
ランダム性を上手くシステムに織り込んでいて、こうやって人狼をゲームにすることができるのか、という驚きがあった。
くらいの紹介にしようと思ってましたが、クリア直前の展開が良すぎて名作になりました。みんなやろう。