dely Tech Blog

クラシル・TRILLを運営するdely株式会社の開発ブログです

国内初?マルチリービングでランキングを勝手に自動改善!

f:id:rnitame:20200814180016p:plain

はじめに

こんにちは。 機械学習エンジニアの辻です。

さて本日は、「国内初?マルチリービングでランキングを勝手に自動改善!」ということで、マルチリービングという手法と、その手法を使ったランキングの自動最適化の方法についてご紹介したいと思います。なお、今回の取り組みは、筑波大学・図書館情報メディア系・准教授の加藤誠先生*1に大変ご助力賜りました。この場を借りてお礼申し上げます。

f:id:long10:20200629081915j:plain

目次

アローの不可能性定理

さて、マルチリービングのご紹介に入る前に、みなさんアローの不可能性定理*2なるものをご存知でしょうか?ちょっとWikipediaで調べてみたところによると、「投票者に3つ以上の独立した選択肢が存在する場合、如何なる選好投票制度であっても、個々人の選好順位を共同体全体の(完備かつ推移的な)順位に変換する際に、特定の評価基準(定義域の非限定性、非独裁性、パレート効率性、無関係な選択肢からの独立性)を同時に満たすことは出来ない。」とありました。

ちょっと何言ってるかわからないですね。

f:id:long10:20200625222933p:plain

要するに、この定理は次の5つの「公正さ」の基準を、常に同時に複数の人に対して満たすようなランキングなんて作れないよ、という主張です。

  • 人々の選好の順序は自由だ
  • 満場一致
  • 独裁者はいない
  • 他の選択肢から影響を受けない
  • 堂々巡りの矛盾にならない(a>b , b>cなら必ずa>c)

つまり、いつの世もみんなの心が一つなることは絶対にないというわけです、悲しいかな。

クラシルのランキングについて

前置きはこれくらいにして、クラシルには様々なランキング機能*3があります。

クラシルのランキング機能(ある日のランキング)

f:id:long10:20200625224611p:plain

ランキングの課題

クラシルのランキングは、現在利用していただいている多くのユーザさんの声によって作成されています。 しかしながら、先ほどのアローの定理が主張するように、ユーザさん全員に喜んでもらえるただ一つのランキングを作成することは無理なので、 この例の場合は、申し訳ないことにサバが嫌いな人にとって、今日のランキングは最低!ということになってしまうのです。(美味しいのにね。)

では、どうしたらいいか?

先ほどのアローの定理を再び思い出してください。ここで主張されているのは、列挙した5つの「公正さ」の基準を常に同時に複数人では満たせないということでした。

でも逆に言えば、

  1. 常に→適宜
  2. 同時→変化する
  3. 複数人→少人数

このような条件なら、完璧ではないにせよ、少しはユーザさんに喜んでもらえるランキングに近づけるんじゃないか? それが今回の取り組みのモチベーションになります。

マルチリービングって何なん?

マルチリービング(Multileaving)というのは、インターリービング(Interleaving)の複数版のことです。 それでは、インターリービングが何かというと、それはA/Bテストを手っ取り早く行う手法の一つです。

A/Bテストとはシステムの機能やデザインの良し悪しを判定するための取り組みのことで、 仮説検定やベイズ最適化を用いて評価するのが一般的です。(FirebaseのA/B Testing機能などを使うと便利ですね。)

f:id:long10:20200629082823p:plain

ただ、こういった方法だと、サンプル数を十分に確保できるまで評価できなかったり、評価方法が複雑になり良し悪しの判断が難しいという状況が起こったりします。 そうなると手っ取り早くAとBのどっちがいいか知りたいというニーズを満たすことができません。

そこで、このマルチリービング(インターリービングも同じ)という手法は、非常に高感度なランキング評価手法であって、 結果判定が可能になるまでの時間やサンプル数が比較的少なくても、AとBのどっちがいいか判断したいというニーズを満たすことができるという、 そんな非常に画期的な手法になります。*4 *5

さて、詳しく知りたい方は、脚注4の加藤先生のQiitaをご参考頂きたいと思うのですが、 この手法をめちゃくちゃ大雑把に説明すると、

  1. いくつか(たとえば4つ)の条件でランキングを作る
  2. いい感じにランキングをごちゃ混ぜにするアルゴリズムを使って、ごちゃ混ぜランキングを作る(初期は1/4ずつ均等に配分するなど)
  3. ユーザさんが、このごちゃ混ぜランキングをクリックした結果(暗黙フィードバック)を集計する
  4. 3で得られた結果から、最初に作った4つのランキングのうち一番強いランキングを評価して、その強いランキング(好まれた)の混ぜる割合をちょっと増やす
  5. 混ぜる割合を変えた状態で2に戻り、再びごちゃ混ぜランキングを作る

(以降、繰り返し)

このとき、このいい感じにごちゃ混ぜにするアルゴリズムの種類にはこのようなものがあります。

  • Balanced interleaving(均衡交互配置) (Joachims 2002a, Joachims 2003)
  • Team draft interleaving(チームドラフト交互配置) (Radlinski et al. 2008)
  • Probabilistic interleaving(確率的交互配置) (Hofmann et al. 2011)
  • Optimized interleaving(最適化交互配置) (Radlinski and Craswell 2013)

そして、今回使用したのは、これらをさらにいい感じにした版のPairwise Preference Multileaving(略してPPM)になります。*6

こちらは加藤先生ご自身がPythonモジュールとしてオープンソースとして公開されているのでご指導いただきつつ利用させて頂きました。*7

以下、加藤先生のモジュールを使用したPPMのデモ実装になります。 少しだけ詳しくみていきましょう。

まずは、ランキング対象となるダミーレシピデータとそのデータに合わせたスキーマクラスを用意します。 レシピ動画の素性を持つVideoクラス、ランキングを生成するRankerクラス、そしてユーザ情報を保持するUserクラスです。 Rankerクラスのrank関数では、与えられたランキングの条件ごとの割合とRankerの重みを線形結合しています。

class Video(object):
    def __init__(self, id, genre_ids, features):
        self.id = id
        self.genre_ids = genre_ids # レシピのジャンル
        self.features = features # 素性(ランキングの条件)

    def __hash__(self):
        return self.id


class Ranker(object):
    def __init__(self, keys, w):
        self.keys = keys # 素性(ランキングの条件)
        self.w = w # 重み

    def rank(self, documents):
        result = sorted(
            documents,
            key=lambda x: np.array([x.features[k] for k in self.keys]) @ self.w.T,
            reverse=True
        )
        return result


class User(object):
    def __init__(self, id, favorite_feature_id):
        self.favorite_feature_id = favorite_feature_id
        self.id = id

    def click(self, videos, click_cnt=3):
        # ユーザはfavorite_feature_idが高いものをクリックする
        return to_id(sorted(videos, key=lambda x: -x.features[self.favorite_feature_id])[:click_cnt])

videos = []

# ダミーレシピデータの作成
def create_videos():
    for i in range(10000):
        video = Video(
            id = i + 1,
            genre_ids = random.sample(genre_ids, 2),
            features = {fid: random.random()  for fid in feature_ids}
        )
        videos.append(video)


def gen_rand(size):
    m = np.random.uniform(low=-1.0, high=1.0, size=size)
    m /= (np.linalg.norm(m))
    return m

つぎに、generate_fluctuated_weight関数として、重みをちょっとだけ変更する(これを摂動と呼んでいます。)関数を定義します。 つまり、初期の重みは単位ベクトルに保存していますが、これを微変化させることで、混合するランキングの割合を調整しています。

# 閉区間[0,1]に収まるように制限する
def generate_fluctuated_weight(original_weight):

    unit_vec = gen_rand(len(original_weight))
    diff_vec = unit_vec * delta

    # 元ベクトルに加算、閉区間[0,1]からはみ出す場合は、はみ出る分を他に付け替え
    tmp = original_weight + diff_vec
    tmp2 = sorted([(i, _) for i, _ in enumerate(tmp)], key=lambda x: x[1])

    for i, v in tmp2:
        if v < 0.0:
            tmp[i] = 0.0
            tmp[-(i+1)] += v

    tmp /= np.linalg.norm(tmp) # 正規化
    diff_vec = tmp - original_weight
    unit_vec = diff_vec / delta

    return (original_weight + diff_vec, unit_vec)

get_superior_rankers関数は、ユーザさんのクリック状況から、一番強かったランキングを判定する関数です。

def get_superior_rankers(il_result):

    prefs = defaultdict(int)
    for res in il_result:
        for r in res:
            prefs[r] += 1

    winner_indexes = []

    for i in range(1, ranker_size):
        wins = prefs[(i, 0)] - prefs[(0, i)]
        if wins > 0:
            winner_indexes.append(i)

    return winner_indexes

そして、このupdate_ranking関数が実際にランキングを生成する関数になります。 現在の重みを摂動させて混合ランキングを作成します。 作成後に、摂動した結果の重みも更新します。

def update_ranking(user, genre_id):

    # メイン重みを取得
    res = get_parameter()
    w = np.array([_[1] for _ in res])

    target_keys_count = len(feature_ids)
    # unit_vecs = np.array([np.zeros(target_keys_count)] + [generate_fluctuated_weight(w) for i in range(ranker_size - 1)])

    weight_vecs = [w] + [generate_fluctuated_weight(w)[0] for i in range(ranker_size - 1)]
    rankers = [Ranker(feature_ids, _w) for _w in weight_vecs]
    top_videos = get_top_videos_per_genre(genre_id)
    rankings = [to_id(ranker.rank(top_videos)[:ranking_count_per_genre]) for ranker in  rankers]

    ppm = PairwisePreference(rankings)
    mixed_ranking = ppm.interleave()

    #  ランキング保存
    # 摂動後の重み更新

こちらのevaluate関数がランキング結果を評価する関数になります。 ユーザさんのクリックした結果を受けてランキング優劣を評価し、重みを更新します。

def evaluate(user, genre_id, click_video_ids):

    # 保存済み摂動重み群をもとに、競わせたランキングを復元
    res = get_ranking()

    weight_vecs = []
    for i in range(ranker_size):
        ranker_id = i + 1
        w = np.array([_[-1] for _ in res if _[0] == ranker_id])
        weight_vecs.append(w)

    main_w = weight_vecs[0]
    # print("main weight: %s" % str(main_w))

    rankers = [Ranker(feature_ids, _w) for _w in weight_vecs]
    top_videos = get_top_videos_per_genre(conn, genre_id)
    rankings = [to_id(ranker.rank(top_videos)[:ranking_count_per_genre]) for ranker in  rankers]

    origin_rankings = get_origin_ranking()
    mixed_ranking = [_[1] for _ in origin_rankings]

    # 復元ランキング達とクリック結果からマルチリービングで優劣判断
    # rankingオブジェクトも復旧する必要がある
    ranking = PairwisePreferenceRanking(rankings, contents=mixed_ranking)

    # クリック対象IDを混合ランキングのインデックスに変換
    click_indexes = [mixed_ranking.index(vid) for vid in click_video_ids]

    result = PairwisePreference.evaluate(ranking, click_indexes)

    # 勝者ランカーを決定
    winner_indexes = get_superior_rankers([result])
    main_w = weight_vecs[0]

    # 重み更新(勝者ランキングに用いた単位ベクトルの平均値を加算)
    if winner_indexes:
        diff_vecs = np.array([w - main_w for w in weight_vecs])
        unit_vecs = diff_vecs / delta
        main_w += alpha * np.average(unit_vecs[winner_indexes], axis=0)

        # メイン重み更新

    return main_w

ここまで定義した関数を、後は順番に呼び出すだけという形になります。

if __name__ == "__main__":
    update_ranking(user, genre_id)
    clicked_video_ids = get_click_data(user, genre_id) #クリック結果を取得
    evaluate(user, genre_id, clicked_video_ids)

こちらのデモ実装におけるシミュレーションでは、

  • 素性数(ランキングの条件)は4つ
  • 生成するランキングのダミーアイテム数は50に固定
  • ダミーアイテムは、4つの素性値をランダム生成したものを事前に大量生成

という条件に基づいてランカー数をnに決定しています。

また、1回のイテレーションで、ユーザさんは提示されたランキング(50アイテム)の中から、 1つめの条件が大きいものを順に3つクリックしたと仮定しました。 それを50イテレーション(=1セット)繰り返した後、第一素性の重みを記録したうえで、さらに20セット繰り返して、最終的に1個目の素性重みの平均を取得し、 それをランカー数:nの場合の「最終第一条件の重み」として評価しました。

その結果、このシミュレーションでは、このようにランカー数:2~20に変化させて行ったところ、次のような結果が得られ、 十分な収束を確認することができました。

f:id:long10:20200626001413p:plain

ランキング評価エコシステム

それでは、このマルチリービングをどのようにクラシルのランキングに反映したかについてご紹介したいと思います。 この仕組み全体をランキング評価エコシステムと呼ぶことにします。 導入したクラシルの機能は、特定の検索キーワードに紐づいて表示されるテーマ別ランキング*8という機能になります。

f:id:long10:20200626112356p:plain

マルチリービングを用いたランキングを自動改善する流れは、このような流れになります。

  1. こちらのテーマ(殿堂入り、時短、子供が喜ぶなど)一つ一つについて、複数のランキング生成条件(視聴数、新しい順など)に基づくランキングをいくつか生成します。
  2. ユーザさんを行動に基づいていくつかのグループ(クラスタ)に分類します。
  3. 各クラスタごとに1で生成したランキングからごちゃ混ぜランキングを生成します。
  4. クラスタごとにそれぞれごちゃ混ぜランキングを表示します。
  5. 1週間経って、ユーザさんがクリックした結果を集計します。
  6. 集計結果から、ユーザさんがこの1週間でもっとも好んだランキング生成条件を評価します。
  7. ユーザさんが好んだランキングを考慮して、ごちゃ混ぜにする割合をちょっと変化させます。
  8. 変化した割合が反映された状態で、再びごちゃ混ぜランキングを生成します。

つまり、ランキングを複数作ってABテストを行い、ABテストの結果を反映したランキングを毎週自動で作ることで、 ほんのちょっとずつランキングを最適化していこうという作戦になります。

なお、この機能実装については、こちらの先行研究を参考に行いました。*9

先行研究でのアルゴリズム

f:id:long10:20200626114737p:plain

こちらの研究では、オンラインでの評価が対象となっていますが、これをそのままクラシルに適応してしまうと処理コストが高すぎるし、 食コンテンツというのは、ニュースコンテンツなどとは異なり即時性をそこまで求められないことから、 今回は1週間に1回更新するバッチ処理として導入することにしました。 また、先行研究のアルゴリズムはTDM(Team draft multileaving)が採用されていますので、PPMを用いている部分も異なっていると言えます。

それでは、ランキング自動改善エコシステムをより具体的にご紹介したいと思います。

全体概要

f:id:long10:20200626102810p:plain

ランキング自動改善エコシステムは、以下の5つのSTEPで構成されています。

1. aggregate ステップ

Athenaを経由して以下のデータ収集・集計を行う ユーザさんの行動から1週間分(起動当日-7日)の特徴量を収集・集計する 1週間分のクリック数をユーザごとジャンルごとに集計し保存する

2. user clustering ステップ

ユーザさんの行動状況から、ユーザさんをk個のクラスタに分類します。 このクラスタごとにランカー(ランキング生成器)を生成していきます。

3. create ranking ステップ

aggregate ステップで収集したデータに基づいて、複数のランキングを生成します。 ランキングを生成したのち、現状のランカーパラメータの保存を行います。 ランカーパラメータの状況に基づき混合ランキングを生成します。

4. evaluate ステップ

ユーザクラスタごとジャンルごとにランカーの評価を行い更新します。 勝者ランカーのパラメータに対し割合を調整して保存します。

5. load ステップ

生成した混合ランキングをDynamoDBに格納します。

難しかった点、課題について

こちらの実装期間については、加藤先生のご指導とモジュールのおかげで、5日ほどでサービスリリースすることができました。 リリースしたばかりなので適合率の評価などは実際まだこれからですが、 導入までの難しかった点としては、マルチリービングがいかに少数のサンプル数で収束効果があるとはいえ、 今回非常にニッチな機能なので、摂動の影響は非常に小さく、それほど大きな効果を得ることはできなそうという点があります。 また、当初ユーザごとにパラメタを調整する設計だったのですが、やはり処理コストが肥大化してしまうので、 今回は、初回導入ということでユーザクラスタ*10 に対するランカーパラメータにすることで処理コストを抑えました。 今後の課題としては、このエコシステムを改善していくことで、ランキングに限らず他機能のA/Bテストにも活用できるようにしていきたいと思っています。 また、ランカー数を増やしたり、摂動するハイパーパラメタをチューニングすることによってさらに最適なランキングを生成し、 可能な限りアローの不可能性定理に立ち向かっていきたいと考えています。

まとめ

いかがでしたでしょうか?
今回は、Pairwise Preference Multileavingという手法を用いてランキングのA/Bテストを行い、その結果を反映してランキングを勝手にどんどん最適化させるという手法について ご紹介させて頂きました。 実際、ユーザさんに満足してもらえるような適合率にしていくためには、まだまだこれから改善が必要になると思っていますが、 アローの不可能性定理に人海戦術で対応していくのは、その名の通り不可能なので、 こういった技術や工夫を用いてクラシルを利用してくださるユーザさんにもっともっと満足してもらえる機能を提供・改善していきたいと考えています。