RareJob Tech Blog

レアジョブテクノロジーズのエンジニア・デザイナーによる技術ブログです

Lucene のコードリーディング

はじめまして、DevOps チームの中島です。
レアジョブ社の技術部門は、4 月 1 日 から新たにレアジョブテクノロジーズ社としてスタートしました。 新しい組織ではフルリモート可となっており、私も都内から引っ越して田舎暮らしを満喫しています。

さて今回は、 Elasticsearch (Lucene) のコードを読んでいく中で見つけた実装の工夫について紹介したいと思います。 レアジョブのサービスでも Elasticsearch を全文検索に利用している箇所があります。 OSS である Elasticsearch のコードを読み込むことで、高速化や検索精度の向上、その他プロダクトの品質向上に繋げたいと考えこのような取り組みをしています。

基礎知識

検索対象のデータ (インデックス) はストレージに保存されており、 Lucene はその内容をメモリに読み込みながら該当データの検索を行います。 データを効率よくエンコードしてストレージに保存することで、 単純に読み書きの量が減る、OS のバッファキャッシュにヒットする確率が上がる、等により検索速度の向上に繋がります。 以下では Lucene で実装されているエンコードの工夫について紹介します。

1. 可変長数値のエンコード

同じ数値型を等しいバイト数ではなく可変長で表現することで、小さい値のバイト数を節約するエンコード方式です。 最上位ビットを次のバイトが存在するフラグとして扱うことで実現しています。 代表的なところでは、Thrift や Protocol Buffers でも採用されています。 例えば、以下のように各値をバイト列で表現します。

値         バイト列
2^7        01000000
2^14       01000000 10000000
2^21       01000000 10000000 10000000
...

値を読み込むコードは以下です。
読み込んだ各バイトの最上位ビットが立っている場合 ( !b>=0 ) 、次のバイトを読み込んでいます。

// org.apache.lucene.store.DataInput
public int readVInt() throws IOException {
  byte b = readByte();
  if (b >= 0) return b;
  int i = b & 0x7F;
  b = readByte();
  i |= (b & 0x7F) << 7;
  if (b >= 0) return i;
  b = readByte();
  i |= (b & 0x7F) << 14;
  if (b >= 0) return i;
  ...

2. ドキュメント ID と単語の出現頻度のエンコード

全文検索エンジンは、検索対象の単語が出現するドキュメントを提示するだけでなく、 関連するドキュメントがより上位にくるように並び替える機能を提供する必要があります。
この並び替える機能は、検索クエリに対する各ドキュメントの関連度 (スコア) をドキュメントごとに計算し (スコアリング) 、 スコアの高い順に並び替えることで実現されています。

古くから文書検索においては、ドキュメント*1内の単語の出現頻度をスコアリングに使用しています。 検索クエリ内の単語が多く出現すれば、より関連度が高いドキュメントだろうという想定です。 この単語の出現頻度を記録するインデックスファイルの内容は、概念的に以下のようになっています。

フィールド f1
  単語 t1
    ドキュメント ID1, t1 の出現頻度
    ドキュメント ID2, t1 の出現頻度
    ドキュメント ID3, t1 の出現頻度
    (=フィールド f1 内に 単語 t1 が出現するドキュメント ID、その出現回数)
    ...

このうち、ドキュメント ID と出現頻度が繰り返される部分において、以下のような実装になっています。

  • ドキュメント ID 部分は前レコードのドキュメント ID との差分を格納する
  • 出現頻度が 1 の場合、ドキュメント ID 部分は ドキュメント ID を 1bit 左シフトして最下位ビットを立てる
    (出現頻度が 2 以上 の場合、ドキュメント ID を 1bit 左シフトした値を格納し、普通に出現頻度のバイト列を続ける)

つまりは、以下のような工夫がなされています。

  • 連続する数値を格納する際に、差分を格納することでビット数を削減する
  • 同じ単語が一度しか出現しない確率が高いという特性を利用して最適化が行われている

値を読み込む部分のコードは以下です。 docID 変数には前レコードの docID が入っています。 ドキュメント ID として読みこんだ値 (code) を 1bit 右シフトして docID に加算し、該当レコードの ドキュメント ID としています。 その後、最下位ビットの判定から出現頻度 (freq) を読み込んでいます。

// org.apache.lucene.index.FreqProxDocsEnum
public int nextDoc() throws IOException {
  ...
  int code = reader.readVInt();
    if (!readTermFreq) {
      ...
    } else {
      docID += code >>> 1;
      if ((code & 1) != 0) {
        freq = 1;
      } else {
        freq = reader.readVInt();
      }
    }
  ...
}

3. 指数表現によるエンコード

Elasticsearch における text フィールドの検索は、標準で BM25 と呼ばれるスコアリングアルゴリズムが採用されています。

https://images.contentstack.io/v3/assets/bltefdd0b53724fa2ce/blt78ee47f523d10430/5c57eb6165ace9e30b316318/bm25_equation.png

引用元: Practical BM25 - Part 2: The BM25 Algorithm and its Variables | Elastic Blog

細かい計算方法は他所に譲りますが、スコアリングに必要な情報がインデックスファイルに格納されていて、それを読み込みながら計算が行われます。 ここで紹介するのは上記の計算式に出てくるドキュメント長 (fieldLen)*2 です。
ドキュメント長はドキュメント内の単語の数を表していて、最大 232 - 1 = 4 バイト分の値の範囲を取るのですが、 浮動小数点数のような指数表現を用い、精度を落とすことで 1 バイトに変換された値がインデックスに格納されています。

1 バイト (8bit) のうち、先頭 5bit が指数部、末尾 3 bit が端数を表しています。
正確にはインデックスに格納される値 = (24 + α) のうち α の部分が上記で表現されます。
24 は 以下に示す longToInt4 メソッドを用いて Integer.MAX_VALUE を表現した値である 231 を、 1 バイトで表現できる最大長である 255 から引いた値です。可能な限り小さい値は正確に表現したいことが分かります。

α の部分をエンコードするコードは以下です。

// org.apache.lucene.util.SmallFloat
public static int longToInt4(long i) {
  ...
  int numBits = 64 - Long.numberOfLeadingZeros(i);
  if (numBits < 4) {
    // subnormal value
    return Math.toIntExact(i);
  } else {
    // normal value
    int shift = numBits - 4;
    // only keep the 5 most significant bits
    int encoded = Math.toIntExact(i >>> shift);
    // clear the most significant bit, which is implicit
    encoded &= 0x07;
    // encode the shift, adding 1 because 0 is reserved for subnormal values
    encoded |= (shift + 1) << 3;
    return encoded;
  }
}

終わりに

振り返ってみると全部エンコードの話になってしまいました。
コードリーディングをすると様々な効率化の工夫を発見出来て楽しいですね。
最後までご覧頂きありがとうございました。

We're hiring!

rarejob-tech.co.jp

*1:正確には処理単位はフィールドごとになりますが、このポスト内では混乱を防ぐためフィールドの代わりにドキュメントという表現をしています。

*2:単語の絶対数が多いドキュメントほど、該当の単語を含む確率は必然的に高くなるので、関連度を下げる方向に作用させたいわけです。EC サイトの商品名や YouTube のタイトルに、検索に引っかかりたいがために関連する単語を入れまくってる状態をイメージしてみてください。

Guzzleでリトライ処理を実装してみる

こんにちは。サービス開発チームのすずきです。

今回は「ネットワークは不安定なり、それを前提にリトライ処理を実装せよ」という天からの啓示があったので
PHPではどのような方法を用いて実現できそうか調べてみると Guzzle の Middleware 機構を利用できそうだったので、 Middleware を利用したリトライ方法について書いていきます。
HTTP クライアントとして Guzzle を利用していたこと、リトライ処理をアプリケーションのロジックと分けて Guzzle 側のみで完結できるのがいいと思ったのが採用した理由になります。

Middleware

Guzzle には Middleware という機構があってリトライを行う Middleware を備えています。
今回はそれを利用してリトライを行います。
RetryMiddleware: https://github.com/guzzle/guzzle/blob/master/src/RetryMiddleware.php

まずは公式のドキュメントを参考に Middleware の使い方を見てみましょう。

$stack = new HandlerStack();  // Middleware を追加するためのstackを生成する
$stack->setHandler(new CurlHandler());  // ベースとなるハンドラをセット

// この例では mapRequest という Middleware を stack に追加する
// $stack->push() をいくつも記載することで複数の Middleware を設定できる
$stack->push(Middleware::mapRequest(function (RequestInterface $request) {
    return $request->withHeader('X-Foo', 'bar');
}));

$client = new Client(['handler' => $stack]);

次にリトライの Middleware の使い方を見ていきます。
RetryMiddleware の生成ロジックを見ると以下のようになっています。

    /**
     * Middleware that retries requests based on the boolean result of
     * invoking the provided "decider" function.
     *
     * If no delay function is provided, a simple implementation of exponential
     * backoff will be utilized.
     *
     * @param callable $decider Function that accepts the number of retries,
     *                          a request, [response], and [exception] and
     *                          returns true if the request is to be retried.
     * @param callable $delay   Function that accepts the number of retries and
     *                          returns the number of milliseconds to delay.
     *
     * @return callable Returns a function that accepts the next handler.
     */
    public static function retry(callable $decider, callable $delay = null): callable
    {
        return static function (callable $handler) use ($decider, $delay): RetryMiddleware {
            return new RetryMiddleware($decider, $handler, $delay);
        };
    }

$decider にはリトライ条件を記述した bool を返す function 、$delay にはリトライ時にどれくらい待ってリトライするのかという待機時間をミリ秒で渡せそうです。

もう少しわかりやすいようにテストコードも見てみたいと思います。

    public function testRetriesWhenDeciderReturnsTrue()
    {
        $delayCalls = 0;
        $calls = [];
        $decider = static function (...$args) use (&$calls) {
            $calls[] = $args;
            return \count($calls) < 3;
        };
        $delay = static function ($retries, $response) use (&$delayCalls) {
            $delayCalls++;
            self::assertSame($retries, $delayCalls);
            self::assertInstanceOf(Response::class, $response);
            return 1;
        };
        $m = Middleware::retry($decider, $delay);

        // 以下略

確かに Middleware::retry() の第一引数 $decider には bool が返却されるfunctionが渡されていました。

リトライしてみる

ここまでで RetryMiddleware の使い方がわかりました。
今回は以下のような条件でリトライをしてみたいと思います。

  • 接続先ホストに接続できない場合にリトライする
  • リトライは3回まで行う

「接続先ホストに接続できない場合にリトライする」という条件はどのように判断できそうか見ていきます。
Guzzle の例外クラスは以下のような構造になっているようです。
https://docs.guzzlephp.org/en/stable/quickstart.html#exceptions

. \RuntimeException
└── TransferException (implements GuzzleException)
    ├── ConnectException (implements NetworkExceptionInterface)
    └── RequestException
        ├── BadResponseException
        │   ├── ServerException
        │   └── ClientException
        └── TooManyRedirectsException

A GuzzleHttp\Exception\ConnectException exception is thrown in the event of a networking error. This exception extends from GuzzleHttp\Exception\TransferException.

ドキュメントの中でこのような記載があるので、接続できないようなネットワークのエラーは ConnectException かどうかで判断できそうです。

ちなみに、http_errors オプションが true の場合はリクエスト送信時の HTTP ステータスが 4xx や 5xx の場合に例外をスローするようです。

A GuzzleHttp\Exception\ClientException is thrown for 400 level errors if the http_errors request option is set to true.

-> クライアントエラー時は ClientException がスローされる

A GuzzleHttp\Exception\ServerException is thrown for 500 level errors if the http_errors request option is set to true.

-> サーバエラー時は ServerException がスローされる

http_errors オプションはデフォルトが true なので例外を抑えたい時は false を設定するのが良さそうです。

$client->request('GET', '/status/500');
// Throws a GuzzleHttp\Exception\ServerException

$res = $client->request('GET', '/status/500', ['http_errors' => false]);
echo $res->getStatusCode();
// 500

改めて、今回の条件でリトライをする場合は以下のようなコードになります。

  • 接続先ホストに接続できない場合にリトライする
  • リトライは3回まで行う
        $decider = function ($retries, $request, $response, $exception) {
            if ($retries >= 3) {  // 初回を含めると最大4回のリクエストが送信される
                return false;
            }
            if ($exception instanceof ConnectException) {
                return true;
            }
            return false;
        };
        $retry = Middleware::retry($decider);
        $handler = HandlerStack::create(new CurlHandler());
        $handler->push($retry);
        $client = new Client(['handler' => $stack]);

テスト方法

リトライ処理の実装はできましたが、最後にテストをするにはどうしたらよいか見ていきます。

Guzzle には HTTP リクエストをモック化するためのハンドラを備えており、ハンドラを切り替えることで HTTP リクエストをモック化することができます。
ハンドラが設定されていない場合は、HandlerStack::create() 内で呼び出す Utils::chooseHandler() でデフォルトのハンドラが設定されている模様。

モック用のハンドラとして MockHandler があるので、これをハンドラとして設定すれば良さそうです。
改めて RetryMiddleware のテストコードを見てみると、
1回目のリクエストで HTTP ステータスコード 200 を返す場合は以下のように書けるようです。

    public function testDoesNotRetryWhenDeciderReturnsFalse()
    {
        $decider = static function () {
            return false;
        };
        $m = Middleware::retry($decider);
        $h = new MockHandler([new Response(200)]);
        $c = new Client(['handler' => $m($h)]);
        $p = $c->sendAsync(new Request('GET', 'http://test.com'), []);
        self::assertSame(200, $p->wait()->getStatusCode());
    }

では、3回目のリトライで HTTP ステータスコード 200 が返る場合の MockHandler は以下のように書けそうです。

        $h = new MockHandler([
                 new ConnectException('timeout', new Request('GET', 'test')),
                 new ConnectException('timeout', new Request('GET', 'test')),
                 new ConnectException('timeout', new Request('GET', 'test')),
                 new Response(200)
            ]);

以上で Guzzle の RetryMiddleware 機構を使ったリトライ処理とモック用のハンドラを利用したテストコードの書き方がわかりました。

さいごに

Guzzle すごい

新規スマホアプリ開発におけるチーム開発と技術選定を振り返る

新規アプリをリリースしました

APP/UX チームの玉置(@tamappe)です。

最近、弊社で新規アプリをゼロからフルスクラッチしてリリースしました。
リリースしたアプリは PROGOS といいます。PROGOS は英語のスピーキング力をAIを使って測定できるアプリです。
PROGOSのサービス自体はWebで先行してリリースされています。今回リリースしたのはそのアプリ版になります。

採用した技術はFlutterです。
プライベートではFlutterを触っていましたが普段の業務でFlutterを使っていないのでまさか業務でFlutterを触り始めるとは思ってもいませんでした。

progos.ai

Twitter アカウント

twitter.com

この記事では全くのゼロからの新規のアプリ開発の場合、どの技術スタックを採用するのがベストプラクティスなのかについて話します。
あるいは技術選定にめちゃくちゃ苦労した話になります。
ちなみにアプリに限らずシステム開発というのは時代やその時のトレンドによってペストプラクティスが変わりますので 2022 年における話になります。

Agenda

  1. 新規事業アプリのフルスクラッチでの技術選定
  2. 設計方針と開発の進め方
  3. チーム開発

1. 新規事業アプリのフルスクラッチでの技術選定

PROGOS のアプリ化について、最初にジャブを受けたのは確か部長の羽田(@jumboornot)との1on1だった記憶があります。

「今から新規でアプリを作るなら何で作るのが一番いい?」

という質問を受けました。
この問いに回答するのは今のアプリ開発界隈では非常に難しいように感じました。
アプリ開発ということで iOS だけではないことは当然です。ここでは iOS アプリと Android アプリの両方を指すことにします。
一番いいのは iOS アプリ、 Android アプリそれぞれネイティブ実装するのが一番いいのかなと。

クロスプラットフォームを使わない場合

今日でのアプリ開発では、iOS は UIKit と SwiftUI で2パターン、 Android では一般的なフレームワークJetpack Compose で2パターンのフレームワークが存在します。
Apple は UIKit ではなく SwiftUI を採用することを推していますので、iOSはSwiftUIを採用するのかな。(個人的には Objective-C が好きなので ObjC で iOS アプリを書きたいですね)
SwiftUI は Apple が 2019 年頃にリリースした iOS のネイティブアプリを宣言的 UI で書けるフレームワークです。
私が宣言的 UI とは何かについて語るのはまだ百億年早いと思っていますので省略します。こちらのページが一番わかりやすいです。

speakerdeck.com

iOS ネイティブでゼロから開発するのならおそらく SwiftUI になるだろうことはほぼ確定です。
つまり、設計方針として宣言的 UI を採用することになります。
Android ネイティブで同じように宣言的 UI を採用する場合、これは自動的に Jetpack Compose を採用することになります。

とすると、それぞれ次のように選択することになります。

iOS Android
SwiftUI Jetpack Compose

iOS では(技術選定当時) iOS 15から async/await が使えるようになりました。今では iOS 13 から使えるみたいです。これから新規アプリを開発する場合はasync/awaitを活用したいです。 また、サポートバージョンについてはなるべく古いバージョンはメンテナンスコストを考えると避けたいので最新バージョンがいいです。そのため、iOS のサポートバージョンを iOS 15 以上にしたいです(願望)。 ということでネイティブで開発するなら次のように提案する気がします。

iOS: SwiftUI + async/await (iOS 15 以上) + SwiftPM

あとは仕様の要件に満たすライブラリを頑張ってチョイスしてなんとかします。(だいたいのプロジェクトなんてそんなもん)

同じ発想を Android に適用させると

Android: Jetpack Compose + Kotlin (Android version 6 以上)

ぐらいのことを提案する気がします。あとは宣言的 UI とライブラリの力を存分に利用します。
スマホアプリをネイティブを新規でフルスクラッチする場合はこれぐらいのことまで考える必要があります。

クロスプラットフォームも考慮に入れる場合

次にクロスプラットフォームの Flutter を加えて吟味するとどうなるかについて検証していきます。

Flutter を採用すると最初から宣言的 UI になっています。
Flutter を採用すると標準で async/await を使えます。(これであとに色々ハマったことはまた別のストーリーとしてあります)
Flutter を採用すると一つのソースコードiOSAndroid アプリをリリースできます。
Flutter を採用するとry

ただし、 Flutter を採用すると課題になることがありました。
状態管理手法でどの設計パターンを採用すれば良いのかという重い課題が出ました。

今日の Flutter のパッケージとして、次の3つのパッケージがあります。

  • Riverpod
  • Provider
  • BLoC (Business Logic Component)

つまり、この3つの中からチームメンバーの人数とスキルセットを考慮してパッケージを選定する必要がありました。
これが非常に重かったです。

この課題は次の項目で述べます。

2. 設計方針と開発の進め方

弊社は検証の末、 Flutter を採用することに決めました。
今まで Flutter を使ったアプリをリリースしていないので今回は新しいことの挑戦になります。

弊社の行動指針に Rarejob Way というのがあります。

www.rarejob.co.jp

  • やりたいことをやろう (High Alignment High Autonomy)
  • ストーリーを語ろう (Share the Whole Story)
  • 変化を生み出そう (Make a Difference)

Flutter を採用すると、このうち「やりたいことをやろう」と「変化を生み出そう」は当てはまる気がしております。
アプリ開発で Flutter を採用することは初めてです。そこで、設計方針を吟味しないといけません。

APP / UX チームでアプリを開発できるのは私含めて3人です。

それぞれのメンバーとスキルセットは次の通りでした。

  • 部長 (iOS, Android, Flutter (BLoC, Provider経験者, Riverpod未経験))
  • Androidアプリエンジニア (Androidネイティブ、Flutter未経験)
  • iOSアプリエンジニア (私)

このメンバーとスキルセットを元に3つの設計方針から一つを決定する必要がありました。
色々調査と議論の末にここは次のように決まりました。

  • Riverpod + MVVM

  • 後述しますが、 freezed のパッケージは採用しませんでした。

3. チーム開発

採用する設計方針を決めたらやっと開発開始です。
全くのゼロからプロジェクトを立ち上げるから始めるのは仕事では初めてです。

アプリ開発において事前に決める項目は限られています。

  • フォルダ構成
  • コーディングスタイルとメインで使うWidget
  • APIクライアント

ポイントは上記だと思っています。

今回全てが初めてでしたので私で全部考えました。考えた後にチームメンバーに私の考えを共有して粉砕されたりしました。
採用したフォルダ構成は大まかには次のようにしました。

フォルダ構成

root/
 ├ assets/
 │  └ images/
 │  └ fonts/
 │  └ html/
 ├ android/
 ├ build/
 ├ ios/
 ├ lib/
 │  └ config/
 │  │ └ route_generator.dart
 │  └ constant/
 │  │ └ api_path.dart
 │  │ └ app_constant.dart
 │  └ l10n/
 │  └ model/
 │  └ service/
 │  └ ui/
 │  │ └ common/
 │  │ └ component/
 │  │ └ page/
 │  │ └ util/
 │  └ util/
 │  └ view_model/
 └ test/

決まったフォルダ構成はもちろん Github の README に記載してメンバーに共有と。

ただし、これは開発当初のフォルダ構成です。リリースする頃には api_path.dartapp_constant.dart が無くなるといった変更があります。
モデルとして MVVM を採用していますので

  • model/
  • ui/
  • view_model/

が分かる構成にしました。

ちなみに MVVM の大まな流れを参考にしたのはこちらの記事です。

wasabeef.medium.com

非常に勉強になりました。

コーディングスタイルと使うWidget

こちらは雰囲気です。
Wikiのページは時間や知見不足で作成できませんでした。

画面に該当するクラスの Widget については iOS ネイティブをモデルにしています。

  • 画面に該当するクラスの大元の部分はStatefulWidgetを使う
  • Viewに該当するクラスの部分はStatelessWidgetを使う

慣れ親しんでいる UIKit の場合、画面に該当するのは UIViewController で View に該当するのは UIView です。
UIViewControllerでは重要なライフサイクルという概念がありますのでイメージ的にはStatefulWidget
UIViewにもライフサイクルは存在しますが静的なイメージが合うのでStatelessWidget

こんな感じで「ネイティブ開発だったらどうか」を基準にしてWidgetを選定しました。

かなり困ったことが画面に該当するクラスの置き場所を page にするか screen にするか。
こちらはFlutterの初期生成プロジェクトで命名されている Widget 名が MyHomePage でしたので xxxPage(xxx_page.dart)命名することに決めました。

APIクライアントを何にするか

Flutter での API 連携は初めての取り組みでしたので、どう実装しようか非常に困りました。
前述のフォルダ構成の serivcemodel に該当する部分の設計です。

model 部分の実装において、当時 freezed パッケージが流行っていて設計として採用しても良いと思っていました。
ですが、検討した結果 freezed の採用は見送りました。使い方を調査をしていた時に使ってみるまでの難しさを体験して挫折しました。

pub.dev

実際に導入することは時間さえ掛ければなんとかなるのですが、今回のアプリ開発ではチーム開発なので他のメンバーも使えるように導入したパッケージの使い方を Wiki にまとめる必要がありました。
freezed を触ってみて手順書が作れそうにありませんでしたので、導入を断念しました。

確かに便利かもしれません。
ですが、自分でチームメンバーに説明できないぐらいの難しさを感じたら導入しないというのも一つの技術選定だと思っています。

結果的に model 部分は Dart 公式のドキュメントと同じ構成になりました。

flutter.dev

API クライアントは http パッケージを採用しています。

pub.dev

そのため、特にイカした設計にはなっておらず標準的なスタイルに落ち着いたかなと思っております。

終わりに

非常に長々と解説しましたが、無事に Flutter 製の PROGOS アプリを世に出すことができて満足しています。
よければ、使ってやってください!

iOS

apps.apple.com

Android

play.google.com

API仕様書作成にScribeを利用する

こんにちは。サービス開発チームのすずきです。

参画しているプロジェクトでAPI仕様書を作るためにScribeを利用してみたのでその経緯と使用方法をお話したいと思います。

Scribe

github.com

Laravel(Lumen/Dingo) で実装したソースコードのPHPDocをもとにAPIドキュメントを生成するためのツールになります。

  • ブラウザで閲覧できるHTMLのAPIドキュメントを作成
  • HTMLページではREST APIへのリクエストも送信可能(Swagger UIの"Try it out"と同様の機能)
  • Postman collectionファイルやOpenAPI Specificationの生成も可能

といった機能を持ちます。

以下のリンクからデモサイトを見ることができます。
デモ

なせScribeを利用したか

通常ある程度の大きさが予想されるシステム開発では、
フロントエンドはVueやNextで作成し、バックエンドはLaravelでREST APIを提供するような構成を取りそれぞれ別のリポジトリで管理しています。
フロントエンドとバックエンドを実装するメンバーはそれぞれ異なるため、コミュニケーションする際はAPI仕様書を参照しながら話すような場面が多くあり、
認識齟齬を少なくするためにAPI仕様書はOpenAPI(Swagger)を利用してしっかりと書いていくようにしています。

一方、今回のプロジェクトでは以下のような条件だったのでScribeを利用することにしました。

  • フロントエンド構成がMPAである
    • バックエンドはLaravelで処理し、描画に必要な値をbladeファイル上でVueに渡す
    • フロントエンドとバックエンドのコードはMonorepoで管理する
  • 画面の一部をAjaxで更新する処理が求められるのでフロントエンドとバックエンドはREST APIで通信することがある
    • APIエンドポイントの数は多くないが、両チームの認識齟齬を減らすために管理工数をあまりかけずに仕様書が欲しい
  • チームにはPHPDocを記述する習慣があり、ScribeのためにPHPDocを書くのではない

先述したOpenAPIで書いていく場合はバックエンドメンバーが管理しているOpenAPIのリポジトリをフロントエンドメンバーがローカルにcloneして立ち上げるのが手間になるため、
GitLab Pagesなどを利用してメンバー全員がAPI仕様書を閲覧できるようにします。
ガシガシ開発している最中だとOpenAPIへの変更もバンバン入り、どのブランチをPagesに上げておくのか、もしくは複数のブランチのAPI仕様書を見れるようにするのかといった工夫が求められ導入や管理コストがかかってしまいます。
しかし、今回のようにMonorepoで開発していくのであれば全メンバーが同じリポジトリをcloneすることになるので、
メンバー各々が自由なブランチのAPI仕様書をローカルで閲覧できるようにするためのコマンドを用意するだけ、という比較的低コストでAPI仕様書が用意できるようになりました。

Scribeの使用方法

今回はリクエスト時のパラメータとレスポンスデータのスキーマAPI仕様書でわかれば良いので、
それらをAPI仕様書で確認できるようにしていきます。

公式ドキュメントに沿ってScribeのインストールを進めていきます。

// composerを利用してScribeをインストール
$ composer require --dev knuckleswtf/scribe

// Scribeの設定ファイルを生成
$ php artisan vendor:publish --tag=scribe-config

これらのコマンドを実行するとsrc/configディレクトリ配下にscribe.phpという設定ファイルが作られます。

  • 認証を必要とする
  • DBを利用しない(全て外部APIからデータを取得する)

作成するAPIがこれらの条件を持つので、以下のような修正を加えました。

    /*
     * How is your API authenticated? This information will be used in the displayed docs, generated examples and response calls.
     */
    'auth' => [
        /*
         * Set this to true if any endpoints in your API use authentication.
         */
-        'enabled' => false,
+        'enabled' => true,


    /**
     * For response calls, API resource responses and transformer responses,
     * Scribe will try to start database transactions, so no changes are persisted to your database.
     * Tell Scribe which connections should be transacted here.
     * If you only use one db connection, you can leave this as is.
     */
-    'database_connections_to_transact' => [config('database.default')]
+    'database_connections_to_transact' => []

HTMLファイルの出力先やドキュメントを表示するURLなども変更できるようなので細かい設定はこちらをご確認ください。

Requestパラメータの表示方法

次にリクエスト時のパラメータを表示できるようにしていきます。
そのためにはScribeでは2つのやり方を用意しています。

  • PHPDocの@queryParam/@bodyParamアノテーションを利用して明示的に記述する
  • LaravelのValidation rulesの内容をもとに自動生成する

今回は前者の方法を選択しました。
Validation rulesを利用しているのですが、私たちが全てのパラメータに対してルールを記述しているわけではないためです。
Validation rulesはinline($request->validate([...]))で記述したもの、Validator::make()で記述したもの、RequestFormクラスのrules()メソッドに記述したものすべてに対応しているようです。

@queryParam/@bodyParamアノテーションを利用する場合は、
QueryStringに対しては@queryParam、RequestBodyに対しては@bodyParamを利用して以下のフォーマットに記載します。

@queryParam パラメータ名 型 ディスクリプション

これはControllerクラス、RequestFormクラスのどちらに記述しても大丈夫です。

公式ドキュメントからRequestFormクラスに記述する場合のサンプルを引用したものとそのときの表示結果が以下になります。

/**
 * @queryParam lang required The language.
 * @bodyParam title string The title of the post.
 * @bodyParam body string required The content of the post.
 */
class CreatePostRequest extends \Illuminate\Foundation\Http\FormRequest
{

}

// in your controller...
public function createPost(CreatePostRequest $request)
{
    // ...
}

f:id:keshipi:20220216100318p:plain
表示結果

Responseデータの表示方法

ここまででリクエスト時のパラメータをAPI仕様書で確認できるようになったので、次はレスポンスデータを表示できるようにしていきます。 レスポンスに関してもいくつか方法があるようです。

今回はエンドポイントに認証をかけている、Eloquent API resourcesを利用していないという理由で3と4番目は排除しました。(認証をかけていても3は利用できるかもしれませんがそこまで調査できておりません。ご存知の方いらしたら教えてください🙇‍♂️) 次に1と2それぞれの方法を見てみます。 @responseを利用する方法はインラインでレスポンスを記述する

/**
 * @response {
 *  "id": 4,
 *  "name": "Jessica Jones",
 *  "roles": ["admin"]
 * }
 */
public function getUser(int $id)
{
  // ...
}

@responseFileを利用する方法は外出ししたファイルのパスを記述する

/**
 * @responseFile storage/responses/users.get.json
 */
public function getUser(int $id)
{
  // ...
}

レスポンスが大きくなる(キーが増える)ことが見込まれる、PHPDocに記載するよりもjsonファイルに記載した方が記述の際にエディタの補助を受けやすいのでControllerクラスの見通しも良さそうなので今回は2番目の「@responseFileを利用する方法」を選択しました。 その際の記述と表示結果が以下になります。

// a file named users.get.json in storage/responses/
// {"id":4,"name":"Jessica Jones"}

/**
 * @responseFile responses/users.get.json
 */
public function getUser(int $id)
{
  // ...
}

f:id:keshipi:20220216105546p:plain
表示結果

さいごに

簡易でありますが工数をあまりかけることなく認識齟齬を低減させるためのAPI仕様書を用意することができました。 今回は利用しませんでしたがScribeはHTTPステータスごとにレスポンスのサンプルを用意したり、リクエストヘッダーやURLパスパラメータに関する情報を記述することができたりとライトユースからヘビーユースを幅広くカバーできる機能を持ち合わせています。 またPostman collectionファイルやOpenAPI Specificationを生成してくれるの嬉しい機能ですね。

英会話力の測定アプリ「PROGOS(プロゴス)」のデザイン改修の話し

こんにちは。気付いたらレアジョブ入社して早くも3年が経ちましたデザイナーのキョウです。
コロナの影響でずっと中国の実家に帰れずにホームシックがMAX状態ですが、早く春になって、いろいろなところに出かければいいなと祈ってばかりです。

さてと、つい最近弊社がリリースした「PROGOS(プロゴス)」という英語スピーキング力無料診断アプリをご存知でしょうか?

progos.ai

アプリの特徴として、AI採点により測定結果は最短2~3分で確認が可能、英語学習のスタンダードである「CEFR」に準拠した判定で、総合評価に加えて6つの指標別評価から、弱点を把握して効率のよい学習につなげることができます。

一番最初の開発段階ではデザインに注力せずに、問題なく英会話力の測定ができて、測定結果をアプリ内で確認できる、という機能面を重視して進めていましたが、最近やっといろいろ落ち着いてきたので、デザイン観点からのUI/UX改善が進められるようになりました。

今までは業務でアプリ開発チームとあんまり絡んだことがなかったので、自分としては今回はとても新鮮な気持ちで作業に入り、ユーザーにとって快適に使えるアプリってなんだろう、と考えるのが楽しい日々です。

初期段階の問題点

生まれたてのアプリなので、もちろん初期段階ではいろいろな問題点がありました。
例えばアプリが重かったり、操作が分かりづらかったり、機能面として不足してるところもいろいろありました。

そこで、企画チームを中心に調査し、以下のような問題点が上げられました。

  • アプリの立ち上げ初期画面がシンプルすぎる、PROGOS(プロゴス)についての簡単な説明を入れたい。
  • 画面下の登録ボタンと受験ボタンの位置が下に寄りすぎて、ユーザーが誤操作してしまうので改善したい。
  • 効率よくユーザーの質問を解決してあげたいので、よくあるお問い合わせページを新設したい。
  • 新規ユーザーがアプリの機能と使い方がすぐわかるように、簡単なチュートリアル画面を用意してあげたい。
  • 既存ユーザーが毎回受験する際に、もう把握しているのにもかかわらず、毎回受験のガイドラインのスライドを読まないと受験画面までに進まないので、もっと受験の手順をシンプルにしてあげたい。
  • ユーザーのテンションをあげて、ユーザー同士の繋がりを深め、PROGOSのことをもっと盛り上げてもらいたいので、受験結果のSNSシェア機能を追加したい。

改善するところはいっぱいあって、やりがいもすごく感じてる中、「ヤッホ~!やるぞ〜!」なノリでデザイン改修をはじめましたが、いざやりはじめると、自分の中の問題点もいくつか出てきました。

私はwebデザイナーとしての経験は長いのですが、アプリに関してのデザイン経験はまだまだ浅いので、どういうUI/UXがアプリに最適しているのかを考える日々でした。
同じデザインでも、使う手段や利用するユーザーによって全然違ってくるので、いろいろ考えないといけないなと感じました。

でもとりあえず、課題を上げて、企画チームと開発チームが優先順位をつけて、みんなで協力しながら、段階を分けて対応することになりました。

課題を解決するために、自分なりに調べて、いろいろなアプリを調査しました。
優れたアプリや機能があれば、なんでこれがいいと思ったのか、一度分析して、頭の中でイメージしたものをすぐ残すように、一度Figma上で複数パターンを作って、デザインチームの皆さまのご意見を伺いながらデザインレビューをしてもらい、出来たデザインを企画チームに提案として持っていき、最後は開発チームに実装してもらう、という流れで進めていました。

具体的な改修内容

施策① f:id:kyou_setsu:20220222112527p:plain

施策② f:id:kyou_setsu:20220218200807p:plain

施策③ f:id:kyou_setsu:20220218200825p:plain

施策④ f:id:kyou_setsu:20220218200843p:plain

初期の画面と改善後の画面をみるとわかりますが、コンテンツ内容とアプリの機能が徐々に充実して、受験するための準備や受験のやり方がよりわかりやすいように改善しました。

その中に、チーム内で一番盛り上がったのは受験結果画面のSNSシェア機能でした。
開発途中でいろいろな問題点やつまずくこともありましたが、チーム全員の協力で最後まで無事にリリースができたのは本当に良かったと思っています。
改めて人の優しさと心遣いで仕事が成り立っているのが実感できました!(笑)

PROGOSアプリはこれからも進化しつつけます

確かにPROGOSアプリは一番最初の状態よりだいぶ改善されましたが、決してこれで終わりではないです。
アプリ内のデザインと機能的にはまだまだ使いづらいところもあり、もっと改善したほうがいいところもいっぱいあります。
これからもユーザーさんの意見を取り入れながら、もっと使いやすいアプリを目指して、チーム全員協力して改善していけたらいいなと思っています!

それでは、また!

"EigenGame: PCA as a Nash Equilibrium" の紹介

導入

EdTechLab で機械学習エンジニアをしています山城です。 私の所属する EdTechLab では、 AI ビジネス英語スピーキングテスト「PROGOS(R)」のモデル開発と運用を中心に、その他データ分析やR&Dも行っています。

さて、機械学習では特徴量の次元削減に使われる手法として PCA (principal component analysis, 主成分分析) があります。EdTechLab でもモデル開発で使ったりしており、馴染みのある手法であります。そんな折、この PCA がゲーム理論におけるゲームとみなせるという、 ICLR2021 に採択された論文 EigenGame: PCA as a Nash Equilibrium openreview.net を見つけました。PCA も Nash 均衡もよく聞く概念ではありますが、この二つを並べて論じているのは初めて見ました。普段使っている手法がどのようにゲーム理論の観点から捉え直せるか、興味を引いたので論文を読み進めてみました。この記事では PCA をゲームとして定式化できることを示した論文の定理2.1 の紹介をします。

まずゲーム理論と PCA についておさらいし、その後定理の主張を説明していきます(ゲーム理論も PCA もご存知の方は最初の2節は飛ばしていただいても問題ないです)。

ゲーム理論の用語の紹介

論文の主張を理解するためにゲームを定式化し、Nash 均衡の概念を導入していきますが、その前によくある例を紹介します。

例. 囚人のジレンマ

[wiki]参照

二人の囚人 A, B がいて、次の前提と条件で司法取引を持ちかけられている。

  • (前提1)互いに相談はできないとする
  • (前提2)囚人はどちらも自分ができるだけ短い刑期で済ませたいと考えている
  • (条件1)片方が自白すれば、自白した方は釈放、黙秘した方は懲役10年
  • (条件2)2人とも黙秘すれば、2人とも懲役2年
  • (条件3)2人とも自白すれば、2人とも懲役5年

各囚人は自白と黙秘のどちらを選択をするべきか、というのが問題です。どちらの囚人も自分の利益の最大化(刑期の最小化)を目的としている場合、どちらの囚人も上記の前提のため、意思決定のプロセスは

  • 相手が自白した場合、自分が黙秘すれば懲役10年となるため、それよりも短い懲役5年で済む自白を選択しよう
  • 相手が黙秘した場合、自分が自白すれば釈放されるので、自白を選択しよう

となるため、結果的にどちらも自白し、どちらも懲役5年となります*1。 。さて、上記の問題は相手のとる戦略(自白or黙秘)を考慮しつつ、自分の利益を最大化(懲役の最小化)するように自身の戦略を選択する意思決定問題と捉えることができます。これをゲームとして定式化していきます。

ゲームの定式化

さっそくゲームを定式化します([lec2] を参照)。

(定義) ゲームとは3つ組み \displaystyle{
(I, S _ {i (i \in I)}, U _ {i (i \in I)})
} のことを指す。ここで各記号はそれぞれ

  • プレイヤー の集合 \displaystyle{
I={1, 2, ..., k }
}
  • 各プレイヤーのとれるアクションの有限集合 \displaystyle{
S _ i(i \in I)
}
  • 各プレイヤーの効用関数 \displaystyle{
u _ i: S \to \mathbb{R}
} ここで \displaystyle{
S := \prod _ {i \in I} S _ i
}

と定めれらます。これは各プレイヤーがおのおの自分のアクションを指定したときに \displaystyle{ S } の元 \displaystyle{ s } が一つ定まり、それに応じて、各プレイヤーの効用関数の値 \displaystyle{
u _ i(s)
}(i.e. 自分の利益)が定まるということを表します。

続いて Nash 均衡の概念を導入します。

(定義)  \displaystyle{S} の元をストラテジープロファイルと呼ぶ。

ここで便宜上の記号を導入しておきます。 \displaystyle{S _ i} の元を \displaystyle{s _ i} と表すことにして \displaystyle{s _ {-i}}\displaystyle{\prod _ {i \neq j} S _ j} の元を表すことにする。

Nash 均衡とは言ってしまえば、全てのプレイヤーに対して、自分だけアクションを変えると必ず自身が損をする状態が成立していることを指します。

(定義)  Nash 均衡とは、任意のプレイヤー \displaystyle{i} に対して

\displaystyle{
u_i (s^*_{i} , s^*_{-i}) ≥ u_i(s_i, s^*_{-i}), \quad s_i \in {}^{\forall}\!S_i
}

となる ストラテジープロファイル \displaystyle{
s^ * = (s^ * _ {i}, s^ * _ {-i}) \in S
} のことを指す。

さらに強い条件として上の等式を満たす \displaystyle{
s^ *
} が唯一である場合は \displaystyle{
s^ *
}strict Nash 均衡と呼ぶ。

先程の囚人のジレンマを上の定式化に当てはめてみると、

  • プレイヤー \displaystyle{
I = \{A, B\}
}
  • アクション \displaystyle{
S _ A = S _ B = \{ \text{自白}、\text{黙秘} \}
}
  • 各プレイヤーの効用関数は次のようになる (\displaystyle{
x _ A, x _ B
} は各囚人の取る選択を表す):
\displaystyle{
\begin{align*} (x_A, x_B) = (\text{自白}, \text{自白})\text{ のとき}& \quad u_A(x_A, x_B) = u_B(x_A, x_B) = 5 \\ (x_A, x_B) = (\text{自白}, \text{黙秘})\text{ のとき}& \quad u_A(x_A, x_B)=0, u_B(x_A, x_B) = 10 \\ (x_A, x_B) = (\text{黙秘}, \text{自白})\text{ のとき}& \quad u_A(x_A, x_B)=10, u_B(x_A, x_B) = 0 \\ (x_A, x_B) = (\text{黙秘}, \text{黙秘})\text{ のとき}& \quad u_A(x_A, x_B)=u_B(x_A, x_B) = 2\end{align*}
}

となります。

このときストラテジープロファイル \displaystyle{
(\text{自白}, \text{自白})
} が Nash 均衡となっており、さらにこれが strict Nash 均衡でもあることがわかります。

 以上の定式化により、各プレイヤーは他のプレイヤーの選択の結果の影響を受けつつ、自身の利益が最大となるように自身の行動を選択するという意思決定問題がゲームとして定式化され、Nash 均衡という概念が導入されました。

少し話はそれますが、Nash 均衡に関しては次の定理が知られています。

(Nash 均衡の存在定理 [lec5])

(上記のような)有限型のゲームにおいて、mixed strategy *2 については必ず Nash 均衡が存在する.

今回の論文で扱うアクションの数は有限ではない無限型のゲームだが、無限型のゲームについてはある条件を満たせば、(上で定義した pure な意味での) Nash 均衡が必ず存在することが示せます(こちらも[lec5]を参照)。

PCA のおさらい

[小西] を参照

PCA とはデータが \displaystyle{
d
} 個の変数からなる\displaystyle{
n
} 個のサンプルが与えられたときに、標本分散を最大化させる座標軸を逐次的に決めていくプロセスのことです。

 もう少し詳しくプロセスを説明します。 \displaystyle{d} 個の変数\displaystyle{
(X _ 1, X _ 2, ..., X _ d)
} からなる \displaystyle{ n } 個のサンプルデータが与えられているとします:

\displaystyle{
\begin{align*}x_1 &= (x_{11}, ..., x_{d1}),\\ x_2 &= (x_{12}, ..., x_{d2}), \\ ... \\ x_n &= (x_{1n}, ..., x_{n1}).\end{align*}
}

このとき各変数 \displaystyle{
X _ i
} の標本分散は \displaystyle{
\frac{1}{n} \sum _ j^ n (x _ {ij} - \bar{x} _ i)^ 2
} で与えられる(\displaystyle{
\bar{x} _ i
}\displaystyle{
X _ i
} の標本平均)。いま各変数の一次結合による変換

\displaystyle{
Y := v_1X_1 + \cdots + v_dX_d
}

によって得られる新たな変数 \displaystyle{
Y
} に対する標本分散を最大化させる \displaystyle{
\boldsymbol{v} = (v _ 1, ..., v _ d)^ {\top}
} を求めることを考えます。このとき \displaystyle{ Y } に関する標本分散は標本平均を \displaystyle{
\bar{y}
} とすると

\displaystyle{
\begin{align*} 
\frac{1}{n}\sum_i^n (y_i - \bar{y})^2 &= \frac{1}{n}\sum_i^n \{\sum_j^d v_j(x_{ij} - \bar{x}_j)\}^2 \\ 
&= \frac{1}{n}\sum_i^n (\check{\boldsymbol{x}}_i \boldsymbol{v})(\check{\boldsymbol{x}}_i \boldsymbol{v})\ \quad \bigl (\check{\boldsymbol{x}}_i := (x_{i1} - \bar{x}_1, ..., x_{id} - \bar{x}_d)\bigr) \\ &=\frac{1}{n}\sum_i^n \boldsymbol{v}^{\top}\check{\boldsymbol{x}}_i^{\top}\check{\boldsymbol{x}}_i \boldsymbol{v} \\ &= \boldsymbol{v}^{\top}M \boldsymbol{v} \quad \bigl (M := \frac{1}{n}\sum_i^n \check{\boldsymbol{x}}_i^{\top}\check{\boldsymbol{x}}_i \bigr)
\end{align*}
}

と変形できます。ここで \displaystyle{
M
}\displaystyle{
X
} の標本分散共分散行列となっています。さらに求める \displaystyle{
\boldsymbol{v}
} には制限条件としてノルムが1 *3であることを課す。これにより標本分散を最大化させる \displaystyle{
\boldsymbol{v}
} を求める問題は最適化問題

\displaystyle{
\begin{align*} 
&max \quad v^T M v \\ 
&subject \, to \quad v^T v = 1
\end{align*}
}

の解として定式化される。この最適化問題ラグランジュの未定乗数法を使うことで、固有値問題

\displaystyle{
Mv = \lambda v 
}

に帰着される。この固有値問題を解き、得られる固有値の中で最大のものを選ぶ(実はそれが標本分散となっている)、その固有ベクトル第1主成分と呼ぶ(それを \displaystyle{
\boldsymbol{v _ 1}
} とおく)。第1主成分を求めた後、今度は2番目に大きい標本分散が得られる \displaystyle{
\boldsymbol{v}
} を求めていく。2番目に求める \displaystyle{
\boldsymbol{v}
} には標本分散を最大にする条件に加えて第1主成分 \displaystyle{
\boldsymbol{v _ 1}
} に対する直交条件*4が追加される。再度上のプロセスを繰り返せば2番目に大きい標本分散を求める問題は結局

\displaystyle{
\begin{align*} 
&max \quad v^T M v \\ 
&subject \, to \quad v^T v = 1, v^Tv_1 = 0
\end{align*}
}

として定式化されます。こちらも同様にラグランジュの未定乗数法で固有値問題に落とし込めます 。同様にそこで得られた固有ベクトル第2主成分と呼びます。以降の第 \displaystyle{
i
} 主成分 (\displaystyle{
i=3, 4, ..., d
}) も同様にして求められます。以上が PCA のプロセスの概要になります*5

PCA では求めた主成分のうち、第 \displaystyle{
k
} 主成分(\displaystyle{
k \lt d
})までを用いて、元のデータを線形変換

\displaystyle{
XV_k \quad \bigr(V_k := (\boldsymbol{v_1}, \boldsymbol{v_2}, ...,\boldsymbol{v_k})\bigl)
}

を行うことで( \displaystyle{
d
} 次元から \displaystyle{
k
} 次元への)次元削減を実現できます。

論文の定理2.1 の主張

 ここまででようやく定理の主張を理解する準備が整ったので早速説明していきます。 まず論文の定理2.1 の主張を述べておきます。\displaystyle{
X
}\displaystyle{
n \times d
} 行列として、\displaystyle{
0 \lt k \le d
} とする。

定理2.1

\displaystyle{
M:= X^ TX } *6の top-\displaystyle{ k }固有ベクトルは正かつ異なるとする*7。このとき、これらベクトルは各 \displaystyle{
i \in {1, 2, ..., k}
} に対して、

\displaystyle{
\max _{\hat{v}_i^{\top} \hat{v}_{i}=1} 
\left\{ 
u_{i}\left(\hat{v}_{i} \mid \hat{v}_{j \lt i}\right)
:= \hat{v}_i^{\top} M \hat{v}_{i} - \sum_{ j \lt i } \frac{\left(\hat{v}_i^{\top} M \hat{v}_{j}\right)^{2}}{\hat{v}_j^{\top} M \hat{v}_{j}}
= \left\|X \hat{v}_{i}\right\|^{2}-\sum_{ j \lt i } \frac{\left\langle X \hat{v}_{i}, X \hat{v}_{j}\right\rangle^{2}}{\left\langle X \hat{v}_{j}, X \hat{v}_{j}\right\rangle}
 \right\}
}

が定めるゲームの strict な Nash均衡となる。(主張ここまで)

ここで \displaystyle{
M
} の top-\displaystyle{
k
}固有ベクトルとは \displaystyle{
M
}固有値を大きい順に並べたとき、上位 \displaystyle{
k
} 個の固有値固有ベクトルを指す。上で見たように、これは \displaystyle{
X
} の第1主成分から第 \displaystyle{
k
} 主成分のことを指しています。

 定理の主張はPCAを直交条件を制約条件とする \displaystyle{
v^ TMv
} を最大化する \displaystyle{
v
} を見つける最適化問題としてではなく、その直交条件という依存関係を目的関数の中に組み込むことで、関数 \displaystyle{
u _ {i}\left(v _ {i} \mid v _ {j \lt i}\right)
} をプレイヤー \displaystyle{
i
} の効用関数として捉えることができ、PCA をゲームとして再定式化することができることを述べている。

表にすると以下のような対応になる。

PCA 囚人のジレンマ
プレイヤー \displaystyle{I = {1, 2, \dots, k }} \displaystyle{I = {A, B }}
アクション \displaystyle{ v \in S^{d} } (\displaystyle{ S^{d} }\displaystyle{ d } 次元単位球) 自白、黙秘
効用関数 \displaystyle{ u _ {i}\left(\hat{v} _ {i} \mid \hat{v} _ {j \lt i}\right), i \in I } \displaystyle{ u_A, u_B }
Nash 均衡 \displaystyle{ v_i (i \in I) }\displaystyle{ v_i } は第\displaystyle{ i }主成分) \displaystyle{  (x_A, x_B) = \left( \text{自白}、\text{自白} \right) }

 

 上記の \displaystyle{
u _ {i}\left(\hat{v} _ {i} \mid \hat{v} _ {j \lt i}\right)
} の式はどのように得られたのかについて、論文に沿ってざっくり説明します*8

上の式をPCA の再定式化として導くために論文では \displaystyle{
d \times k
} 行列\displaystyle{ \hat{V} }に対して \displaystyle{
R(\hat{V}):= \hat{V}^ {\top} M \hat{V}
} を導入しています。\displaystyle{
R(\hat{V})
} の値がもし \displaystyle{
\hat{V}
}\displaystyle{
X
}\displaystyle{
k
} 個の主成分(i.e. \displaystyle{M}固有ベクトル)からなる行列なら \displaystyle{
R(\hat{V})
}\displaystyle{
k \times k
} の対角行列となることに注意します。著者らは次の最適化問題を導入しました。

\displaystyle{
\max _{\hat{V}^{\top} \hat{V}=I} \sum_{i} R_{i i}-\sum_{i \neq j} R_{i j}^{2}.
}

ここで \displaystyle{ R _ {i j} } は行列 \displaystyle{ R }\displaystyle{ (i, j) } 成分*9。この式のお気持ちを述べると、第一項

\displaystyle{
\sum_{i} R_{i i}
}

対角成分の最大化の役割をもたせ(ここは \displaystyle{ u_i } の第一項に対応)、第二項

\displaystyle{
- \sum_{i \neq j} R_{i j}^{2}
}

非対角成分の絶対値の最小化の役割を持たせていますつまりこの最適化問題\displaystyle{
R
} を対角化しつつ、その対角成分を最大化させる \displaystyle{
V
} を求める、すなわち \displaystyle{
M
}固有値を最大にする固有ベクトルたちを求める問題と考えられます。一方でこの定式化で求まる固有ベクトルでは、主成分間の関係が満たす依存関係(直交条件)を織り込めておらず、PCA の再定式化にはなっていません。そこで \displaystyle{
- \sum _ {i \neq j} R _ {i j}^ {2}
} を上記の関数 \displaystyle{
u _ {i}\left(\hat{v} _ {i} \mid \hat{v} _ {j \lt i}\right)
} の第二項に置き直すことで、制約条件からは依存関係を外しつつ、依存関係を導入した上記の定理2.1の式でPCAの定式化をすることができました。

以上で定理2.1 の紹介終わる。

後記

この後、論文では定理2.1 の定式化に基づいて、主成分を求めるアルゴリズム(sequential なものとdecentralized なもの)の提案や、その収束性の証明、パフォーマンスの評価のための実験について解説しています。

著者らは論文の結論部分で、今回の定式化や、そこで提案されたアルゴリズムについて、連合学習やプライバシー保護学習や GAN への応用*10 、またはアルゴリズムの改良*11 などを今後の研究の方向性として挙げ、今回のようにゲームの観点から機械学習を見ることで、機械学習ゲーム理論両分野の双方向の発展につながることへの期待を述べています。

今回この論文を読み進めてみて、ゲーム理論や PCA の詳細を復習ができたことや、機械学習で馴染みの深い PCA がゲーム理論の言葉に置き換えられていくのは面白かったです。今回紹介できなかったアルゴリズム部分や続編の論文、ゲーム理論の実応用周りをもう少し調べてみたいと思いました。

最後に、詳細は確認していませんが ICLR 2021 には他にも Dropout をゲーム理論の観点から捉え直した別の論文も投稿されているので、気になる方は確認してみてください。

参考文献

[wiki] https://ja.wikipedia.org/wiki/囚人のジレンマ

[小西] 多変量解析入門, 小西貞則

[lec2] https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-254-game-theory-with-engineering-applications-spring-2010/lecture-notes/MIT6_254S10_lec02.pdf

[lec5] https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-254-game-theory-with-engineering-applications-spring-2010/lecture-notes/MIT6_254S10_lec05.pdf

*1:ちなみにどちらも黙秘すれば、どちらもより短い懲役に2 年となります。その場合の選択はパレート最適と呼ばれます [wiki] 参照

*2:プレイヤーのとるアクションに確率の概念を導入したもの

*3:この条件 \displaystyle{ v^{\top} v=1 } は単位球上のベクトルという条件に等しい i.e. コンパクト空間上の点

*4:変数間を独立にするため

*5:実際に求める際にはSVD など行列分解を用いたアルゴリズムで実行される。

*6:論文中で特に言及はないが、この \displaystyle{ X } はすでに中心化されていると仮定していると思われる(一般性は失われない)。これ以降に出てくる \displaystyle{ X } は全てそのように仮定する

*7:この定理の証明でこの条件が必要になる

*8:筆者の理解不足で誤りが含まれているかもしれないが、その際はご指摘いただけると幸いです

*9:\displaystyle{ R := (R_{ij}) } は標本分散共分散行列とみなせることに注意

*10:ちなみに GAN は2人ゼロサムゲームと捉えることができる

*11:著者らは続く論文で、よりパフォーマンスの高いアルゴリズムを提案している

Cookie と ALB を利用して特定のユーザーにのみカナリアリリースを行う

おはようございます。最近 AWS CDK ばかり触ってるしのです。

今回は、実際にレアジョブで行なった事例を元に、新しいバージョンのアプリケーションをいかに少ないリスクでリリースするかについてお話します。

概要

やったことは以下のような感じです。

カナリアリリースを行ない、低リスクで新バージョンのアプリケーションをリリースしたい。

要件上、"特定のユーザーにのみ"新バージョンを見せて、他のユーザーは既存のアプリケーションを利用して欲しい。

リクエストの分散自体は ALB の機能で可能だが、"特定のユーザーのみ" を対象にするためのロジックをどこかで持つ必要がある。

アプリケーション側でログイン時に"特定のユーザーのみ" 判定用のCookie を発行する。(ログイン時は必ず既存のアプリケーションへリクエストする)

ALB のリスナールールにて、判定用の Cookie を持つリクエストは新しいバージョン、それ以外は既存のバージョンへ流すルールを設定する

Cookie を発行する割合をアプリケーション側で変更して、徐々に新しいバージョンのアプリケーションを公開していく

f:id:shino8383:20220128162432p:plain

経緯

弊社では、最近までメインサービスとなるレアジョブ英会話の大規模リファクタリングを行っていました。

何年も稼働してきた既存アプリケーションから仕様は大きく変更せずに、開発効率の改善などを目的に 1 から作り直すことを機能単位に行なっていました。

その中で、レアジョブ英会話の中でもコア機能となる講師検索機能やレッスン予約のリプレイスは影響範囲が広く、サービスが完全に利用できない状況さえ発生しうるリスクの高いプロジェクトでした。

事前に検証するのはもちろんですが、問題が発生した際のサービス影響を最小限にする工夫が必要でした。

そこで、カナリアリリースで少ないユーザーから徐々に新しいリリースを公開して...とやりたいところですが、問題がありました。

  1. フロントのデザインが大きく変わっているので、新しい画面を見せるユーザーは固定したい
  2. 個人ユーザーだけではなく、法人ユーザーなどもいるため、特定のユーザーには既存の画面を見せたい(法人ユーザーはカナリアリリースできない要件があった)

そのため、特定のユーザーにだけ新バージョンを利用して頂くためのロジックが必要になり、Cookie と ALB のリスナールールを組み合わせた段階リリースを行いました。

ロールバックも ALB のリスナールールを変更するだけでよく、また必要な Cookie の値が知られたとしても新しいバージョンのアプリが利用されるだけなので問題ないと判断しました。

その結果として、古の仕様やレアケースなどが起因となる事前の検証で確認が漏れていた不具合をユーザー影響をできるだけ小さくしたまま検知することができました。

実装詳細

以下の画像のように、判定用の Cookie を持っているか・特定のパスか を判定するルールを設けて、マッチすれば新バージョンのアプリを含んだターゲットグループへ Forward します。

f:id:shino8383:20220128163014p:plain

このルールを既存のアプリケーションへ Forward するためのルールより優先度を高くして設定します。

その結果、特定の画面について特定の Cookie を持っている場合は新バージョンへ、持っていなければ既存バージョンへリクエストが送られます。

Cookie の付与については user id を指定する形で付与しました。

結論

特定のユーザーにのみ段階的にリリースを行うという話はあまり聞いたことがなかったので、今回お話させて頂きました。 普通のカナリアリリースであれば、AWS が提供している機能で簡単に実現できるのですごいですよね。

今回はロールバックの判断とかメトリクスの監視、ログの監視など正常に動いているかどうかの判断が複雑だったので自動化等はしておりません。

ではこの辺で。ありがとうございました。

パワー

we're hiring!!

appeal.rarejob.co.jp