Google Cloud Runで想定外の課金が発生した話

ヒューリスティックコンのパラメータチューニングをGCPでやる - threecourse’s blogを試している中で、Google Cloud Run（以下、Cloud Run）で1万円使ってしまったので、 同じようなことを試す人がもしいたら（あまりいないと思いますが・・）ということで注意喚起のためにもメモ。

やったこと

  • Cloud Run内で、最適化プログラムを動かす
  • 1回の計算は4秒で、その中で5万行くらい標準エラーに出すようにしていた
    （コンペ用のプログラムで、雑多な情報を提出時に無視される標準エラーに出すようにしていた）
  • 計算をトータルで2万回くらい投げた

何が起こったか

対策

教訓

  • この程度で済んで良かったが、下手すると桁が違ってた可能性があるので怖い
  • 他の人がやっていないことをやるとき、サービスをよくあるユースケースと違うことに使うときには気をつけましょう
  • 課金のアラーム設定や見積もり、内訳をちゃんと確認しましょう（見積もりもちょっと遅れてやってくるので難しい部分はあるのだが・・）

ヒューリスティックコンのパラメータチューニングを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倍程度にすると良さそう。
  • チューニングを繰り返すと微妙なパラメータがベストとなることもあり、「最適なパラメータチューニング」となっているかは分からない。 引き続き要検討だが、試行回数を増やすのが良いような気もする。

構成

全体の流れ

パラメータチューニングの全体の流れは、以下のようになります。

  1. Optunaの初期化を行う
  2. Google Cloud Storage（以下GCS）にテストケースとバイナリをアップロードする
  3. Optunaでの並列パラメータチューニングの実行を開始する
  4. 各パラメータの試行では、
    ・10個のテストケースを実行し、その結果の平均をスコアにする
    ・10個のテストケースの実行は、2ケースごとのバッチにしてCloud Runに計算依頼を飛ばすことで行う
    ・Cloud Runの計算において、GCSからテストケースとバイナリをダウンロードする
    ・10並列で行う（つまり、10並列 x 5バッチ = 50個の計算依頼が飛んでいる状況になる）
  5. パラメータの試行100ケースが全て終わると、最も良いパラメータを選んで終了する

最適化プログラムの構造

パラメータを受け取り、計算結果を返せるように、最適化プログラムを組んでおく必要があります。

  • 引数として「名前」「テストケース名」「各パラメータ」を受け取り、
    結果である「スコア」や「焼きなましの計算回数/更新回数」などの補助情報をjsonファイルなどに出力する仕組みにします。
  • こうすることで、外部からPythonなどを用いて、最適化プログラムを並列で叩いてその結果を取得できるようになります。
  • このまま提出するとWrong Answerになってしまうので、コンパイル定数などを用いて手元でコンパイルしたときと提出したときの挙動を変える必要があります。

Optuna

Optunaは、改めて非常に使いやすいツールですね。

その他、以下の機能が便利でした。

Cloud RunにデプロイするDockerイメージ

Cloud Runは、リクエストを処理している間のみ課金され、また自動的にスケールしてくれるという素晴らしいサービスです。

Cloud Runを使うためには、httpリクエストを受け取り、レスポンスを返すDockerイメージを作成する必要があります。
今回は、flaskでhttpリクエストの処理を行い、その中でC#の最適化プログラムを動かすため、C#とPython（Anaconda）を動かせる構成にしています。

Dockerイメージ内の処理は、以下のような流れになります。

  1. httpリクエストのデータとして、「ランの名前」「計算対象となるケース名のリスト」「パラメータ」を受け取る
  2. 「ランの名前」を基にGCSからテストケースとバイナリをダウンロードする
  3. 「計算対象となるケース名のリスト」の各ケースを「パラメータ」を指定して実行し、結果を取得する
  4. 結果のリストをレスポンスとして返す

Cloud Runの設定

最大100までインスタンスを立ち上げ、インスタンス内の同時実行数は1、実行時間制限は（一応）15分、インスタンスはCPU1個、メモリ512MBという設定にしました。

同時実行数を1にすることで、複数の計算で同時にCPUを使うことを防ぎ、正しく計測できるようにしています。 たまになぜか計算回数が半分くらいになることがあるようですが、概ね計測に問題は無さそうです。 もう少し攻めた設定にしても良いかもしれません。

なお、インスタンスがスケーリングしている最中には、429や500といったレスポンスを返すことがあるので、それらのときには少し待って再度リクエストを投げるようにする必要があります。

Cloud Runの料金はそれほどでもないのですが、ログには注意が必要です。 標準出力がログとして飛んでいってしまうので、最適化プログラムで一定間隔ごとに焼きなましの温度などを出力するようにしていると、1回のチューニングで数十GBのログが飛んでいくことがあるようです（怖）。GCPのログ取り込みで除外設定を作成するか、最適化プログラムを叩くときに標準出力・標準エラーをDEVNULLなどで抑止する必要があります。

追記：
threecourse.hatenablog.com

継続的インテグレーションについてのメモ

参考資料

少し古いが、テストの分類など以下のスライドがよくまとまっている。

www.slideshare.net

また、CircleCIでチュートリアル＋αをやりました。 circleci.com

（CircleCIのドキュメント、Orbs・ジョブ・アーティファクトといった用語の具体例がなかなか出てこないので、初心者には分かりづらいような・・）

その他、以下の書籍を参考にしました。

継続的インテグレーションとは？

定義は上記文献や継続的インテグレーション - Wikipediaを参照。

私の理解では、常に「クリーン」な状態を保ちながら開発するために、ソースコードのバージョン管理とテスト・ビルド・デプロイを自動化して接続すること。CIと略記される。

CIサーバ

継続的インテグレーションを行うために、以下のCIサーバと呼ばれるサービスがある。

  • CIrcle CI
  • Google Cloud Build
  • GitHub Actions
  • JenkinsやTravisCIなど

CIサーバでは、以下の設定を行うことになる。

  • ビルド、テストといったジョブを定義する
    設定ファイルはyamlなどで記述する
  • トリガーを指定する
    Pushされたとき、プルリクエストが送られたときなど、ジョブを起動するトリガーを指定する
    APIを叩くなどで手動実行もできる
  • GitHubやBitBucketなどと連携設定をする

CIサーバは、以下の機能を持つ。

  • トリガーとなるイベントが発生すると、上記のジョブを実行する
    ジョブは、docker imageを用いて行われる。また、並列や依存関係を考慮して実行が行われる
  • テストに失敗するとそのジョブは失敗する。
  • アーティファクトと呼ばれるビルド時生成物を保存する仕組みがある
    アーティファクトの例は、テストのカバレッジやビルドされたバイナリなど
  • ジョブの状況、テスト結果やアーティファクトをWeb画面から見ることができる

雑感

  • ユニットテストだけで良いのなら、CIサーバを用いて綺麗な流れで開発できそう。
    結局は、時間や手間のかかるテストをどう扱うかが問題になる。
  • 上記書籍などでもその議論がなされている。時間などでテストの種類を階層化し、時間のかかるテストはコミットごとに行うのではなく定期実行する、といったアプローチになる
  • 開発においては、プルリクエストを送る前に手元でテストしたい気もする。それらを考えると、トリガーとか複雑なワークフローよりも、任意のタイミングで任意のジョブを実行して、結果をいい感じに管理できるようにしたい

競技プログラミングの解説に必要な要素

AtCoderの解説についての議論があったので、考えたことを書いてみました。 最近あんまりratedに参加していない中、外からなんやかんや言うのはあれなのですが、何かの足しになれば。
（私のアカウントは https://atcoder.jp/users/threecourse です）

解説に必要な要素

解説を構成する要素は以下だと考えています。

  1. 解法の実装の概要
  2. 解法の正当性の証明
  3. 解法をどうやって思いつくか

この中で核となるのは、「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）が分かりづらい場合でも、動画もありますし、コミュニティの力でどこかに分かりやすい解説が落ちているため、困ることはあまり無いですが。

フロントエンド何もわからない（その３）

しばらく経つといろいろ忘れますが、覚え直すと少しずつレベルアップしている感じはありますね。 今回は、グリッド上に情報を表示するGUIを作ってみたかったため、8クイーン問題を題材にしました。

WebページはGitHub Pagesを使って公開しています。

threecourse.github.io

コードはこちらです。

github.com

Nuxt.jsの利用

Vue.jsというjavascriptのフレームワークに、さらにいろいろ盛り込んだフレームワークがNuxt.jsです。

ja.nuxtjs.org

データを保持するVuexが組み込まれているなどの利点があり、ディレクトリ構成などのお作法を統一する意味でも、Vueを使うなら最初からNuxtにしてしまった方が早いかなと思いました。 シンプルな処理ならNuxtのみで良く、 必要に応じてバックエンドサーバを立てて計算はそこに投げるような構成にすると良いでしょう。

（参考）Nuxt.jsビギナーズガイド https://www.amazon.co.jp/dp/B07J5434JB

Bulmaの利用

Bulmaは、javascriptが組み込まれておらず、比較的シンプルなcssフレームワークです。何もcssフレームワークを入れない場合と比較すると、だいぶ見た目がよくなります。
(Nuxt.jsのデフォルトのインストール方法では最新版が入るとは限らないので、npmで自分で入れる方が良いのかも） 　

bulma.io

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にランのリクエストを投げる

要件

１．ランを投げたい

ローカルのPCから、python run.py --param1 10 のように書いたらランがサーバ上で実行され、終わったら結果をどこかに保存してくれると嬉しいですね。 ローカルのPCで計算が動いていると、どうしても集中できなくなるので。

以下の２つのユースケースを想定します。

  1. 10分〜数時間以上かかるようなラン。Kaggleの画像系コンペの計算を想定。
  2. 数十秒〜数分のラン。マラソンマッチを想定。
    （実際は多数ケースを流すので、もっと時間がかかってa.と同じ扱いで良いのかもしれない）

前者の場合だと、起動までに数分かかっても問題ないでしょう。 一方で後者の場合だと、数秒〜数十秒で起動してほしい気持ちがあります。

２．dockerを使いたい

昨今はdockerを使うメリットが大きくなってきているように思います。 環境を持ち運びできるのはさまざまな場面で便利で、 例えばローカルPCでは計算量が足りず、クラウド上のサービスに載せたくなったときもdockerで動くようにしてあると比較的スムーズです。

３．コードとの紐付けを行いたい

コードを変更したらスコアが下がったので、前のスコアの良かったランと比較してデバッグしたい、といったときに前のランのコードを参照できないとつらいです。 なので、ランにはgitのcommit idなどを紐付けしておき、ラン間のコードの差分を見れるようにしておきたいです。

ソリューション

１．構成

まず、適当な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. その他の選択肢

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で行います。

3. 流れ

流れをまとめると、 以下のようになります。

Compute Engineのインスタンスを使う場合：

  1. フォルダcodeを固めて送ることで、コードをGCSに送付する
  2. Compute Engineインスタンスでコンテナを起動する
  3. コードをGCSから取得する
  4. 計算を実行する
  5. 計算結果をGCSにアップロードする
  6. Compute Engineインスタンスを自ら終了させる

Cloud Run + Cloud Tasksを使う場合：

  1. フォルダcodeを固めて送ることで、コードをGCSに送付する
  2. Cloud Taskを通してCloud Runにhttpリクエストを送る
  3. Cloud Runはhttpリクエストを受けて計算処理を実行する
  4. コードをGCSから取得する
  5. 計算を実行する
  6. 計算結果を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

追記：
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}$ と分母が独立でなく、分子の値が大きくなるときほど分母が大きくなりやすい関係性にあるため、「フラットな」期待値よりも少し小さくなる、と感覚的に理解できる。