Stack Overflowのアルゴリズム: ユーザ属性編

http://kevinmontrose.com/2015/01/27/providence-machine-learning-at-stack-exchange/

1 comment | 0 points | by WazanovaNews 約2年前 edited


Jshiike 約2年前 edited | ▲upvoteする | link

Stack Oveflowではサイトの各機能の精度をあげるために、「webエンジニア」「Javaテクノロジー」など、ユーザごとの属性ラベルを付与しています。ユーザは、そのデータをダウンロード、もしくはクエリされないように無効化することも可能です。この仕組みを構築したProvidenceプロジェクトを、同社のエンジニアであるKevin MontroseとJason Punyonが紹介しています。

1) 機械学習における最適なモデルの模索

まず把握したかったポイントは、

  • エンジニアのタイプにはどのようなものがあるか?
  • エンジニアは一つのタイプに特化しているものなのか?
  • タイプごとにサイトの利用形態は変わるのか?

Stack Oveflow Careersにある大量だが曖昧な表現の履歴書と求人データを眺めて、

  • フルスタックwebエンジニア
  • フロントエンドwebエンジニア
  • バックエンドwebエンジニア
  • Androidエンジニア
  • iOSエンジニア
  • DBアドミン

など、11種類のエンジニアタイプを定義した。

次に社内のエンジニアが手分けして、Stack Overflow Careersに登録しているユーザからランダムに抽出された1,237名に対して、手動でエンジニアタイプを当てはめた。その結果、エンジニアタイプにはある種の階層構造がざっくりと存在することがわかった。(階層とエンジニアタイプの概念図)メジャーなエンジニアタイプ階層は、web / モバイル / その他にわけることができる。それを考慮すると、最初にメジャーなエンジニアタイプの階層を検証し、それからマイナーな階層に進む仕組みとした。Stack Overflowのタグの閲覧データ(ユーザに閲覧された質問に付加されているタグを集計したデータ)を元に分析するので、階層別のタグの内訳を下記の通りにまとめてみた。

  • メジャーなエンジニアタイプ階層
    • Webプログラミング言語(java, c#, javascript, php等)
    • モバイルプログラミング言語(java, objective-c等)
    • 非WEB / 非モバイルプログラミング言語
    • iOSデバイス
    • Webテクノロジー(html, css等)
  • モバイルエンジニアタイプ階層
    • iOSデバイス関連(ios, objective-c等)
    • Android関連(android, listview等)
    • Windowsフォン関連
  • その他のエンジニアタイプ階層
    • Stack Overflow使われるTop 100のタグ
    • Top 100ののペアとなるタグ
    • SQL関連(sql, tsql等)
    • DB関連(mysql, postgressql等)
    • Linux/Unix関連(shell, bash等)
    • 数学関連(matlab, numpy等)

タグ閲覧データは総計ではなく、平均を算出してそこからの偏差を使うことが多い。機能によっては、 例えば、Webプログラミング言語のタグ閲覧データを、Webプログラミング言語、モバイルプログラミング言語、非WEB / 非モバイルプログラミング言語それぞれとの偏差を利用するケースもある。

次に、Stack Oveflow Careerの求人データから抽出し、

  • PHP
  • Ruby on Rails
  • Microsoft関連(ASP.NET, IIS等)
  • Node.js
  • Python関連(Django, Flask等)
  • Java関連(JSP, Struts等)
  • WordPress
  • クラウド関連(Azure, EC2等)
  • MySQL

など15種類のテクノロジーのラベルを定義した。iOSとAndroidが含まれていないのは、モバイルの場合は、エンジニアタイプが決まれば利用するテクノロジーもほぼ自明なので、抽出されなかったと考えられる。

特定のテクノロジーに紐づくタグや複数のテクノロジーにある比率で関連するタグが存在するという仮説を実証するために、まずは、「php / php-* / zend-frameworkはPHP」「ruby-on-rails / ruby-on-rails-* / active-recordはRuby On Rails」などの基本パターンを用意してから、機械学習で精度をあげた。

ノイズを取り除くために、テクノロジー毎のタグを500個に制限し、Stack Overflowの質問において使用数が0.05%以下のタグは排除した。

2) 求人バナーのクリックスルー率(CTR)での検証

各ユーザがStack Oveflow Careersに掲載されている求人内容にどれだけフィットするかを、各求人ポジションとユーザの相関値で計測する。

ユーザごとに、11個のエンジニアタイプの%ラベル、15個のテクノロジーの%ラベル、それらのラベルを設定するのに利用したタグの閲覧データの三つが存在する。

また求人ポジションごとに、望ましいエンジニアタイプとテクノロジーのリスト、関連するタグが設定されている。

求人内容が幅広すぎたり(例えば、「どのプラットフォームでもよいのでWebエンジニア」)とか、狭すぎたり(例えば、「この地域でASP.NET / MVC2 / EE4 / F#の経験のある人」)することを極力避ける。

一つのラベルの影響力が大きくなりすぎないようにし、その場合に選択されるべき別のラベルは何かを決めるアルゴリズムについては、リアルタイムで実行できるようにする必要がある。

  • 求人ポジションにない、そのユーザのエンジニアタイプとテクノロジーのラベルは考慮しないようにする。(Androidエンジニアが該当しない求人ポジションは、そのユーザのAndroidエンジニアのラベルを無視する。)
  • 残りのエンジニアタイプラベルのパーセントを足し合わせる
  • 残りのテクノロジーラベルのパーセントを足し合わせる。
  • ユーザにとって最もactiveで、かつ求人ポジションにも該当するタグを見つけ、それがタグのactivity全体の何%になるか計算する。
  • 上記三つのパーセントに対しそれぞれ、事前に用意した比重(パターン別の計算を繰り返して最適値を算出済: エンジニアタイプが1、テクノロジーが2、マッチしたタグが3)を反映させ、その結果を足し合わせる。
  • 結果の値を、ありえる最大値で割ることで相関値を計算する。つまり、完璧にフィットするユーザ像を定義し、そのユーザがどれだけその値に近いかを計算する仕組み。

ユーザの情報がない(オプトアウトしている。)もしくは求人ポジションの情報がない(入力内容が極端すぎたり、不備など)場合も、ランダムにサンプリングしたユーザのマッチの平均で30%-50%にあたる標準偏差に調整したものを利用している。

ユーザに求人広告バナーを掲載したときのCTRで検証している。

  • まず、エンジニアタイプ(メジャー/マイナー)ラベル、テクノロジーラベル、タグを個別にテスト。それから、相関値を地域別の出し分けも考慮してたうえで、A/Bテストする。
  • バグの影響を下げるため、ユーザへの露出率は段階的にアップ。
  • 特定の求人ポジションでのCTR改善が、別のポジションに極端な悪影響がでないことも確認。
  • 全体で27%の改善。

3) 日次の集計作業

HAProxyから取得した、時間 / リクエストURI / クエリstring / 各種のタイミング情報から構成されるログデータを日別に集計。過去6週間の範囲から計算した予測モデルを日次で更新している。

  • ProvinceクッキーGUID(非ログインユーザは、ランダムなGUIDに対して、無効になる期限をかなり先に設定したProvinceクッキーをセットしている。)とユーザログインIDのタイミングデータから、非ログインとログインユーザのアカウントの紐付けを実施。
  • タグ閲覧データ: ユーザ別に、閲覧した質問にあるタグを集計し、最新更新タイミングとともに、Redisインスタンスに保存。
  • タグ閲覧データが更新されたユーザのみ、予測モデルを再計算し、その結果をRedisに取り込む。New YorkのRedisインスタンスから、Oregonのインスタンスへのバックアップも実施。

4) 反省点

最初に仮で、1年間ユーザデータを保存し、15分ごとに予測モデルを再計算すると決めたが、その結果、Cassandraや未知のWindowsサーバアーキテクチャを採用することになった。その新しいテクノロジーが組み合わさった結果、既存の運営/検知ノウハウが活用できず、データセンタ全体の電源障害につながるバグを事前に察知できなかった。

[その他参照サイト]

http://kevinmontrose.com/2015/01/29/providence-what-technologies-do-you-know/

http://kevinmontrose.com/2015/02/04/providence-matching-people-to-jobs/

http://jasonpunyon.com/blog/2015/02/05/providence-testing-and-results/

http://jasonpunyon.com/blog/2015/02/10/providence-architecture-and-performance/

http://jasonpunyon.com/blog/2015/02/12/providence-failure-is-always-an-option/


2014 Topアクセスランキング


Back