2023-06-18

AWS API GatewayとLambda 関数 URL（とChatGPT）

AWS Lambdaにデプロイした関数を外部からHTTPリクエストでトリガーしたいときどうすればいいのか、ChatGPTに聞いてみた。

AWSの公式ドキュメントにもAPI Gatewayを使用してLambdaのエンドポイントを得る方法が書かれている。

docs.aws.amazon.com

Lambdaの使い方について書かれたインターネットの記事にもAPI Gatewayを使ってエンドポイントを発行する方法を紹介しているものが多くある。しかし、実はこの方法は必ずしもベストプラクティスとは限らない。そのことについてのメモのようなもの。

Lambdaのタイムアウトについて

AWS Lambdaではデプロイした関数にタイムアウトを設定することができ、これは最大で15分まで拡張できる。しかし、API Gatewayの方にもタイムアウト時間の設定があり、こちらの最大値は29秒である。

つまり、15分以内に処理が終わる関数であればLambda上で実行できるはずなのに、API Gatewayが30秒時点でタイムアウトを返してしまうため時間をフルに使えないといった現象が起こる。この現象についてChatGPTに質問すると、AWS Step Functionsを使ってLambda関数を非同期に実行し、クライアントが定期的に問い合わせをしながら完了を待つという構成を提案される。 GhatGPTではなくGoogleで検索しても同様の方法を紹介した記事が複数Hitする。しかし、API Gatewayのタイムアウト制限を回避するためだけにこんなに煩雑なことをしないといけないとは面倒だ。

Lambda関数URLについて

実はLambda関数URLという機能を使えばLambdaから直接エンドポイントを発行できるため、そもそもAPI Gatewayを通すことなくLambda関数を外部からトリガーすることができる。よって、Step Functionsなどを用いた複雑な構成を用いずとも15分をフルに使うことができる。認証周りの設定などAPI Gatewayに劣る部分もあるが、こちらで充分な場合も多い。

ではなぜChatGPTがAPI Gatewayを用いた方法を提案してくるかというと、単純にLambda関数URLが2022年4月にリリースされた新しい機能だからである。 GPT-4は2021年9月までのデータを用いて学習しているため、ChatGPTはLambda関数URLの存在をそもそも知らず、古い情報に基づいて当時のベストプラクティスを提案してきていたということになる。しかしこれはこれで正しい方法ではあるので、教えてもらったとおりに検索するとたくさんの記事（これらの多くは古い記事）がHitする。

古い情報には気をつけよう

普段ChatGPTに何かを質問するときにはハルシネーションを見抜くことに多くの注意を払っているため、教えられたことが事実であると確認できれば安心してしまい、その時点で情報を鵜呑みにしてしまう傾向にある気がした。質問したことが不変の事実であれば問題ないが、エンジニアリングに関することなど時間とともに変化する可能性のあることを質問するときには注意しないといけないなと思った（小並感）

2023-06-04

SECCON Beginners CTF 2023に初心者チームで出た

経緯

いつもボードゲームや謎解きをして遊んでいるグループでSECCON Beginners CTF 2023にチームで参加する人を募集していたので参加してみた。 CTF初心者チームだったが、全員（元）競技プログラマなのでチームメイトが強かった。~~ちなみに調べたら誰も今年AtCoderに出てなかった。~~

僕はreversingカテゴリの問題をずっとやっていた。バイナリの知識がほとんどなく、調べながらやっていたら自力で2(+1)問解けたので、考えたことを書く。

Half

問題概要

バイナリファイルが与えられる。

解法

とりあえずバイナリエディタが必要な雰囲気を感じたのでStirlingをダウンロードする。

与えられたバイナリをStirlingで見ると、テキストエリアにflagが表示されているのでこれを入力すればAC。

この問題はやほーbbさんが僕より先に解いていた。

ちなみにバイナリのテキストから可読部分を抽出するにはstringsコマンドを使えばいいということを後の問題を解きながら知った。

$ strings half
(略)
Enter the FLAG:
%99s%*[^
Invalid FLAG
ctf4b{ge4_t0_kn0w_the
_bin4ry_fi1e_with_s4ring3}
Correct!
(略)

Three

問題概要

バイナリファイルが与えられる。

解法

さっきと同じ方法でやろうとすると、flagが明示的にtextとして保存されていないことがわかる。この時点で僕の知識を超えているが、せっかくなので色々調べていた。

とりあえずStirlingでテキスト部分を眺めていると"libc.so.6"とか"GLIBC"とかいう文字列が見えるので、C言語のコードをコンパイルした実行ファイルだということに気づく（さっきの問題もそうだったのだが気づいてなかった）。実行してみると、標準入力で入れたflagが正解かどうかを判定してくれるプログラムのようだった。

あらかじめ買っておいたセキュリティコンテストチャレンジブックを読んでいたらバイナリ解析に使えるいろいろなツールが載っていたので、試してみることにした。

最初にIDA Free版で逆アセンブルをしてみた。validate_flagという関数があることは分かったが、アセンブリを1時間くらい眺めていても結局flagの正誤判定をどうやっているのかが分からなかった。

チームのdiscordを見ると、drafearさんがGhidraで逆コンパイルができるらしいという情報を（コンテスト前に）貼ってくれていたので、Ghidraを入れる（ここでJDKのバージョンを合わせるのに若干時間がかかる）。与えられたバイナリをGhidraで逆コンパイルしてみると、validate_flagの中身をコード形式で見ることができた。

undefined8 validate_flag(char *param_1)

{
  char cVar1;
  size_t sVar2;
  undefined8 uVar3;
  int local_c;
  
  sVar2 = strlen(param_1);
  if (sVar2 == 0x31) {
    for (local_c = 0; local_c < 0x31; local_c = local_c + 1) {
      if (local_c % 3 == 0) {
        cVar1 = (char)*(undefined4 *)(flag_0 + (long)(local_c / 3) * 4);
      }
      else if (local_c % 3 == 1) {
        cVar1 = (char)*(undefined4 *)(flag_1 + (long)(local_c / 3) * 4);
      }
      else {
        cVar1 = (char)*(undefined4 *)(flag_2 + (long)(local_c / 3) * 4);
      }
      if (cVar1 != param_1[local_c]) {
        puts("Invalid FLAG");
        return 1;
      }
    }
    puts("Correct!");
    uVar3 = 0;
  }
  else {
    puts("Invalid FLAG");
    uVar3 = 1;
  }
  return uVar3;
}

これによると、flag_0, flag_1, flag_2という3つの配列に入った文字を1文字ずつ繋ぎ合わせてflagを作っていることがわかった。それぞれの配列に入っている値を見ながら頑張ると

ctf4b{c4n_y0u_ab1e_t0_und0_t4e_t4ree_sp1it_f14g3}

という文字列が得られるので、これを入力すればAC。

ちなみにこの問題だけで2時間くらいかかっていた。

Poker

問題概要

バイナリファイルが与えられる。

解法

与えられたバイナリを実行してみると、インディアンポーカーの勝敗を予想するゲームが始まる。1,2のいずれかの値を入力すると1Pと2Pのどちらが勝ったか（引き分けもある）が表示され、当たっていればポイントがもらえる。連続で当て続ければポイントが増えていくが、1回でも外すと最初からになるようだった。

問題ページのフレーバーテキストには「みんなでポーカーで遊ぼう！点数をたくさん獲得するとフラグがもらえるみたい！でもこのバイナリファイル、動かしてみると...？実行しながら中身が確認できる専門のツールを使ってみよう！」とあるので、点数をいっぱい獲得すればいいんだなということがわかる。

とりあえずIDAとGhidraで逆アセンブル、逆コンパイルをしてみたが、眺めていてもよくわからない。

この時点で「予想を入力する前から内部で勝者が決まっていて、実行しながら変数を参照できるようなツールを使えばカンニングができる」という問題なのではないかと予想していて、バイナリを実行しながらメモリの状態を見られるようなツールを探していたがうまくいかなかった（Windowsマシンを使っていて、バイナリをWSL2で実行していたのだが、こういう状況でメモリの状態を見られるツールがあるのかどうか結局よくわかっていない。）

疲れたので、この時点で一回諦めて寝た。

起きてからもよくわからなかったので、やけくそになってポーカーゲームで同じ数字を連打して遊んでいたらやたらと点数が取れることに気づく。この時点で、勝敗が時間で決まっているんじゃないかという予想が立つ。そこで本に載っていたltraceコマンドで見ながらゲームを実行してみると、UNIX時間（秒）が勝敗のシードとして使われていそうだということがわかった。

1秒以内なら勝敗が同じになることが分かったので、ファイルから標準入力するコマンドを使って1を大量に流し込んでみたところ、簡単に点数を増やすことができた。しかし何回やっても98点を取った時点でプログラムが落ちてしまい、99点以上は一回も取れなかった。

このことを頭に入れた状態でもう一度逆コンパイルされたコードを見てみると、こんな関数を見つけた。

undefined8 FUN_00102262(void)

{
  undefined4 uVar1;
  int local_10;
  int local_c;
  
  local_c = 0;
  FUN_001021c3();
  local_10 = 0;
  while( true ) {
    if (0x62 < local_10) {
      return 0;
    }
    FUN_00102222(local_c);
    uVar1 = FUN_00102179();
    local_c = FUN_00101fb7(local_c,uVar1);
    if (99 < local_c) break;
    local_10 = local_10 + 1;
  }
  FUN_001011a0();
  return 0;
}

これによると、99点を取ればflagがもらえるが、99回入力すると強制的にreturn 0;する処理が入っていることが分かった。ここでreturnするのをやめさせることができれば99点が取れそうだ。よって、Stirlingを使って0x62（98）を0x63（99）に書き換えて実行してみたところ、ゲームが終了することなくflagをゲットできた。

[?] Enter 1 or 2: [+] Player 1 wins! You got score!

================
| Score :  98  |
================

[?] Enter 1 or 2: [+] Player 1 wins! You got score!

================
| Score :  99  |
================

[?] Enter 1 or 2: [+] Player 1 wins! You got score!
[!] You got a FLAG! ctf4b{4ll_w3_h4v3_70_d3cide_1s_wh4t_t0_d0_w1th_7he_71m3_7h47_i5_g1v3n_u5}

結果

チームとしては、24位/778チームだった。これはチームメイトが協力して難しい問題を解いていたためで、僕はあまり関係なく自分の興味あることをやっていたという感じだった。CTFをやったのは初めてだったけど、かなり面白いと感じた。競技プログラミングを始めたときの感覚に近いかもしれない。

これからもちょっとずつ過去問を解いたりしてみようかな、という気持ちになった。

2023-04-09

新ジャンル：英会話サーモンラン

Speakを始めてから1か月以上2か月未満が経った。

www.speak.com

英語について

だいたいの日本人は英語を話せるようになりたいと思うが、僕もそう思っている。

僕は高校入学直後から1年生の終わりごろまで勉強というものを完全に諦めていた時期があり、英語ももちろん嫌いだった。具体的には1年生の間に受けた英語Ⅰと英文法の定期テストほぼすべてで赤点を取ったり、河合塾の全国模試で英語の偏差値が35だったりした。 2年生に上がる際に思い付きで理系選択をしたので受験のために多少勉強するようになったが、それでも英語にはずっと苦手意識があった。

大学では物理学科に入学したので英語が苦手とは言っていられなくなり、英語に慣れるために学部2年のころに「海外ドラマやアニメなどを1日1話（30分くらい）観る」という日課を始めた。 PowerDVDというソフトにはDVDを英語音声で流しながら英語字幕と日本語字幕を同時に表示するという機能があるので、それを使ってTSUTAYAやGEOで借りたDVDを観ていた。これは3年くらい続いたので、500時間くらいは海外の映像作品を見た計算になる。結果としてリーディングやリスニングには割と効果があったのと、たくさん聞いたことで英語を読むときの発音もかなり改善されたと思う。ただ、聞くだけで一切話していないので、スピーキングの能力は全く上がらなかった（当たり前）。誰かスピーキングの練習相手になってくれんかな～と思いながら最近まで過ごしていた。

Speakについて

Speakは英会話の練習ができるアプリである。 AIと話せるということを売りにしていて、AI関連のトピックとして2か月ほど前にTwitterで若干話題になった。 Speakは有料アプリだが1週間のトライアル期間があり、その間は無料で使うことができる。最近はずっと自宅にいるので、作業中ずっとAIと話してたら英会話がうまくなるんじゃないかと思い、Speakを始めてみることにした。

結果的には、作業中にAIと話すというのはあまりうまくいかなかった。理由としては

やりとり一回ごとに画面をタップする必要があるので、作業ができない
AIの精度が微妙
英語で話すのは日本語で話すのと違って結構頭を使うので、作業に割くリソースがない

など。

AIと話すのは断念したが、Speakはもともと英語学習アプリなのでAIと会話する以外のコンテンツもある。形式はいろいろあるが、聞こえてきた英語をそのまま発音したり、聞こえてきた日本語を英語に直して発音したりするオーソドックスなもののほかに、録音された講師の音声を使ってまるで通話しているかのように英会話のレッスンを受けられるといったものもある。どれもアプリの音声認識機能を使っているので、こちらの発言を聞いて正誤判定もしてくれる。音声認識だけで進行するので、画面のタップも必要ない。

これらのコンテンツはかなり気に入っているのだが、英会話表現を身に着けるには繰り返しが重要なため、同じ表現を何度も出題されたりすると退屈になることもある。 Speakをやってる間は頭を使って、耳も使って、口も使う。なにか別のものと並行できないだろうか……？

英会話サーモンランがある生活

結論から言うと、Speakとサーモンランは同時に行うことが可能である。

www.nintendo.co.jp

なぜなら、サーモンランは口を使わないし、頭も使わないからである。サーモンランをプレイしているとまるで頭を使っているかのような錯覚に襲われることがあるが、実際はほとんど反射でプレイしている（もう少し正確に言うと、脳の言語野を使わないということだと思うけど）。逆にサーモンランでは目を使い、手を使うが、これらは英会話では使わない。耳だけは役割が被ってしまうが、サーモンランで聞こえてくる音は言語として処理する必要はないため、サーモンランの音のせいで英会話に支障が出るということはほぼないようだった。

サーモンランは楽しいので、英会話の繰り返しによる退屈さをカバーできる。逆に英会話は有益なので、サーモンランの無益さをカバーできる。僕は今のところこの方法で1日1～2時間ほど英語を勉強することに成功している。 Speakのサブスクは1年間なので、1年続けられれば少しはスピーキングがうまくなるかもしれない。

みなさんも英会話サーモンランにチャレンジしてみてはいかがだろうか。

2023-03-21

Atcoder お誕生日コンテストX - 「この問題はほんとうにひどい問題であるため，できれば先に他の問題のほうをお楽しみいただければと思っておりまして，ですので他の問題を通し終えて暇になり，かつその暇を」をCNNで解く

問題

atcoder.jp

問題概要

括弧を含む四則演算の式が与えられるので、答えを整数で出力する。ただし、式は画像で与えられる。

式の画像は、Courier Primeというフォントの各文字に対して回転、縦横の拡大（縮小）、せん断変形、平行移動を行って生成される。さらに、確率 $P=0.05$ で画素を反転させるノイズが生成される。

この問題について

2014年2月に開催されたJAPLJさんのお誕生日コンテストで出題された問題。

AtCoderで開催されるお誕生日コンテストではいわゆるギャグ寄りの問題が出題される傾向にある（というよりこのコンテストが原点？）が、この問題はその中でもかなり強いギャグである。

僕がこの問題を知ったのは競プロを始めてしばらく経った2018年ごろだったが、かなり印象に残っている問題だった（「解けるわけないのになぜかACしている人がいる」と思っていた）。

最近ニューラルネットワークをC++に埋め込むことについて考えていたときにこの問題のことを思い出し、チャレンジしてみることにした。

制約が当時と異なる点について

問題の制約は問題文中に書かれているが、そのなかに「AtCoder で送信できるソースコードは UTF-8 で 60,000 文字以下なので，文字数制限に注意してプログラムを書くこと．」とある。しかし、現在のAtCoderにおけるコード長制限は512KiBであり、これは1バイト文字なら500000文字以上に相当する。今回は、結果的に当時の制約のなかで解くことができた。

解法

問題設定

この問題は「画像データから数字と記号の情報を取り出す」「得られた式をパースして計算する」という2段階に分けられる。後者は競プロでは構文解析の超典型問題なので難しい部分は前者だが、前者は前者で機械学習における典型データセットであるMNISTと非常によく似ている。

記号が6種類あるのでMNISTよりクラスの数が少し増えているのと、満点である500点を取るためにはモデルの正答率100%が必要である。とはいえMNISTにはどう考えてもラベル付けをミスっているとしか思えないデータや既存の数字のどれにも似ていないデータなどが含まれているため、それに比べると正答率100%は目指しやすいと考えられる。

学習データセットの生成

学習はPythonで行うので、Pillowを使ってデータセットを生成した。

実際にクエリとして与えられる画像と同じように、Courier Primeの各文字に対してランダムに回転、拡縮、せん断変形、平行移動を行っていく（回転角は少し多めに±20°まで取ってみた）。推論の際にはクエリ画像にメジアンフィルタを適用してノイズを除去するが、その際に文字の形が変わりがちなので、あらかじめ $P=0.05$ でノイズを生成してからメジアンフィルタを適用したものを教師データとして用いた。実際に与えられるクエリ画像では文字が途切れているということはないが、~~面倒なので~~強いモデルを作るために修正は特に行わなかった。データセットは各文字5000枚ずつ生成した。

モデルの作成

学習にはPyTorchを用いた。モデルは以下のように定義した。

class Model(nn.Module):
    def forward(self, x):
        h = F.relu(self.conv1(x))
        h = F.relu(self.conv2(h))
        h = F.relu(self.conv3(h))
        h = self.pool(h)
        h = h.view(-1, 16*6*3)
        h = self.linear1(h)
        o = self.linear2(h)
        return o

    def __init__(self):
        super(Model, self).__init__()
        self.conv1 = nn.Conv2d(in_channels=1, out_channels=4, kernel_size=3, stride=2).to(device)
        self.conv2 = nn.Conv2d(in_channels=4, out_channels=8, kernel_size=3, stride=2).to(device)
        self.conv3 = nn.Conv2d(in_channels=8, out_channels=16, kernel_size=3, stride=1).to(device)
        self.pool = nn.MaxPool2d(kernel_size=(2, 2), stride=(2, 2)).to(device)
        self.linear1 = nn.Linear(in_features=16*6*3, out_features=20).to(device)
        self.linear2 = nn.Linear(in_features=20, out_features=16).to(device)

生成したデータセット80000枚をtrainデータ64000枚とtestデータ16000枚に分割して学習率0.001で200epochほど学習させると、trainデータに対する正答数が64000、testデータに対する正答数が15983となった。accuracyは99.8%だが、データセットはクエリ画像よりも少し難しめのものを生成していることを考えるとまあまあな気がした。学習時間はデスクトップPC（with RTX3080）で10分くらいだった気がする（ちゃんと計ってない）

モデルをC++に移植する

AtCoderではPyTorchは使えないので、推論を行うには別の方法を用いる必要がある（追記：今度の言語アップデートで入るらしい？）。今回は当初のモチベーション通りC++にモデルを埋め込んでみる。

Python側で学習したモデルをエクスポートするとき、パラメータをそのままリスト形式で書き出すという方法もなくはないが、バイナリにパラメータを詰め込むほうが圧倒的に効率がよい。

PyTorchのパラメータはデフォルトでは4バイトの浮動小数点数なので、10000パラメータを埋め込んだバイナリは約40000バイトになる。今回はインポートも自分で書くのでパラメータを自分で決めた順番で並べるだけでよいが、適当な場所にパラメータ数の情報などを整数で挟み込んでおくと読み込み時にずれていないかどうかなどが判断できて便利。

通常の環境であればこのバイナリをファイルとして保存してC++側で読み込むという処理で問題ないが、AtCoderではファイル一枚しか提出できないためモデルを文字列として埋め込む必要がある。今回はバイナリを文字列に変換するためにbase64によるエンコードを用いた。base64では6バイトを1文字で表すため、結局10000パラメータは54000文字程度になる。

    def get_linear_params(self, linear):
        param = struct.pack("<I", linear.weight.nelement())
        for val in linear.weight.data.flatten().tolist():
            param += struct.pack("<f", val)
        param += struct.pack("<I", linear.bias.nelement())
        for val in linear.bias.data.flatten().tolist():
            param += struct.pack("<f", val)
        return param

    def get_conv2d_params(self, conv2d):
        param = struct.pack("<I", conv2d.weight.nelement())
        for val in conv2d.weight.data.flatten().tolist():
            param += struct.pack("<f", val)
        param += struct.pack("<I", conv2d.bias.nelement())
        for val in conv2d.bias.data.flatten().tolist():
            param += struct.pack("<f", val)
        return param

    def get_parameter_string(self):
        # C++モデル用のbase64を出力する
        params = bytes()

        params += self.get_conv2d_params(self.conv1)
        params += self.get_conv2d_params(self.conv2)
        params += self.get_conv2d_params(self.conv3)
        params += self.get_linear_params(self.linear1)
        params += self.get_linear_params(self.linear2)

        return base64.b64encode(params).decode()

次に、C++側でモデルを用意する。 AtCoderで使えるC++の機械学習ライブラリは多分ないので、推論部分を自前で実装していく。線形層を実装するのは比較的簡単だが、畳み込み層の処理を実装するのはかなり面倒くさい。とはいえ、実際にPyTorchで動かした推論処理と比較しながら実装していけばなんとかなった。

C++は適当に書いても充分高速なので、今回のケースであれば愚直な実装でも実行時間にはかなり余裕があった。さらに、モデルのパラメータをインポートするためにbase64のデコードとバイナリの読み込みを追加で実装した。

これで、 $38\times65$ の画像を読み込んで描かれている記号を推論するモデルが用意できた。

残りの部分を書く

本質の部分が実装できたので、あとは残りの部分を書いていく。

ジャッジから与えられるクエリ画像にはノイズがかかっているので、最初に $3\times3$ のメジアンフィルタをかけてノイズを除去する。

作成したモデルは $38\times65$ の画像しか推論できないので、文字の場所を特定して画像を切り出す必要がある。文字は基本的に大きな連結成分になっているので、黒いピクセルがある列が5列以上並んでいれば文字であるとして判断した。各画像を推論すれば文字列の式が得られるので、あとは構文解析を書けば完成。

これを提出してもWAが1～2ケース出る場合があるが、何度か学習をやり直してモデルガチャをすれば数回でACできた（60000文字以内に収めようとした場合。現在のコード長制限をフルで使って大きなモデルを使った場合は一発でACできた。）

提出

atcoder.jp

感想

軽い気持ちで手を付けたら2日くらいかかってしまった（大半はCNNの実装）

昔この問題を競プロとして見たときはタイトルの通り「ほんとうにひどい問題」だと思ったが、ニューラルネット埋め込みの課題として見れば教育的な良問だった。

なんにせよ、昔から気になっていた問題をACできてよかった。

2023-03-10

AlphaTensorのゲームの部分

昨年10月、DeepMindが強化学習を用いて行列の積を従来の手法よりも高速に計算できるアルゴリズムを発見したと発表した。このニュースを見たとき強化学習と新たなアルゴリズムの発見が自分の中で結びつかなかったので、元論文を読んで社内の勉強会で発表した。その内容をこちらにもまとめ直してみる。強化学習をアルゴリズムの発見に適用する過程が特に気になっていたので、その部分に注目した内容になっている。

元論文

Discovering faster matrix multiplication algorithms with reinforcement learning

既存の行列演算アルゴリズム

定義

行列積の愚直な計算方法は、各行と列に対して定義通りに計算していくというものである。

$\displaystyle \left( \begin{array}{rr} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{array} \right) \left( \begin{array}{rr} b_{11} & b_{12} \\ b_{21} & b_{22} \\ \end{array} \right) = \left( \begin{array}{rr} a_{11}b_{11} + a_{12}b_{21} & a_{11}b_{12} + a_{12}b_{22} \\ a_{21}b_{11} + a_{22}b_{21} & a_{21}b_{12} + a_{22}b_{22} \\ \end{array} \right)$

この方法では、 $N\times N$ 行列同士の積を計算するために乗算が $N^3$ 回、加算が $N^2(N-1)$ 回必要となる。この例では $2\times2$ 行列なので、乗算が8回と加算が4回となっている。この方法はどんな大きさの行列にも適用できるから、これよりも遅いアルゴリズムは意味がない。

Strassenのアルゴリズム

定義による計算方法では $2\times2$ 行列の積を求めるために8回の乗算を要したが、これを7回の乗算で計算できる方法がある。それは、以下のようなものである。

$\displaystyle \left( \begin{array}{rr} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{array} \right) \left( \begin{array}{rr} b_{11} & b_{12} \\ b_{21} & b_{22} \\ \end{array} \right) = \left( \begin{array}{cc} p_1 + p_4 - p_5 + p_7 & p_3 + p_5 \\ p_2 + p_4 & p_1 + p_3 - p_2 + p_6 \\ \end{array} \right)$

ここで、

$\displaystyle \begin{align*} p_1 &= (a_{11} + a_{22})(b_{11} + b_{22}) \\ p_2 &= (a_{21} + a_{22})b_{11} \\ p_3 &= a_{11}(b_{12} - b_{22}) \\ p_4 &= a_{22}(b_{21} - b_{11}) \\ p_5 &= (a_{11} + a_{12})b_{22} \\ p_6 &= (a_{21} - a_{11})(b_{11} + b_{12}) \\ p_7 &= (a_{12} - a_{22})(b_{21} + b_{22}) \\ \end{align*}$

である。このアルゴリズムでは各 $p$ を計算する際に1度だけ乗算を行っているので、合計で7回の乗算を用いている。代わりに加算の回数は愚直に計算した場合よりも大幅に増えて、18回になっている。

ブロック行列の積

行列の積を計算する際、行列 $A, B$ それぞれをブロック（部分行列）に分け、それらを行列の成分とみなして積を考えてもよい。たとえば

$\displaystyle \begin{align*} \left( \begin{array}{rr|r} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ \hline a_{31} & a_{32} & a_{33} \\ \end{array} \right) \left( \begin{array}{rr|r} b_{11} & b_{12} & b_{13} \\ b_{21} & b_{22} & b_{23} \\ \hline b_{31} & b_{32} & b_{33} \\ \end{array} \right) &= \left( \begin{array}{r|r} A_{11} & A_{12} \\ \hline A_{21} & A_{22} \\ \end{array} \right) \left( \begin{array}{r|r} B_{11} & B_{12} \\ \hline B_{21} & B_{22} \\ \end{array} \right) \\ &= \left( \begin{array}{r|r} A_{11}B_{11} + A_{12}B_{21} & A_{11}B_{12} + A_{12}B_{22} \\ \hline A_{21}B_{11} + A_{22}B_{21} & A_{21}B_{12} + A_{22}B_{22} \\ \end{array} \right) \\ &= \left( \begin{array}{rr|r} a_{11}b_{11} + a_{12}b_{21} + a_{13}b_{31} & a_{11}b_{12} + a_{12}b_{22} + a_{13}b_{32} & a_{11}b_{13} + a_{12}b_{23} + a_{13}b_{33} \\ a_{21}b_{11} + a_{22}b_{21} + a_{23}b_{31} & a_{21}b_{12} + a_{22}b_{22} + a_{23}b_{32} & a_{21}b_{13} + a_{22}b_{23} + a_{23}b_{33} \\ \hline a_{31}b_{11} + a_{32}b_{21} + a_{33}b_{31} & a_{31}b_{12} + a_{32}b_{22} + a_{33}b_{32} & a_{31}b_{13} + a_{32}b_{23} + a_{33}b_{33} \\ \end{array} \right) \end{align*}$

のように計算できる。ブロック行列の性質を用いれば、 $2\times2$ 行列の積のアルゴリズムを任意の大きさの行列積に対して適用することができる。たとえばStrassenのアルゴリズムを用いたとすると、ブロック行列どうしの積が7回発生するが、それぞれの積に対してStrassenのアルゴリズムを再帰的に適用することによって大きな行列の積を計算することができる。このとき、必要な乗算の回数は $N^{\log_27}$ 回となり、愚直に計算した場合よりも高速になる。行列の和と積の計算は常に後者のほうが重いため、アルゴリズムを再帰的に適用することを考えたとき、乗算の回数が少ないアルゴリズムのほうが計算量が小さく優秀である。

ここで重要なのは、何らかのヒューリスティックな方法を用いてある大きさの高速な行列積アルゴリズムを発見できれば、ブロック行列の性質を適用してそれ以上の大きさの行列積も高速化できるということである。 AlphaTensorでは強化学習を用いて特定の大きさの行列積の高速なアルゴリズムを発見することを目的としている。簡単のために正方行列で説明しているが、行列が長方形であってもまったく問題ない。

TensorGame

AlphaTensorでは強化学習を行列積のアルゴリズム発見に適用するために、「クリアしたら行列積のアルゴリズムを発見したことになるゲーム」を設計し、これをTensorGameと呼んでいる。

Matrix multiplication tensor and algorithms. （元論文より引用）

状態

$N\times N$ 行列どうしの積のアルゴリズムを発見したいとき、TensorGameの盤面として $N^2\times N^2\times N^2$ のテンソル $T$ を用いる。テンソルの要素 $T_{ijk}$ は、行列 $A, B$ の積を $C$ としたとき、その要素 $c_k$ における $a_ib_j$ の係数を表している。つまり、TensorGameの盤面のバリエーションは、 $C$ の各要素が任意の $a_ib_j$ の線形結合であるような状態を表現できる。

引用画像aは $2\times2$ 行列どうしの積のアルゴリズムを発見するTensorGameの盤面である。この図では $T$ のうち0の要素を半透明に、1の要素を不透明に表示している。つまり

$\displaystyle \begin{align*} c_1 = a_1b_1 + a_2b_3 \\ c_2 = a_1b_2 + a_2b_4 \\ c_3 = a_3b_1 + a_4b_3 \\ c_4 = a_3b_2 + a_4b_4 \\ \end{align*}$

という状態を表している（これは正しい行列積の表示になっている）。TensorGameでは各要素を任意の整数にすることができるが、正しい行列積を表している状態は1つだけである。

TensorGameには2つの特別な状態が存在すると考えることができて、それは $T$ のすべての要素が0の状態と、 $T$ が「正しい行列積の表示」になっているような状態である。このうちの一方の状態からスタートして、ルールに従って $T$ に決められた操作を行うことでもう一方の状態に遷移させることができればクリアとなる。AlphaTensorは、このゲームを最短手数でクリアすることを目指す。

アクション

TensorGameでは、プレイヤーが取れるアクションは $N^2$ 要素のベクトル3つで表される。たとえば、

$\displaystyle u_1= \left( \begin{array}{rr} 1 \\ 0 \\ 0 \\ 1 \end{array} \right),\; v_1= \left( \begin{array}{rr} 1 \\ 0 \\ 0 \\ 1 \end{array} \right),\; w_1= \left( \begin{array}{rr} 1 \\ 0 \\ 0 \\ 1 \end{array} \right)$

はそのうちの一つである。 TensorGameにおける「一手」は「行列 $A, B$ の各要素の線形結合をそれぞれ1つずつ作り、それをかけ合わせたうえで $C$ の各要素に好きな係数で足す」操作を表している。

引用画像bは前述のStrassenのアルゴリズムを表しているが、先に例示した $u_1,v_1,w_1$ はこの図における $m_1$ に対応している。つまり、 $u_1 = (1, 0, 0, 1), v_1 = (1, 0, 0, 1)$ に対応する $(1a_1 + 0a_2 + 0a_3 + 1a_4)(1b_1 + 0b_2 + 0b_3 + 1b_4)$ を作り、それを $c_1, c_2, c_3, c_4$ に係数 $w_1=(1, 0, 0, 1)$ で加算しているということになる。

ここで重要なのは、TensorGameにおける一手は乗算をかならず1回だけ含むという点である。このことから、ゲームをクリアするまでに要した手数がそのまま完成したアルゴリズムに含まれる乗算の数となり、ゲームを最速でクリアする手順を求めることが最速のアルゴリズムの発見と等価であるということができる。

引用画像cはStrassenのアルゴリズムをTensorGameのアクションで表したものであり、ボードゲームにおける棋譜に対応するものである。これによると、Strassenのアルゴリズムは「7手」のアルゴリズムであると考えることができる。

成果

AlphaTensorはAlphaZeroをベースにした強化学習アルゴリズムによってさまざまなサイズのTensorGameの解法を学習し、その過程で生み出された解法には既存のアルゴリズムを上回る性能のものがあった。その中には $4\times4$ における47手（既存の最速は49手）や、 $5\times5$ における96手（既存の最速は98手）などが含まれる。

その他興味深かったトピック

元論文中には学習の方法や手法の応用についても書かれており、興味深いものがいくつかあった

上で紹介したTensorGameは時間計算量の考え方にしたがって乗算の回数が最小になるアルゴリズムを求めるものだったが、理論上最速のアルゴリズムがGPUやTPUの実機上でも最速とは限らない。TensorGameではスコアを「乗算の回数」ではなく「実機でそのアルゴリズムを用いたときにかかった時間」とすることで各デバイスに最適化した行列積のアルゴリズムを発見することができた。
AIの文脈では囲碁や将棋といったボードゲームは大きな状態空間をもっていることがよく言及されるが、TensorGameは状態空間だけでなく行動空間も非常に大きい。実際の学習では各ベクトルの要素が取り得る値をある範囲の整数に限定しているが、それでも各アクションの取り得る範囲は膨大であり、既存手法のようにすべてのアクションの評価値を求めて比較するといった方法を取ることができない。これを解決するためにモデルのPolicy HeadにTransformerのアーキテクチャを使用し、文章を生成するようにアクションを生成した。

など。ほかにも学習上の工夫のうち別のゲームに応用できそうな部分があった。

感想

囲碁や将棋をはじめとして、強化学習で訓練されたエージェントがボードゲームにおいて人間を上回るパフォーマンスを発揮する事例は多く知られているので、今回はアルゴリズムの発見をゲームに落とし込む過程にとくに注目した。「AIが強化学習で新しいアルゴリズムを発見した」というニュースを聞いたとき、さまざまなアルゴリズムに適用できる汎用的な手法が開発されたのかな、と思ったが、実際に論文を読んでみると問題設定の部分で人間がかなりサポートを行っており、他のアルゴリズムにそのまま適用できるものではなさそうだった。

環境を用意できるがその詳細が完全に分かっていない場合に強化学習は特に力を発揮するが、GPUの実機で高速なアルゴリズムを発見するということは机上の研究ではできないため、非常に興味深かった。今後発売されるデバイスの中には専用のアルゴリズムを強化学習でチューニングして性能を上げたモデルが出てくるかもしれない（？）

2023-03-07

ブログを始めたい

最近Twitterがいろいろとやばくなってきていて、フォロワーが移行先の話をしているのもよく見るようになった。

さっきも急にAPIの不具合でTwitter Webが繋がらなくなってしまい、ブラウザにエラーメッセージを含む生JSONがそのまま表示されるということになっていた。

近い将来に突然Twitterがなくなるとはあまり思ってないが、じわじわと衰退していくということはあるかもしれない。そうなったときにどうするかは決めてないが、友達の多い場所に自然と行くのかもしれないと思っている。

僕は2011年にTwitterに登録したけど、それは当時やっていた「魔法少女まどか☆マギカ」の公式アカウントをフォローして情報を得るためだった。なので当時はツイートは一切していなくて、フォロワーも0人だった。その後、2013年に高校3年生になってから友達になんとなくアカウントを教えたらフォローされて、そこからツイートもするようになった。

大学に入って学部生のころはずっとTwitterをやっていて、自分の考えていることもなんでも呟いていたけど、最近はTwitterで長文もあまり書かなくなったし、自分の考えみたいなものもほとんど呟かなくなってきている。いつからかは分からないけど、いつのまにかそんな感じになっていた。

それとは別に、勉強したことをアウトプットできる場所が欲しいというのはずっと思っていた。僕は学生時代に自分のホームページを作っていて、競技プログラミングの解いた問題や解けなかった問題などの記事をそこに投稿していた。僕のホームページは多分誰も見てなかったし、誰も見てない前提で書いていた。学生時代は暇だったのでそれでもモチベーションが保てていたし、自分の書いた記事を誰も見ていなくても自分だけは覚えていて、それが競プロのレートに繋がるという意識があったので続けられていた。

2020年の4月に就職してから、業務に関する勉強が面白くなっていたので競プロはあまりやらなくなっていた。そうすると毎日問題を解くという習慣もなくなり、HPは全く更新しなくなってしまった。

競プロ（と本業の物理）しかやってなかった学生時代よりいろんなことを勉強するようになったのに、そのことをHPに書く気にはあまりならなかった。その理由は、やっぱり「誰も見ていないから」だと思う。もはや競プロのレートを上げるという目標がないので、「誰も見てなくてもいいや」とは思わなくなっていた。

最近になって、なぜ世の中の多くのエンジニアが記事の参照性が高いHPではなくブログをやっていて、そこに自分の勉強したことを書いているのかということが理解できた。それはやっぱり、書いた記事を他人に見てもらいやすいからではないだろうか。何かを勉強してアウトプットするのは手間がかかるし、何らかのモチベーションで自分を引っ張らないとできない。自分のHPに書いた記事を他人に見てもらうのは難しいが、ブログならTwitterアカウントと連携して投稿しやすいし、見てもらいやすい。自分のアウトプットを他人に見てもらって反応がもらえたら、それを目当てにもっと勉強できるかもしれない。最初に「他人に見てもらうこと」をモチベーションにしなかったせいで、こんな当たり前のことに気づくのにずいぶん時間がかかってしまった。

こういった理由で、これからは勉強したことをブログに書いてみようかな、と思った。学生時代に3つだけ記事を投稿したブログを持っているので、そこに書くことにした。でも、いきなり「技術記事」を投稿してしまうと、僕のことなので「ブログには『質のいい記事』だけを投稿しよう」という気持ちになる可能性が高い。そんな気持ちで続くわけないので、最初にあえてカスの記事を投稿してブログを汚しておくことにした。それがこの文章である。最初にこういう文章を投稿しておけば、どんな記事でもこの記事よりは上になる。

あと、最近の僕はスカしていて、インターネットに自分の感情を書くのはダサいという考えになっているところがある。昔はそんなことなかったのに、いつの間にかそうなっていた。これを直したいので、あえて自分の感情を多く書いてみた（いつものTwitterの感じでいけば「ブログ始めました。これからは勉強したことをここに書いていきます」みたいな短い文章を書いているはずだ）

この記事はTwitter連携して投稿する予定なので、何人かは見ることになると思う。こんなことを書いておいて、そのあと1か月経ってもこの記事がずっとブログの一番上にあったら、メチャクチャ恥ずかしい。最初はこの記事を下に押し流すことをモチベーションにして記事をいくつか書いてみたい。何個か記事を書けば習慣化して、定常的にアウトプットできるようになるかもしれない。

あと、完全に勉強したことの話ばかりしようとは思っていなくて、趣味の謎解きやボードゲームの話なども書きたいと思っている。要するに、最近の僕がTwitterに書かなくなってしまったような話をここに書けたらいいなと思っているので、応援してください。

2019-08-03

TCO19 Japan Regional Eventに行ってきました。

競技プログラミングイベント

TCO19 Japan Regional Event に行ってきました！

リクルートコミュニケーションズがスポンサーとなって開催されたTopCoderのオンサイトコンテストで、僕はTopCoderが以前開催していた富士通デジタルアニーラのコンテストに参加していたので、Development枠で招待してもらえました。

朝

前日から東京に来て友達の家に宿泊していました。

朝は比較的余裕をもって東京駅までたどり着いていたのですが、急にトイレに行きたくなって並んだりしていたら時間的余裕が消滅してしまいました。リクルートがあるグラントウキョウサウスタワーには以前にも来たことがあったのですが、東京駅のどの出口から出ればよいかを覚えていなかったためTwitterで質問したりしてなんとか間に合いました。

TCO regional @ Tokyo Japan! pic.twitter.com/WrIG2ulubh
— sudoster (sudo0124) (@sudoster) August 3, 2019

午前の部

会場で衣類や缶バッジなどのグッズを貰って喜んでいるとすぐにイベントが始まりました（会場入りがギリギリだったため）。リクルートコミュニケーションズやTopCoderの中の人のお話を聞いたり、カッコイイPVを見たりしました。英語が聞き取れたり聞き取れなかったりしましたが周囲の雰囲気を見ながら適切に拍手などを行うことによって難なく乗り切ることができました。

その後はマラソンマッチがとても強いことで有名なtomerunさんによるマラソンマッチのintroductionを聞きました。僕はまだまだ雰囲気でマラソンマッチをやっている部分が多くあるので、強い人の取り組み方は非常に勉強になりました。

ここでDevelop部門やdesign部門のコンテストがありましたが、普段参加しているコンテストと形式が違っていて難しそうだったので参加を見送りました。Develop部門で招待されたにもかかわらずDevelop部門に参加しないという不審者になりました。

品物です pic.twitter.com/XV4Ioo1Idt
— 竹雄🤪 (@takeo1116) August 3, 2019

昼食

お弁当。おいしい。食べすぎました。

SRM

昼食が終わるとSRMのwarm-up roundがありました。10分で1問しかなく、解ければ賞金をもらえるというチャンスでしたがギリギリ間に合わずお金を得ることができず非常に残念でした。

僕はTopCoderでは主にマラソンマッチに参加していたので、このイベントに招待されるまでSRMはやったことがなかったのですが、事前に一度SRMに参加して練習しておいたので会場で無知を晒すことを防ぐことができました。練習していなかったらオンサイトに来ておいてコンテストの参加方法がわからないという不審者になっていたかもしれないと思うとこれは英断でした。

warm-up roundが終わると少し時間をおいて本番コンテストが始まりました。

本番ではEasyを見た瞬間に解法をひらめきましたが実装に手間取り結構時間をかけてしまいました。Medは想定解がDPだったのですが、僕は数学で解こうとしてしまい、残念ながら解けませんでした。イベントの時間割に「02:00 PM - 04:00 PM：TCO19 Tokyo Regionals Algorithm Round」と書かれていたのをコーディングフェイズが午後4時までという意味だと勘違いしていたので、のんびりやっているうちに唐突にコンテストが終了して動揺する不審者になってしまいました。

SRMのあとは問題の解説が行われて、RCOのsugim48さんがEasyとMedの解説をしてくれました。丁寧な解説で、とてもわかりやすかったです。Hardについては会場で解けた人の中から解説者を募集する形になって、snukeさんが名乗り出て解説してくれました。僕はそもそも問題文を読んでいなかったので、TopCoderのイベントでAtCoderの人が解説してるの面白いな、などと関係のないことを考えていました。

表彰式

解説が終わると、しばらく休憩を挟んで別室で懇親会と表彰式が行われました。表彰式ではSRMのシステムテストの結果発表がICPCのYes/Noのような形式で行われました。順位表で僕の周囲の人が結構Easyを落としていて、僕も落ちるかと思ったら意外にも耐えたので喜びました。Hardのpretestを通している人は数人いましたが、システムテストでsnukeさんが唯一生き残り単独全完を成し遂げていました。Development、Designの結果発表も行われ、全体的にかなり盛り上がりました。最後にTopCoderの中の人による挨拶と記念撮影があって、解散になりました。

まとめ

いつものオンサイトイベントとは違って今回はいわゆるalgo形式だけではなく様々な形式のコンテストに参加している人が招待されていたので、普段のオンサイトでは会えない人々と挨拶やお話ができてとても楽しかったです。また来年もこういったイベントがあれば是非参加できるように頑張りたいと思いました。

おわり