LIVESENSE Data Analytics Blog

リブセンスのデータ分析、機械学習、分析基盤に関する取り組みをご紹介するブログです。

LivesenseDataAnalyticsBlog

MENU

CloudFormationでコンテナビルド用パイプラインをつくる

テクノロジカルマーケティング部の橋本です。 肩書的には分析基盤開発・保守を担当するエンジニアですが、近頃は基盤開発に限らず、データアナリストが推進するデータ活用施策をエンジニアの立場でサポートしており、施策実行のために必要となる周辺システムの開発も行っています。仕事とあらば、できる事はなんでもやります。

そんな中で、最近バッチ処理構築のお手伝いをすることが多かったのですが、そこで利用したCloudFormationを使ったコンテナビルド用パイプラインの取り回しが良かったので、こちらでご紹介しようと思います。

CloudFormation(以下、CFn)は、AWS謹製のInfrastructure as Codeのフレームワーク、およびマネージドサービスの名前です。特徴としては

  • AWSのサービスを記述するのに便利なAPI
  • 宣言的記述
  • 拡張多数(SAMなど)

と、Terraformの様に複雑なロジックや制御はできませんが、AWSで小〜中規模サービスを展開するには便利です。

背景

ディレクターやアナリストでもコードを書く!

弊社では「営業でもSQLを使う」という文化がありますが、アナリストや一部のディレクターはSQLだけでなくモデリング・スコアリングのためにRやPythonなどのコードを書いたりしています。これらのコードで有効性が期待されるものについては、そのまま実環境で試してみたいというニーズが当然のようにあり、そういう場合はバッチ処理の中でこれらのコードを動かすことになります。Cronで定時にキックするタイプの小粒なバッチ処理で、ワークフローエンジンを使う程ではないにしろ、定時にサービス各所からデータを集め、ディレクターやアナリストのロジックで加工・スコアリング等の処理を行い、それをプロダクトのDBに書き戻してサービス内で使う・・・といったものです。私がお手伝いしていたのは、そのコードが動く環境構築と基礎づくりで、それに対してディレクターやアナリストからPull Requestが飛んでくる・・・そんな状況でした。

でも、デプロイとか環境構築が・・・

ただ、それ専用にサーバを用意して、都度デプロイしたり保守運用するとエンジニアの手数の方が追いつかず・・・という場面がしばしばありました。コードが書けるとは言え、流石に非エンジニアの人達に本番サーバを操作する権限を与えて・・・というのも危険ですし、ランタイムのビルドやライブラリ依存関係が・・・アップデートが・・・と、それをディレクターやアナリストにやってもらうのも無理があります。都度デプロイ作業の手順書を・・・なんてやってられません。また、この状況だとアナリストも気軽にバッチ処理を追加したいと言い出しづらく、試行錯誤の回数が制限されてしまう可能性があります。データ活用においてこの状況は致命傷になりかねません。 ということで、アナリストやディレクターがPoCレベルの実装を安全に実環境でテストでき、かつ、エンジニアの負荷をかけずに済むように簡単・安全にデプロイできるしくみを作りたいというのが今回の背景にあったニーズです。

つくるもの・できるようになること

上記背景を受けて、Githubへのpushによってキックされ、変更入りのイメージがECRに自動でpushされる素朴なコンテナCDパイプラインを作ってみました。これをCronキックの都度イメージの更新を確認してサーバで走らせれば、ロジックの変更もランタイムのアップデートも、Githubにpushするだけで変更が本番環境に適用されます。

今回つくるパイプラインは以下の構成で、AWSのリソースはCFnテンプレートとして記述していきます。

f:id:livesense-analytics:20190627171857j:plain
cfn

こうすることで、

  • バッチ処理のコード、ロジックはすべてGithubで管理できる
    • コーダーはGithubの所定のブランチへ変更をpushすればよいだけになる
  • CronサーバにはdockerとAWS CLIがインストールされ、クレデンシャルが配置されていればOK
    • 他は特にいらない
    • バッチ処理毎にランタイムやライブラリも自由に選べ、アップデートも比較的気楽にできる
  • パイプラインはCFnテンプレートで記述されているので
    • 同じ仕組みの横展開、撤収が容易にできる
    • 部署間でのエンジニアへの技術協力、仕組みの譲渡が容易にできる

などなど、とても便利です。特に、

  • コーダーの関心がGithubまでで完結し、デプロイ、リリースを気にしなくてよくなる
  • ランタイム環境の影響範囲がコンテナに閉じる
  • Infrastructure as Codeとして、仕組みがポータブルに受け渡しできる

といった辺りのメリットが好評でした。

用意するもの

  • パイプラインを構築する AWSアカウントと、Administrator権限を持ったIAMユーザ
    • rootユーザでの操作は危険なのでやらないこと
  • Githubアカウントとリポジトリ
  • バッチ処理を走らせるCronサーバ
    • dockerとAWS CLIがインストールされていること
    • デプロイユーザのクレデンシャルがインストールされていること

CFnによって作成されるリソースは

  • CodeBuildプロジェクト
  • ECRリポジトリ
  • IAMロール
    • CodeBuildにアタッチする
  • CloudWatch Logs ロググループ
    • CodeBuildのログを出力する

となります。それから別途、

  • IAMユーザ(Cronサーバのデプロイユーザ)

を作成しておく必要があります。

実装

CFn

今回のテンプレートは、全てyaml形式で書いていきます。

先ず、nested stackの大枠から。

AWSTemplateFormatVersion: "2010-09-09"
Description: Build Pipeline for xxxx Container
Resources:
  EcrRepos:
    Type: "AWS::CloudFormation::Stack"
    Properties:
      TemplateURL: "https://s3.amazonaws.com/hoge-cloudformation-templates/xxxx/ecr-repos.yml"
  BuildLogs:
    Type: "AWS::CloudFormation::Stack"
    Properties:
      TemplateURL: "https://s3.amazonaws.com/hoge-cloudformation-templates/xxxx/build-logs.yml"
  IAMRoles:
    Type: "AWS::CloudFormation::Stack"
    Properties:
      TemplateURL: "https://s3.amazonaws.com/hoge-cloudformation-templates/xxxx/iam-roles.yml"
    DependsOn: 
      - EcrRepos
      - BuildLogs
  CodeBuildProjects:
    Type: "AWS::CloudFormation::Stack"
    Properties:
      TemplateURL: "https://s3.amazonaws.com/hoge-cloudformation-templates/xxxx/codebuild.yml"
    DependsOn: IAMRoles

今回のスタックは2段にネストされており、スタック全体をまとめる上の階層のスタックがコレです。書いてあるとおり、それぞれ

  • ECRリポジトリ
  • CloudWatch Logsロググループ
  • IAMロール
  • CodeBuildプロジェクト

の、テンプレートが呼び出されています。スタック全体を作成・更新する際には、このyaml(main.yml)を

aws cloudformation deploy --template ./main.yml --stack-name xxxx-build --capabilities CAPABILITY_NAMED_IAM

のようにして呼び出して使うことになります。この時、各サブスタックのテンプレートとなるyamlは、予めS3の所定のバケットに配置されていなければなりません。こんな感じでupload.shを作り、それをテンプレート更新の都度、aws cloudformation deployの前に使う必要があるので注意です。これを忘れてしまうと、テンプレートが更新されないままdeployが走ってしまいます。

BUCKET=s3://hoge-cloudformation-templates/xxxx
aws s3 cp ecr-repos.yml ${BUCKET}/ecr-repos.yml
aws s3 cp build-logs.yml ${BUCKET}/build-logs.yml
aws s3 cp iam-roles.yml ${BUCKET}/iam-roles.yml
aws s3 cp codebuild.yml ${BUCKET}/codebuild.yml

S3のバケット名は任意のものを使って下さい。

依存関係をもつスタックにはDependsOn属性が設定されており、依存するスタックの名前が書かれています。これが設定されているスタックは、依存するスタックが作成された後に作成が開始されます。上記スタックが依存している内容は、後ほど具体的に確認していきます。

次に、ECRリポジトリのスタック(ecr-repos.yml)を見ていきます。

AWSTemplateFormatVersion: "2010-09-09"
Description: ECR Repository for xxxx
Resources:
  xxxxECR:
    Type: "AWS::ECR::Repository"
    Properties:
      RepositoryName: xxxx
Outputs:
  xxxxECRArn:
    Value: !GetAtt xxxxECR.Arn
    Export:
      Name: xxxx-ECR
  xxxxECRName:
    Value: !Ref xxxxECR
    Export:
      Name: xxxx-ECR-Name

Resourcesフィールドには、作成されるリソースについて記述されています。ここではxxxxという名前のECRリポジトリを作成しています。

Outputsフィールドには、このスタックについて他のスタックから外部参照される変数の名前と値が書かれています。例えば、xxxxECRArnフィールドの記述によって、CFnにxxxx-ECRという論理名の変数が作成され、その値は!GetAtt関数でxxxxECR.Arnの値が設定されます。これは、xxxxECRリソース(ECRリポジトリ)のARN(AWS Resource Names)になっていて、このスタックの作成が完了すると、外部のスタックからは!ImportValue関数と論理名(xxxx-ECR)でこのECRリポジトリのARNにアクセスできるようになります。こんな感じです。

- !ImportValue xxxx-ECR

この外部参照の使い方は、後に紹介するスタックでまた確認します。

次は、CodeBuildがログを排出するCloudWatch Logs ロググループのスタックです。

AWSTemplateFormatVersion: "2010-09-09"
Description: CloudWatchLogs for xxxx CodeBuild
Resources:
  xxxxBuildLogs:
    Type: "AWS::Logs::LogGroup"
    Properties:
      LogGroupName: xxxx-build
      RetentionInDays: 60
Outputs:
  xxxxBuildLogsArn:
    Value: !GetAtt xxxxBuildLogs.Arn
    Export:
      Name: xxxx-CloudWatchLogs-BuildLogGroup
  xxxxBuildLogsName:
    Value: !Ref xxxxBuildLogs
    Export:
      Name: xxxx-CloudWatchLogs-BuildLogGroup-Name

こちらもecr-repos.ymlと、ほぼ同様の構成です。

次に、CodeBuildプロジェクトにアタッチする各種権限(IAMロール)のスタックです。このスタックでは、作成したIAMロールに、以下のポリシーをアタッチしています。

  • ビルドしたイメージを格納するECRリポジトリの読み書き権限
  • ビルド時のログを格納するCloudWatchLogsログストリームを、xxxx-CloudWatchLogs-BuildLogGroupロググループに作成する権限
  • xxxx-CloudWatchLogs-BuildLogGroupロググループのログストリームに、ログを書き込む権限
AWSTemplateFormatVersion: "2010-09-09"
Description: IAM Role for xxxx CodeBuild
Resources:
  RoleCodeBuild:
    Type: "AWS::IAM::Role"
    Properties:
      RoleName: xxxx-codebuild
      AssumeRolePolicyDocument:
        Version: 2012-10-17
        Statement:
          - Effect: Allow
            Principal:
              Service: "codebuild.amazonaws.com"
            Action: "sts:AssumeRole"
      Policies:
        - PolicyName: xxxx-codebuild-role
          PolicyDocument:
            Version: 2012-10-17
            Statement:
              - Effect: Allow
                Action:
                  - "ecr:GetDownloadUrlForLayer"
                  - "ecr:BatchGetImage"
                  - "ecr:BatchCheckLayerAvailability"
                Resource:
                  - !ImportValue xxxx-ECR
              - Effect: Allow
                Action:
                  - "ecr:CompleteLayerUpload"
                  - "ecr:InitiateLayerUpload"
                  - "ecr:UploadLayerPart"
                  - "ecr:PutImage"
                Resource:
                  - !ImportValue xxxx-ECR
              - Effect: Allow
                Action:
                  - "ecr:GetAuthorizationToken"
                Resource:
                  - "*"
              - Effect: Allow
                Action:
                  - "logs:CreateLogStream"
                  - "logs:PutLogEvents"
                Resource:
                  - !ImportValue xxxx-CloudWatchLogs-BuildLogGroup
                  - !Join
                    - ":"
                    - - !ImportValue xxxx-CloudWatchLogs-BuildLogGroup
                      - "log-stream:*"
Outputs:
  RoleARN:
    Value: !GetAtt RoleCodeBuild.Arn
    Export:
      Name: xxxx-Role-CodeBuild

iam-roles.ymlでは、ecr-repos.ymlbuild-logs.ymlで作成した論理名の変数を!ImportValueで参照しています。こうすることで、予め作成されたリソースの属性値を参照し、スタックの定義に用いることができます。この論理名は、テンプレートが実行される前にCFnに定義されている必要があり、順番を違える(CFnに論理名が未定義のままテンプレートを実行してしまう)と参照エラーになってスタックの作成が止まってしまいます。main.ymlDependsOn属性を設定したのはこのためです。

最後に、CodeBuildプロジェクトのスタックです。

AWSTemplateFormatVersion: "2010-09-09"
Description: CodeBuild Project for xxxx Container
Resources:
  xxxxCodeBuild:
    Type: "AWS::CodeBuild::Project"
    Properties:
      Name: !ImportValue xxxx-ECR-Name
      Artifacts:
        Type: NO_ARTIFACTS
      Environment:
        Type: LINUX_CONTAINER
        Image: "aws/codebuild/docker:18.09.0"
        ComputeType: BUILD_GENERAL1_SMALL
        EnvironmentVariables:
          - Name: IMAGE_REPO_NAME
            Type: PLAINTEXT
            Value: !ImportValue xxxx-ECR-Name
          - Name: AWS_ACCOUNT_ID
            Type: PLAINTEXT
            Value: !Ref "AWS::AccountId"
      ServiceRole: !ImportValue xxxx-Role-CodeBuild
      Source:
        Type: GITHUB
        GitCloneDepth: 1
        Location: "https://github.com/path/to-your-project-repo"
      Triggers:
        Webhook: true
      LogsConfig:
        CloudWatchLogs: 
          Status: ENABLED
          GroupName: !ImportValue xxxx-CloudWatchLogs-BuildLogGroup-Name

これで、AWSにコンテナビルドのパイプラインが作成されます。

Githubリポジトリ

ビルドの対象になるGithubリポジトリのコードには、CodeBuildが実行するビルドの手順を記したbuildspec.ymlを、リポジトリのルートに配置します。こんな感じです。

version: 0.2

phases:
  pre_build:
    commands:
      - echo Logging in to Amazon ECR...
      - $(aws ecr get-login --no-include-email --region $AWS_DEFAULT_REGION)
  build:
    commands:
      - echo Build started on `date`
      - echo Building the Docker image...          
      - IMAGE_TAG=`echo $CODEBUILD_WEBHOOK_TRIGGER | awk -F/ '{print $2}' | sed 's/master/latest/'`
      - docker build -t $IMAGE_REPO_NAME:$IMAGE_TAG .
      - docker tag $IMAGE_REPO_NAME:$IMAGE_TAG $AWS_ACCOUNT_ID.dkr.ecr.$AWS_DEFAULT_REGION.amazonaws.com/$IMAGE_REPO_NAME:$IMAGE_TAG      
  post_build:
    commands:
      - echo Build completed on `date`
      - echo Pushing the Docker image...
      - docker push $AWS_ACCOUNT_ID.dkr.ecr.$AWS_DEFAULT_REGION.amazonaws.com/$IMAGE_REPO_NAME:$IMAGE_TAG

これで、CodeBuildでビルドされたイメージが、CFnで設定したECRリポジトリにpushされます。

Cronサーバ

Cronサーバでは、実行の都度、docker pullした後にdocker runします。こんな感じのシェルスクリプトを毎回実行します。

export AWS_CONFIG_FILE=/home/xxxx/.aws/config
export AWS_SHARED_CREDENTIALS_FILE=/home/xxxx/.aws/credentials
IMAGE="xxxxxxxxxx.dkr.ecr.ap-northeast-1.amazonaws.com/xxxx:latest"
$(aws ecr get-login --region ap-northeast-1 --no-include-email)
docker pull ${IMAGE}
docker run --rm --env-file=prod.env ${IMAGE}

クレデンシャルは、デプロイユーザを作成してアクセスキー、シークレットアクセスキーを発行して下さい。CFnでパイプラインのスタックを作成した後、下記の要領でテンプレートを実行し、IAMユーザを作成します。

AWSTemplateFormatVersion: "2010-09-09"
Description: IAM Users and Group for xxxx
Resources:
  DevelopersGroup:
    Type: "AWS::IAM::Group"
    Properties:
      GroupName: xxxx-developers
      Policies:
        - PolicyName: xxxx-developers-policy
          PolicyDocument:
            Version: 2012-10-17
            Statement:
              - Effect: Allow
                Action:
                  - "ecr:BatchCheckLayerAvailability"
                  - "ecr:GetDownloadUrlForLayer"
                  - "ecr:GetRepositoryPolicy"
                  - "ecr:DescribeRepositories"
                  - "ecr:ListImages"
                  - "ecr:DescribeImages"
                  - "ecr:BatchGetImage"
                Resource:
                  - !ImportValue xxxx-ECR
              - Effect: Allow
                Action:
                  - "ecr:GetAuthorizationToken"
                Resource:
                  - "*"
   DeployUser:
    Type: "AWS::IAM::User"
    Properties:
      Groups:
        - !Ref DevelopersGroup
      UserName: xxxx_deploy

一応グループも作ったので、後からここへIAMユーザを追加することもできます。

作業手順

  1. Githubリポジトリを作り、buildspec.ymlをmasterブランチのルートディレクトリに入れておく
  2. CodeBuildにOAuthを通しておく(次の項に記載)
  3. CFnテンプレートを適用する
  4. CodeBuildのbranch filterを設定しておく(「ちょっとだけ便利にしておく」に記載)
  5. デプロイユーザのIAMユーザを作り、クレデンシャルを発行しておく
  6. デプロイユーザのクレデンシャルを使って、Cronをサーバに設定する

使用方法

使用前に

CFnの操作はAdministrator権限のIAMユーザで行う

CFnがテンプレートにより実行するAWSへの操作については、CFnを実行したユーザの権限が引き継がれます。適切な権限がないとリソースの作成、変更に失敗するので、基本的にはAdministrator権限のユーザでしましょう。もしAdministrator権限が強力過ぎるとか、得られないような場合には、リソース管理に必要なPolicyを適切にアタッチしたユーザでCFnの操作をしなければなりません。

CodeBuildにデプロイユーザのGithubアカウントでOAuthを通しておく

CodeBuildがGithubにアクセスする際のアカウントを設定します。残念ながらこれはWebコンソールからしか実行できないようです。1回だけ設定しておけば、接続を解除しない限り再設定は不要です。

先ず、Administrator権限のIAMユーザで、CodeBuildを開いて、「ビルドプロジェクトを作成する」をクリック。

f:id:livesense-analytics:20190624171052p:plain
「ビルドプロジェクトを作成する」を選ぶ

「送信元」カードの「ソースプロバイダ」を、「Github」にして、「リポジトリ」の項目で「OAuthを使用して接続する」を選択し、「GitHubに接続」ボタンを押す。

f:id:livesense-analytics:20190624171117p:plain
GitHubに接続

するとGitHubのドメインにリダイレクトされるので、デプロイユーザアカウントで、OAuth認証を行う。

f:id:livesense-analytics:20190624171503p:plain
OAuth認証

ここまでの手順でCodeBuildの画面に戻ってくるので、そのままビルドプロジェクト作成をキャンセルすればOKです。

テンプレートを配置するバケットを作成しておく

任意のバケット名で作成して下さい。これも、最初に1度だけ行えばOKです。

aws s3 mb s3://hoge-cloudformation-templates/

スタック作成・更新

ここまでくれば、あとはコマンド一発です。ポチッとな。

./upload.sh
aws cloudformation deploy --template ./main.yml --stack-name xxxx-build --capabilities CAPABILITY_NAMED_IAM

スタックの作成に失敗した場合は、一旦スタックを削除して作り直して下さい。

aws cloudformation delete-stack --stack-name xxxx-build

スタック削除時の注意点

  • ECRにイメージが残っていると失敗します。イメージは全て削除して下さい。
  • CloudWatch Logsロググループに、ログストリームが残っていると失敗します。ログストリームは全て削除してください。
  • IAMロールにポリシーがアタッチされていると失敗する時があります。その場合は、ロールのポリシーを全てデタッチしてからdeleteして下さい。

ちょっとだけ便利にしておく

f:id:livesense-analytics:20190624171703p:plain
プライマリソースのウェブフックイベント

  1. CodeBuildの作成したビルドプロジェクトの画面で、「ビルドの詳細」タブを選択
  2. 「送信元」カードが現れるので、「編集」をクリック
  3. 「プライマリソースのウェブフックイベント」カードが現れるので・・・
    • 「イベントタイプ」をプッシュのみ選択
    • 「これらの条件でビルドを開始する」の「HEAD_REF」に^refs/(tags/(v\d\.\d|dev)|heads/master)$と入力しておく
  4. 「ソースの更新」をクリック

こうすると、

  • masterブランチにpushがあった時にビルド
  • v*.*devというタグが打たれた時に、そのブランチをビルド

という挙動にできます。

あと、何回も作成と削除を試していると、こんなのにも遭遇するので参考まで。

補足

IAMユーザはスタックとは別に管理

今回、パイプラインのスタックとは別にIAMユーザのスタックを作成しましたが、これは、IAMユーザに別のスタックに対する権限等をアタッチする場合を考えてのものです。例えば、前項で作成したIAMユーザに別リポジトリのアクセス権限を出したければ、論理名でこんな感じに追加してスタックを更新するだけで簡単に権限を追加できます。

                  - "ecr:DescribeRepositories"
                  - "ecr:ListImages"
                  - "ecr:DescribeImages"
                  - "ecr:BatchGetImage"
                Resource:
                  - !ImportValue xxxx-ECR
                  - !ImportValue yyyy-ECR   <-- こんな感じ

IAMユーザは、パイプラインのスタックとは独立して作成し、後から依存するリソースへの参照を入れてやる・・・という作業順序になります。

更に・・・

今回はプロジェクト名をxxxxとしてハードコーディングしましたが、コレをパラメータで抽象化し、汎化することができます。この時、Outputの論理名がCFn全体で重複してしまうとダメなので、Outputの論理名自体にパラメータを入れてやる必要があり、若干工夫が必要になります。長くなるので説明を省きますが、コードだけ書くと

出力側

Parameters: 
  ProjectName: 
    Type: String
    Default: xxxx
...
Outputs:
  ECRArn:
    Value: !GetAtt ECR.Arn
    Export:
      Name: !Sub "${ProjectName}-ECR"

参照側

Parameters: 
  ProjectName: 
    Type: String
    Default: xxxx
...
  Resource:
    Fn::ImportValue: !Sub "${ProjectName}-ECR"

として、こんな感じに呼び出してやります。

aws cloudformation deploy --template ./main.yml \
--stack-name zzzz-build \
--capabilities CAPABILITY_NAMED_IAM \
--parameter-overrides \
ProjectName=zzzz

おわりに

今回ご紹介したのは、データエンジニアリング特有の技術というわけではありませんが、リブセンスではこういった技術も随時活用して、アナリストやディレクターが自分たちの作ったロジックを試しやすい環境、ビジネスにおけるデータ活用を簡単で安全に推進できる環境作りに力をいれています。

所々躓きポイントがあり、使い慣れるまで若干修行感のあるCFnですが、使い慣れてくると記述が単純なので楽です。もっとも、スマートな記述、美しいコード・・・とかいう世界とは無縁の泥臭い感じになるので、スタックを立てては消し、立てては消し・・・という職人的コーディング作業になります。こういうのが楽しめる感じになってくると、手の混んだ芸術的テンプレがムクムクと育って・・・。Systems Manager パラメータストアなんて機能もあるので、こんなので外部から設定を注入するとか、まだまだ色々できそうです。

「小〜中規模サービスを展開するには便利」と書きましたが、大規模インフラの記述もやってできない事はないと思います。ただし、上記の規模でもそれなりに煩雑なので、1つのスタックで記述するのが難しいと感じる程度までインフラが育ったら、そこがサブスタック分割のポイントと考えるのが良さそうです。単純・素朴を常に心がけてインフラを育てたいものです。

CFnで、ぜひお手軽IaCを楽しんで下さい。

Factorization Machinesをレコメンデーションで使うときの評価推定値計算

こんにちは、リブセンスで統計や機械学習関係の仕事をしている北原です。今回はレコメンデーションで使う評価推定値計算の効率化に関する小ネタです。機械学習を実務で使うときのちょっとした工夫に関するお話です。実装にはJuliaを使います。

FM(Factorization Machines)をレコメンデーションで使う場合、各ユーザーに対してレコメンド可能なアイテムの評価推定値計算を行うため、ユーザー数とアイテム数が多くなると非常に計算時間がかかります。学習データで交差検証をしたりコンペで使ったりしているだけだとあまり問題にならないのですが、実務では結構問題になります。こういうのは実務の現場で個別に対処されているためか知見もあまり公開されていないようです。対処方法はいろいろあるのですが、ここでは計算方法を少し工夫することで計算量を削減する簡単な方法を紹介します。合わせて計算量の見積もりや計算量削減の考え方、アルゴリズム実装のコツについてもお伝えできればと思います。

ユーザーベース協調フィルタリングの評価推定値計算

ユーザーベース協調フィルタリングを利用してレコメンデーションを行う場合、ユーザーとアイテムの組み合わせごとに評価推定値を計算し、各ユーザーに対して評価推定値が高いアイテムをレコメンドするのが一般的です。そのため、ユーザー数やアイテム数が多いと計算量が多くなり、実務でレコメンデーションを利用するときに計算時間が問題になることがよくあります。交差検証で精度が高そうだったから運用にのせようと考えて、一通りのレコメンデーション処理をやってみたら推定値計算に時間がかかりすぎることに気がついた、といったこともあるのではないでしょうか。学習は高速なので交差検証などを行っている範囲では計算時間の問題に気づきにくいのです。

まず、評価推定値計算に必要なデータ量について考えてみましょう。弊社サービスの場合、ユーザー数、アイテム数とも、多くとも数十万程度を見込んでおけばよいのでデータ量はそれぞれ$O(10^5)$です。したがって、組み合わせの数は$O(10^{10})$となります。つまり、評価推定値計算のデータ量は$O(10^{10})$です。評価データとして、口コミ評点や応募、求人詳細ページ閲覧を使った場合、1ユーザーあたりの評価データ数の平均はせいぜい$O(10)$ぐらいです。そのため、学習データとして使われる評価データ数のオーダーは$O(10^6)$になります。学習時と推定値計算時とでは1サンプルデータあたりの計算量が異なるので単純比較はできないものの、データ数が一万倍も多いのであれば、学習時だけでなく推定値計算時の計算量についても配慮が必要ではないかと予想がつきます。レコメンデーションを使いたい場面では、多くの場合1ユーザーあたりの評価データ数はユニークアイテム数より十分小さいので、評価推定値の計算量は弊社に限らず問題になりやすいのではと思います。

対処方法はいろいろあるものの、代表的な方法は、運用の工夫、並列・分散処理の利用、計算量改善の三つです。どれか一つしか使えないわけではなく組み合わせて使うこともできるので、組み合わせるのが一般的です。

運用の工夫としては、レコメンデーション効果の低い組み合わせを計算しないようにする方法があります。例えば、求人サイトの場合、会員登録時に希望職種や希望勤務地を入力してもらうことが多いので、希望と合致する求人しかレコメンドしないように制限する方法が考えられます。この方法は簡単でよく使われているのですが、希望職種や希望勤務地が適切に登録されてないと見逃しが発生してしまうという問題があります。同じような業務内容なのに異なる職種として登録されている求人はレコメンドされませんし、希望勤務地の隣接地域に非常にマッチする求人があってもレコメンドされません。制限を強めると見逃しが多くなる一方で、弱めると組み合わせが多くなるのでバランスをとる必要があります。

並列・分散処理の利用はいうまでもないですね。単純に組み合わせが多いだけで独立して計算可能な部分が多いので並列・分散処理を使うのは容易です。高性能なインスタンスや分散処理システムを利用するなどスケールさせるのも比較的簡単です。しかし、並列・分散処理だけで解決しようとすると計算機リソースを消費しすぎてコストがかかるという問題もあります。

計算量改善は計算式を整理して計算量を削減する方法です。計算式をうまく整理できると実装変更以外のコストをかけずに計算時間を短縮することができます。ただし、アルゴリズムやモデルによっては使えないこともあります。シミュレーションなどの数値計算や、最適化、機械学習などのアルゴリズム実装をすることが多い人にとっては、計算式を整理して効率的な計算ができるようにするのは当たり前のことなので、ノウハウが公開されることは少ないです。

Factorization Machinesの評価推定値計算

それでは、FMで評価推定値計算するときの計算量について考えてみましょう。

まず、評価推定値計算時のFMについて説明します。学習時は評価済みデータからモデルパラメータを推定しますが、評価推定値計算時はユーザーコンテキストとアイテムコンテキストを組み合わせたデータの評価推定値を計算します。ユーザー数を$s^u$、アイテム数を$s^i$とすると、$s=s^u s^i$の評価推定値を計算します。全コンテキスト数(特徴量数)を$n$、因子数を$k$とし、評価推定値$\hat{\mathbf{y}} \in {\mathbb R}^{s}$、評価と対応するコンテキストデータ${\bf X} \in{\mathbb R}^{s \times n}$(1サンプルのコンテキストは$\bf{x}$と表記)、モデルパラメータ$w_0 \in {\mathbb R}$、${\bf w} \in {\mathbb R}^n$、${\bf V} \in {\mathbb R}^{n \times k}$を使って、評価推定値$\hat{y}$は

$$ \begin{eqnarray} \hat{y}({\bf x}) &=& w_0 + \sum^n_{j=1}{w_j x_j} + \sum^n_{l=1}\sum^n_{j=l+1}{\hat{w}_{l, j} x_l x_j} \label{eq:fm} \\ \hat{w}_{l, j} &=& \sum^k_{f=1}{v_{l,f} v_{j,f}} \label{eq:w} \end{eqnarray} $$

と計算できます。評価推定値計算時にはモデルパラメータ$w_0$、$\bf{w}$、$\bf{V}$は既知です。コンテキスト$\bf{X}$はユーザーに関するコンテキスト${\bf X}^u \in{\mathbb R}^{s \times n^u}$とアイテムに関するコンテキスト${\bf X}^i \in{\mathbb R}^{s \times n^i}$が連結されたもの${\bf X} = [{\bf X}^u \, {\bf X}^i]$になっています。ここで$n^u$と$n^i$はそれぞれユーザーとアイテムのコンテキスト数で$n=n^u+n^i$です。それに対応し、モデルパラメータも${\bf w}^u \in {\mathbb R}^{n^u}$、${\bf w}^i \in {\mathbb R}^{n^i}$、${\bf w} = [{\bf w}^u \, {\bf w}^i]$、${\bf V}^u \in {\mathbb R}^{n^u \times k}$、${\bf V}^i \in {\mathbb R}^{n^i \times k}$、${\bf V}=\begin{bmatrix}{\bf V}^u \ {\bf V}^i \end{bmatrix}$と表記します。

このまま計算すると計算量は$O(s^u \, s^i \, k \, (n^u + n^i)^2)$になりますが、交互作用項を変形した

$$ \begin{eqnarray} \hat{y}({\bf x}) &=& w_0 + \sum^n_{j=1}{w_j x_j} + \frac{1}{2} \sum_{f=1}^{k}\left(\left(\sum_{j=1}^{n} v_{j, f} x_{j}\right)^{2}-\sum_{j=1}^{n} v_{j, f}^{2} x_{j}^{2}\right) \label{eq:fm2} \end{eqnarray} $$

を使うと、計算量は$O(s^u \, s^i \, k \, (n^u + n^i))$になります。FMでレコメンデーションを行うときのコンテキストデータはスパースなので、1ユーザーあるいは1アイテムあたりのコンテキストの非ゼロデータ個数を$\overline{m}^u$、$\overline{m}^i$とすると、計算量は$O(s^u \, s^i \, k \, (\overline{m}^u + \overline{m}^i))$となります。

では具体的な計算量がどのくらいになるか考えてみましょう。弊社の場合だと、ユーザー数とアイテム数はそれぞれ数十万程度を見込んでおけばよいので$s^u \sim O(10^5)$、$s^i \sim O(10^5)$、因子数は多くとも数百程度とすると$k \sim O(10^2)$、コンテキストの非ゼロデータ個数は、会員登録情報など簡単な前処理だけで使えるデータであればせいぜい数十、求人詳細テキストなどを使う場合でも数百程度に収まると考えると$\overline{m}^u + \overline{m}^i \sim O(10^2)$になります。そうすると、計算量は$O(s^u \, s^i \, k \, (\overline{m}^u + \overline{m}^i)) \sim O(10^{14})$になります。かなり大きそうですが比較対象がないとわかりにくいですね。

そこで、学習時と比較してどのぐらいの計算量になるか考えてみましょう。以前の記事でFMのモデルパラメータをAlternating Least Squares(ALS)で推定する方法を紹介したので、それと比較します。学習時の計算量は、評価数$s$、因子数$k$、1モデルパラメータに対応する非ゼロデータ個数の平均を$\overline{m}_C$とすると$O(s \, k \, \overline{m}_C)$でした。弊社サービスの場合、1ユーザーあたりの平均評価数は$O(10)$程度なので$s \sim O(10^6)$ になります。ユーザーIDやアイテムID以外のコンテキストが極端に多くなければコンテキスト数$n$はユーザー数$s^u$やアイテム数$s^i$とほぼ同じオーダーになるので$n \sim O(10^5)$です。1モデルパラメータに対応する非ゼロデータ個数$\overline{m}_C$と1データあたりのコンテキストの非ゼロデータ個数$\overline{m}^u + \overline{m}^i$との比は、評価数の逆数$1/s$とコンテキスト数の逆数$1/(n^u + n^i)$との比と等しくなるので、$\overline{m}_C \sim O(10)$になります。そのため、学習時の計算量は$O(s \, k \, \overline{m}_C) \sim O(10^{9})$となります。つまり、弊社の場合、学習時と比較して評価推定の計算量は十万倍程度になります。学習は一分で終わっても評価推定計算にはおよそ七十日かかるので、並列・分散処理で十倍程度高速化しても一週間はかかります。求人サービスの場合は求人の入れ替わりが激しいので、時間をかけて高精度なモデルを作るより頻繁にモデルを更新して新しい求人をレコメンドできるようにしたほうがよいことが多いです。そのため、これぐらい計算時間がかかると運用上のボトルネックになってしまいます。

特徴量作成を行う立場からも考えてみましょう。レコメンデーションの精度を上げるためには、有用なコンテキスト情報を増やす必要があります。求人サービスの場合、希望勤務地などの会員情報や年収などの求人情報だけでなく、求人詳細テキストから自然言語処理を利用して作成した特徴量やユーザーが過去に閲覧した求人や閲覧傾向の変化などレコメンデーションに有用と思われる情報は数多くあります。そのため、コンテキストを増やしていきたいですが、評価推定値の計算時間も増えてしまうので容易には増やせないというジレンマが生まれてしまいます。

事前計算による計算量削減

それでは、本記事のテーマである計算量削減方法について説明します。

基本的な考え方は非常にシンプルで、繰り返し同じ計算をする部分については一回計算したらその値を記憶しておき繰り返し使い回すことで計算量を削減します。式($\ref{eq:fm}$)に含まれる計算の中で繰り返し同じ計算をする部分というのは、ユーザーあるいはアイテムに関するモデルパラメータとコンテキストデータのみで計算できる部分です。

計算量削減のコツは課題を定式化して改善可能な部分を明確にすることです。そこで、まずユーザーとアイテムの違いがわかるように式($\ref{eq:fm}$)を書き直してみましょう。前節で導入した表記を使うと式($\ref{eq:fm}$)は

$$ \begin{eqnarray} \hat{y}({\bf x}) &=& w_0 + \sum^{n^u}_{j=1}{w^u_j x^u_j} + \sum^{n^i}_{j=1}{w^i_j x^i_j} + \sum^{n^u}_{l=1}\sum^{n^u}_{j=l+1}{\hat{w}^{u}_{l, j} x^u_l x^u_j} + \sum^{n^i}_{l=1}\sum^{n^i}_{j=l+1}{\hat{w}^{i}_{l, j} x^i_l x^i_j} + \sum^{n^u}_{l=1}\sum^{n^i}_{j=1}{\hat{w}^{u,i}_{l, j} x^u_l x^i_j} \label{eq:fm3} \\ \hat{w}^u_{l, j} &=& \sum^k_{f=1}{v^u_{l,f} v^u_{j,f}} \label{eq:w_u} \\ \hat{w}^i_{l, j} &=& \sum^k_{f=1}{v^i_{l,f} v^i_{j,f}} \label{eq:w_i} \\ \hat{w}^{u,i}_{l, j} &=& \sum^k_{f=1}{v^u_{l,f} v^i_{j,f}} \label{eq:w_ui} \end{eqnarray} $$

と書くことができます。和の記号の範囲や上付き添字で示されたユーザーとアイテムの違いに注意してください。式($\ref{eq:fm3}$)の右辺第6項のみがユーザーとアイテムの組み合わせになっており、それ以外はユーザーのみあるいはアイテムのみのデータで計算可能で、事前に一回計算して結果を記憶しておけば$O(1)$で計算できることがわかります。式($\ref{eq:fm3}$)の右辺第6項をそのまま計算すると計算量は$O(k \, n^u \, n^i)$、スパースなことを考慮すると$O(k \, \overline{m}^u \, \overline{m}^i)$となり計算量が小さいとは言い難いので、ここが改善ポイントではないかと予想がつきます。

念のため、式($\ref{eq:fm3}$)の第4項、第5項の計算量についても考えておきましょう。式($\ref{eq:fm3}$)の第4項、第5項は、式($\ref{eq:fm}$)の交互作用項と同じ形をしているので同様の変形をすると、式($\ref{eq:fm2}$)の交互作用項と同じ形になります。式($\ref{eq:fm3}$)の第4項は各ユーザーについて、第5項は各アイテムについて計算する必要があるので、計算量はそれぞれ$O(s^u \, k \, \overline{m}^u)$と$O(s^i \, k \, \overline{m}^i)$になります。前節と同様に$s^u \sim O(10^5)$、$k \sim O(10^2)$、$\overline{m}^u \sim O(10^2)$とすると、式($\ref{eq:fm3}$)の第4項の計算量は$O(s^u \, k \, \overline{m}^u) \sim O(10^9)$となるため学習時より計算量が小さいことがわかります。式($\ref{eq:fm3}$)の第5項も同様なので、学習時に計算量が問題にならなければ、式($\ref{eq:fm3}$)の第4項、第5項でも問題になることはないと考えてよいでしょう。

次に、式($\ref{eq:fm3}$)の第6項について考えましょう。式($\ref{eq:fm3}$)の第6項は

$$ \begin{eqnarray} \sum^{n^u}_{l=1}\sum^{n^i}_{j=1}{\hat{w}^{u,i}_{l, j} x^u_l x^i_j} &=& \sum^{n^u}_{l=1}\sum^{n^i}_{j=1}\sum^k_{f=1}{v^u_{l,f} v^i_{j,f} x^u_l x^i_j} \nonumber \\ &=& \sum^k_{f=1} \Biggl(\sum^{n^u}_{l=1} {v^u_{l,f} x^u_l} \Biggr) \Biggl(\sum^{n^i}_{j=1} {v^i_{j,f} x^i_j} \Biggr) \nonumber \\ &=& \sum^k_{f=1} q^u_f q^i_f \label{eq:qq} \end{eqnarray} $$

と変形することができます。ここで

$$ \begin{eqnarray} q^u_f &=& \sum^{n^u}_{j=1} {v^u_{j,f} x^u_j} \label{eq:q_u} \\ q^i_f &=& \sum^{n^i}_{j=1} {v^i_{j,f} x^i_j} \label{eq:q_i} \end{eqnarray} $$

としています。$q^u_f$はユーザーデータのみで計算でき、$q^i_f$はアイテムデータのみで計算できるので、事前に一回計算し記憶しておけば式($\ref{eq:qq}$)の計算量は$O(k)$になります。したがって、式($\ref{eq:fm3}$)の計算量は$O(s^u \, s^i \, k)$となります。

もう少し$q^u_f$と$q^i_f$について考えてみましょう。$q^u_f$はユーザーごとに因子数分の$k$個計算しておく必要があります。つまり、合計$k \times s^u$個計算しておく必要があるので、因子を行、ユーザーを列とした$q^u_f$を要素にもつ${\bf Q}^u \in {\mathbb R}^{k \times s^u}$を事前に計算し記憶しておきます。同様に、アイテムについても因子を行、アイテムを列とした$q^i_f$を要素にもつ${\bf Q}^i \in {\mathbb R}^{k \times s^i}$を計算し記憶しておきます。${\bf Q}^u$を作成する計算量は$O(s^u \, k \, \overline{m}^u)$、${\bf Q}^i$を作成する計算量は$O(s^i \, k \, \overline{m}^i)$で、式($\ref{eq:fm3}$)の第4項、第5項と同じ計算量になるため、計算量が問題になることはありません。

まとめると、ユーザーのみあるいはアイテムのみで計算可能な部分を事前に計算しておき、その結果を式($\ref{eq:fm3}$)の計算時に使うことで式($\ref{eq:fm3}$)の計算量は$O(s^u \, s^i \, k)$となります。それにより、コンテキストの非ゼロデータ個数$\overline{m}^u$や$\overline{m}^i$には依存せず、コンテキストを増やしても評価推定値計算の計算量は増加しなくなります。前節と同様の想定で$s^u \sim O(10^5)$、$s^i \sim O(10^5)$、$k \sim O(10^2)$とすると$O(s^u \, s^i \, k) \sim O(10^{12})$となります。並列・分散処理でさらに十倍程度高速化できれば計算量は$O(10^{11})$になるので、前節で見積もった学習時の計算量$O(10^9$)より百倍大きいものの、これぐらいであれば現実的な時間内に計算を終えることができるようになります。弊社でもここで紹介した計算方法と並列処理を併用して運用しています。

なお、式($\ref{eq:fm3}$)の計算量$O(s^u \, s^i \, k)$は、Matrix Factorization(MF)の評価推定値計算と同じ計算量になっています。そのため、レコメンデーションでMFを使った運用ができているならば、コンテキストを使うFMを導入したときの評価推定値計算時間は同程度になるため、計算時間がボトルネックになってFMを導入できなくなることはほとんどありません。

実装

では実装してみましょう。今回も簡潔な表記が可能なJuliaを使います。今回はコードも少ないので少し実装のコツも紹介します。

今回扱っている数式はシンプルなので実装するのは比較的容易だと思いますが、数式はわかるしコードも読めるけど慣れていないと自分で書くとうまく書けないという人もいるかもしれません。アルゴリズムの種類によって数式を実装に落とすコツは異なるのですが、ここでは多くの場合に使える基本的な考え方を2つ紹介します。

1つ目は、ベクトルや行列などの変数を作成するときのサイズと型についてです。論文などを読むと記号の定義が書いてあるのでそれを使います。例えば、${\bf V} \in {\mathbb R}^{n \times k}$となっていれば、行数$n$、列数$k$の浮動小数点数型の行列にすればよいことがわかります。そのため、記号を定義しているところを全て見つけてベクトルや行列を作成するコードを書いていけば、実装しようとしているアルゴリズムに必要な変数は一通りコードに落とせます。

2つ目は、和の記号についてです。和の記号を使った計算は、ループに置き換えることができるというのは基本ですよね。和の記号が三つかかっている計算は三重ループになります。注意するのは添字と和の範囲です。論文によっては和の範囲が省略されていたり実装しにくかったりするので、アルゴリズムを実装する前に確認しておく必要があります。例えば、$\sum^k_{f=1}$とあればループ変数$f$を1から$k$まで変えるループであるとすぐにわかりますが、$\sum_{f \in F}$とあれば集合$F$の定義を確認しておく必要があります。$F$の要素は特別な条件を満たさなければいけないのであれば条件処理の追加が必要になったりします。また、変数の添字が省略されていることもよくあります。論文では誤解されない範囲で簡潔な表記になっていて、実装には適していない表記になっていることもあるので、そのような場合は和の範囲を明示したり添字を省略しない形に書き直すと実装しやすくなります。

1データ分の推定値計算と、${\bf Q}^u$や${\bf Q}^i$の事前計算のコードは以下のとおりです。

using Distributions
using SparseArrays
using LinearAlgebra

# 以前の記事(https://analytics.livesense.co.jp/entry/2019/05/28/110000)で紹介したコードと同じ
function y_hat(x_, w₀, w, v)
    (i, x) = findnz(x_)  # 非ゼロデータのインデックスと値
    n = nnz(x_)          # 非ゼロデータの数
    k = size(v)[2]

    ΣΣwᵢⱼxᵢxⱼ = 0.0
    for f_ in 1:k
        Σvx = 0.0
        Σv²x² = 0.0
        for j_ in 1:n
            vx = v[i[j_], f_] * x[j_]
            Σvx += vx
            Σv²x² += vx^2
        end
        ΣΣwᵢⱼxᵢxⱼ += Σvx^2 - Σv²x²
    end
    return w₀ + x ⋅ w[i] + 0.5 * ΣΣwᵢⱼxᵢxⱼ  # 式(3)
end

function precompute_q(x_, v, s, k)
    q = zeros(Float64, k, s)  # (因子数, データ数) 

    for i_ in 1:s
        (idx, x) = findnz(x_[i_, :])
        nnz_ = nnz(x_[i_, :])

        for f_ in 1:k
            for j_ in 1:nnz_
                q[f_, i_] += v[idx[j_], f_] * x[j_]  # 式(9), (10)
            end
        end
    end
    return q
end

呼び出しコードは以下のとおりです。事前計算を使うと非ゼロデータ個数が増えても計算量がほとんど変わらないことを確認してみてください。

# サンプルデータ作成
sparseness = 0.01  # 非ゼロの比率

sᵘ = 10^3           # ユーザー数
nᵘ = 10^3           # ユーザーコンテキスト数
xᵘ = convert(SparseMatrixCSC{Int64,Int64}, sprand(Bool, sᵘ, nᵘ, sparseness))
xᵘᵗ = sparse(xᵘ')

sⁱ = 10^3           # アイテム数
nⁱ = 10^3           # アイテムコンテキスト数
xⁱ = convert(SparseMatrixCSC{Int64,Int64}, sprand(Bool, sⁱ, nⁱ, sparseness))
xⁱᵗ = sparse(xⁱ')


# モデルパラメータはすでに計算済みという想定(ここでは乱数を使う)
k = 10
n = nᵘ + nⁱ
w₀ = rand()
w = rand(n)
v = rand(Normal(0.0, 0.001), n, k)

# 事前計算用にユーザーとアイテムのパラメータを分ける
wᵘ = w[1:nᵘ]
vᵘ = v[1:nᵘ, :]
wⁱ = w[(nᵘ+1):n]
vⁱ = v[(nᵘ+1):n, :]


# 事前計算なし
@time e1 = [y_hat(vcat(xᵘᵗ[:,i], xⁱᵗ[:,j]), w₀, w, v) for j in 1:sⁱ, i in 1:sᵘ]

# 事前計算あり
@time ŷᵘ = [y_hat(xᵘᵗ[:, i], 0, wᵘ, vᵘ) for i in 1:sᵘ]                              # 式(4)の第2項、第4項
@time qᵘ = precompute_q(xᵘ, vᵘ, sᵘ, k)                                            # 式(9)
@time ŷⁱ = [y_hat(xⁱᵗ[:, i], 0, wⁱ, vⁱ) for i in 1:sⁱ]                                  # 式(4)の第3項、第5項
@time qⁱ = precompute_q(xⁱ, vⁱ, sⁱ, k)                                               # 式(10)
@time e2 = [w₀ + ŷᵘ[i] + ŷⁱ[j] + qᵘ[:,i] ⋅ qⁱ[:,j] for j in 1:sⁱ, i in 1:sᵘ]  # 式(4)、式(8)


# 事前計算が正しく動いているか確認
(e1 .- e2).^2 |> mean |> sqrt



# 非ゼロ比率を一定のままコンテキストデータサイズを増やす => 非ゼロデータ個数が増える
nᵘ = 10^4           # ユーザーコンテキスト数
xᵘ = convert(SparseMatrixCSC{Int64,Int64}, sprand(Bool, sᵘ, nᵘ, sparseness))
xᵘᵗ = sparse(xᵘ')

nⁱ = 10^4           # アイテムコンテキスト数
xⁱ = convert(SparseMatrixCSC{Int64,Int64}, sprand(Bool, sⁱ, nⁱ, sparseness))
xⁱᵗ = sparse(xⁱ')

n = nᵘ + nⁱ
w₀ = rand()
w = rand(n)
v = rand(Normal(0.0, 0.001), n, k)

wᵘ = w[1:nᵘ]
vᵘ = v[1:nᵘ, :]
wⁱ = w[(nᵘ+1):n]
vⁱ = v[(nᵘ+1):n, :]

# 事前計算なし
@time e1 = [y_hat(vcat(xᵘᵗ[:,i], xⁱᵗ[:,j]), w₀, w, v) for j in 1:sⁱ, i in 1:sᵘ]

# 事前計算あり
@time ŷᵘ = [y_hat(xᵘᵗ[:, i], 0, wᵘ, vᵘ) for i in 1:sᵘ]                              # 式(4)の第2項、第4項
@time qᵘ = precompute_q(xᵘ, vᵘ, sᵘ, k)                                            # 式(9)
@time ŷⁱ = [y_hat(xⁱᵗ[:, i], 0, wⁱ, vⁱ) for i in 1:sⁱ]                                  # 式(4)の第3項、第5項
@time qⁱ = precompute_q(xⁱ, vⁱ, sⁱ, k)                                               # 式(10)
@time e2 = [w₀ + ŷᵘ[i] + ŷⁱ[j] + qᵘ[:,i] ⋅ qⁱ[:,j] for j in 1:sⁱ, i in 1:sᵘ]  # 式(4)、式(8)

さて、実装のコツをふまえてコードを見ていきましょう。ベクトルや行列のサイズが記号定義と同じになっていますよね。また、簡単な内積演算は演算子を使っていますが、それ以外はfor文になっているので、疎行列の部分を除くと、ループの範囲が前節までの説明と一致していることも合わせて確認してみてください。

コンテキストデータ${\bf X}$を疎行列としているところと、行列にアクセスするときは列単位になっているところが実装上の注意点です。Juliaは基本的に列単位のアクセスが高速になるよう設計されているので、行単位でアクセスが必要な行列は転置して列単位でアクセスできるようにしています。${\bf Q}^u$や${\bf Q}^i$の定義で、因子を行、ユーザーやアイテムを列にしたのも列単位でアクセスしやすくするためです。

事前計算を行うことで少しコード量が増えていますが、この程度であれば実装工数の増加を懸念するほどではないでしょう。式($\ref{eq:fm3}$)の第2項と第4項は式($\ref{eq:fm}$)とほぼ同じ形なのでy_hat()関数を流用できます。式($\ref{eq:fm3}$)の第3項と第5項についても同様です。${\bf Q}^u$や${\bf Q}^i$の事前計算でコードが10行ほど増えますが、$\bf{Q}$同士の計算は内積計算なので簡単です。

最後に

今回は、FMの評価推定値の効率的な計算方法について紹介しました。技術的には大した方法ではないものの、少しの工夫で計算量を削減できるので実用性は高いです。このような実装の仕方は実務で数値計算やアルゴリズム実装などをされている方にとっては当たり前の方法ですが、短い工数で機械学習を使おうとすると計算量まで頭が回らないことがあります。そんなときに、こういう方法があることを知っていれば、役に立つこともあるのではないでしょうか。

以前の記事とともにFMを使ってレコメンデーションをするときの計算量に着目した内容を扱いました。機械学習では精度に注目が集まりがちでディープラーニング関係を除くと計算量の話題は少ないように思います。弊社の場合だと、グロース施策が当たってユーザー数が急増したり、業務提携でアイテム数(求人数)が急増したりすることがあるので、どのぐらいのデータ量までなら現在のままで対応できるか、インスタンス増強するとどれぐらいコストが増えるかなどの見通しをもっておく必要があります。こういうときに計算量は役に立ちます。機械学習は「やってみないとわからない」と言われますが、理解を深めることで見通しを立てられる場面も少なくありません。弊社では機械学習を使う場合でも見通しを立てたり原因を考えたりすることを大事にしています。

レコメンデーションは売上に直結することが多いのでよく使われますが、使いこなすのは大変です。RMSEやAUCのような精度に注目が集まりがちですが、今回紹介したように計算量が問題になることもあります。ログデータを使ってオフライン精度検証を行うときにも注意が必要で、単純にデータ分割する交差検証を使うのは不適切ですし、そのままRMSEを評価するとバイアスが生じる問題もあります。また、RMSEやAUCのような精度が高ければよいレコメンデーションになっているわけでもないので精度指標についても配慮が必要です。実際に運用してみないと気づきにくい課題もいろいろあるのですよね。そのような課題や対処方法は地味な内容だったりするので公開されていることは少ないですが実務では重要だったりします。本ブログでは、学習データの作り方や精度検証のコツといった他ではあまり扱われていない内容も今後取り上げていこうと思います。

Alternating Least SquaresによるFactorization Machinesのパラメータ推定

こんにちは、リブセンスで統計や機械学習関係の仕事をしている北原です。今回はレコメンデーションにも使えるFactorization Machines(FM)の効率的な学習アルゴリズムの紹介です。実装にはJuliaを使います。

実務で必要な要件を満たす機械学習ライブラリがなくて、機械学習モデルをカスタマイズすることってありますよね。最近はTensorFlowのような機械学習フレームワークが充実してきたので、そういう場合にはこれらのフレームワークを利用することが多いかもしれません。しかし、アルゴリズムによっては、フルスクラッチで実装することで大幅に効率化できるものもあります。今回扱うFMのAlternating Least Squares(ALS) はその一例です。そこで使われている効率化方法は実装が簡単でギブスサンプリングなどでも使うことができる便利なものなのですが、あまり知られていないようです。そこで、今回はこの計算効率化方法を紹介しようと思います。

Factorization Machines

レコメンドアルゴリズムといえば、協調フィルタリングやコンテンツベースフィルタリングが有名ですが、本記事ではコンテキストを使えるFMを扱います。求人サービスだと職種や年収、勤務地などの情報が有用なので、これらの情報をレコメンデーションで利用できると新規ユーザーにも好みにあったレコメンドがしやすくなります。FMは有名なので、検索するといろいろと情報が見つかると思います。ここでは計算効率化に関する部分を中心に説明します。

FMは、Matrix Factorization(MF)やSVD++のような協調フィルタリングを一般化して表現できるようにしたモデルです。MFと同様に、ユーザーが未評価のアイテムについても評価推定値$\hat{y}$を計算することができるので、レコメンデーションに利用されています。MFとFMは学習データのフォーマットが異なっていて、MFだと評価点数をユーザー数×アイテム数の疎行列で表したものを学習データとしますが、FMだと1行1評価としてユーザーやアイテムに対応する要素を1としたものを学習データとしているところに注意が必要です。詳しくは論文解説記事1解説記事2などを見てください。

FMは、評価データ数を$s$、ユーザーIDなども含むコンテキスト数(特徴量数)を$n$、因子数を$k$とし、評価値$\mathbf{y} \in {\mathbb R}^{s}$、評価と対応するコンテキストデータ${\bf X} \in{\mathbb R}^{s \times n}$(1サンプルのコンテキストは$\bf{x}$と表記)、モデルパラメータ$w_0 \in {\mathbb R}$、${\bf w} \in {\mathbb R}^n$、${\bf V} \in {\mathbb R}^{n \times k}$を使って、以下のようなモデルで表現されます。

$$ \begin{eqnarray} \hat{y}({\bf x}) &=& w_0 + \sum^n_{i=1}{w_i x_i} + \sum^n_{i=1}\sum^n_{j=i+1}{\hat{w}_{i, j} x_i x_j} \label{eq:fm} \\ \hat{w}_{i, j} &=& \sum^k_{f=1}{v_{i,f} v_{j,f}} \label{eq:w} \end{eqnarray} $$

モデル上のポイントは、交互作用項の係数$\hat{w}_{i, j}$がモデルパラメータ${\bf V}$の異なる行の内積になっているところにあります。これにより特徴量の組み合わせが学習データに存在しなくとも$\hat{w}_{i, j}$を計算できるため、レコメンデーションに利用しやすくなっているというのが1つ目の利点です。通常の回帰モデルでは、交互作用項の係数が特徴量の組み合わせの数$n(n+1)/2$だけ必要です。そのため、特徴量数$n$が多いとモデルパラメータ数が膨大になるという問題があります。しかし、FMでは${\bf V}$のサイズ分しか必要としません。通常は$k \ll n$となるよう因子数$k$を決めるので、同様の問題は起きにくくなるというのが2つ目の利点です。

一見すると交互作用項が複雑なのですが、各モデルパラメータについては線形になっているところが計算上のポイントです。二乗誤差を考えたとき、各モデルパラメータについては単純な二次関数になるため、簡単に最適値を計算することができます。

ここで後の説明をやりやすくするために、式($\ref{eq:fm}$)の別の表記を導入します。各モデルパラメータについて線形なので、着目するモデルパラメータを$\theta$としたとき式($\ref{eq:fm}$)は一般的に

$$ \begin{equation} \hat{y}(\mathbf{x} | \theta)=g_{(\theta)}(\mathbf{x})+\theta h_{(\theta)}(\mathbf{x}) \label{eq:lin} \end{equation} $$

と書くことができます。$g_{(\theta)}(\mathbf{x})$は$\theta$を含まない部分、$h_{(\theta)}(\mathbf{x})$は$\theta$にかかっている部分です。$\theta$以外のモデルパラメータはすでに与えられていて定数になっていると考えるとわかりやすいかもしれません。少し具体例を見てみましょう。例えば、特徴量数$n=3$、因子数$k=2$のとき、式($\ref{eq:fm}$)は

$$ \begin{eqnarray} \hat{y}(\mathbf{x}) &=& w_0 + w_1 x_1 + w_2 x_2 + w_3 x_3 \nonumber \\ &+& (v_{1, 1} v_{2, 1} + v_{1, 2} v_{2, 2}) x_1 x_2 + (v_{1, 1} v_{3, 1} + v_{1, 2} v_{3, 2}) x_1 x_3 + (v_{2, 1} v_{3, 1} + v_{2, 2} v_{3, 2}) x_2 x_3 \end{eqnarray} $$

と書けます。$\theta=w_2$とすると

$$ \begin{eqnarray} g_{(w_2)}(\mathbf{x}) &=& w_0 + w_1 x_1 + w_3 x_3 \nonumber \\ &+& (v_{1, 1} v_{2, 1} + v_{1, 2} v_{2, 2}) x_1 x_2 + (v_{1, 1} v_{3, 1} + v_{1, 2} v_{3, 2}) x_1 x_3 + (v_{2, 1} v_{3, 1} + v_{2, 2} v_{3, 2}) x_2 x_3 \\ h_{(w_2)}(\mathbf{x}) &=& x_2 \end{eqnarray} $$

となります。同様に、$\theta=v_{3, 2}$とすると

$$ \begin{eqnarray} g_{(v_{3,2})}(\mathbf{x}) &=& w_0 + w_1 x_1 + w_2 x_2 + w_3 x_3 \nonumber \\ &+& (v_{1, 1} v_{2, 1} + v_{1, 2} v_{2, 2}) x_1 x_2 + v_{1, 1} v_{3, 1} x_1 x_3 + v_{2, 1} v_{3, 1} x_2 x_3 \\ h_{(v_{3,2})}(\mathbf{x}) &=& x_3 (v_{1, 2} x_1 + v_{2, 2} x_2) \end{eqnarray} $$

となります。式($\ref{eq:lin}$)の表記を使うことで、$w$や$v$の違いにかかわらず統一的にモデルパラメータを扱えたり、微分を

$$ \begin{equation} \frac{\partial \hat{y}(\mathbf{x})}{\partial \theta} = h_{(\theta)}(\mathbf{x}) \label{eq:par_y} \end{equation} $$

のように簡潔に表記できます。しかし、これだけだと大変な計算が$g_{(\theta)}(\mathbf{x})$や$h_{(\theta)}(\mathbf{x})$に置き換えられて数式が簡単になるぐらいで、実用上のメリットがないように思うかもしれません。特徴量数や因子数が増えれば$g_{(\theta)}(\mathbf{x})$や$h_{(\theta)}(\mathbf{x})$の計算量が増加することは容易に想像がつきます。ところが、$g_{(\theta)}(\mathbf{x})$や$h_{(\theta)}(\mathbf{x})$を定義どおりに計算しなくてもモデルパラメータを推定できるうまい方法があり、式($\ref{eq:lin}$)の形にすることでその方法を導出しやすくなっているのです。このうまい方法については後で説明します。

Alternating Least Squaresによるパラメータ推定

モデルパラメータの推定方法には様々なものがありますが、今回はAlternating Least Squres(ALS、交互最小二乗法)を使います。MFの派生モデルのパラメータ推定法としては定番の一つです。Coordinate Descent(座標降下法)と考えることもできます。最近だとStochastic Gradient Descent(SGD、確率的勾配降下法)のほうが有名ですし、FMのモデルパラメータ推定にも利用されていますが、SGDだと今回紹介する効率的計算は使えません。

ALSでは、更新しないモデルパラメータを固定したまま、誤差を最小化するように各パラメータを一つずつ更新する処理を、最適値に収束するまで繰り返します 。一方で、SGDやGradient Descent(GD、勾配降下法)のような勾配法では、勾配を少しずつ下っていくことで最適値をもとめます。WikipediaのCoordinate descentGradient descentに掲載されている図を見ると、直感的なイメージがつかめると思います。

SGDやGDのような単純な勾配法と比較したときのALSの利点は、学習率のような調整パラメータがないところです。近年では学習率を自動調整する方法がいろいろと提案されているので、あまり強いメリットを感じないかもしれません。それでも、最初から学習率を考えなくともよいのは利点の一つでしょう。

では、FMのモデルパラメータ更新式を導出しましょう。モデルパラメータ集合を$\Theta$、モデルパラメータ$\theta \in \Theta$の正則化係数を$\lambda_{(\theta)}$として正則化項を入れた二乗誤差

$$ \begin{equation} L = \sum^s_{l=1}{(\hat{y}({\bf x}_l) - y_l)^2} + \sum_{\theta \in \Theta}{\lambda_{(\theta)} \theta^2} \label{eq:err} \end{equation} $$

を最小化することでパラメータを推定します。モデルパラメータは複数ありますが、ALSでは1パラメータのみを変数として考え、残りを定数のように扱うところがポイントです。1つのモデルパラメータ$\theta$のみを変数としたとき、二乗誤差$L$を最小にする$\theta$の値は、$\theta$で微分したものを0とおいて整理すればよいですね。式($\ref{eq:lin}$)と式($\ref{eq:par_y}$)を使って

$$ \begin{eqnarray} \frac{\partial L}{\partial \theta} &=& \sum^s_{l=1}{2 (\hat{y}({\bf x}_l) - y_l) \frac{\partial \hat{y}({\bf x}_l)}{\partial \theta}} +2 \lambda_{(\theta)} \theta \nonumber \\ &=& 2 \sum^s_{l=1}{(\hat{y}({\bf x}_l) - y_l) h_{(\theta)}(\mathbf{x}_l)} +2 \lambda_{(\theta)} \theta \nonumber \\ &=& 2 \sum^s_{l=1}{(g_{(\theta)}({\bf x}_l) - y_l) h_{(\theta)}(\mathbf{x}_l)} + 2 \theta \sum^s_{l=1}{h^2_{(\theta)}(\mathbf{x}_l)} +2 \lambda_{(\theta)} \theta =0 \\ \end{eqnarray} $$

と変形し、$\theta$について整理すると

$$ \begin{equation} \theta=-\frac{\sum^s_{l=1}{(g_{(\theta)}({\bf x}_l) - y_l) h_{(\theta)}(\mathbf{x}_l)}}{\sum^s_{l=1}{h^2_{(\theta)}(\mathbf{x}_l)} + \lambda_{(\theta)}} \label{eq:orig_theta} \end{equation} $$

と、二乗誤差$L$を最小にする$\theta$を計算できます。式($\ref{eq:lin}$)を使っているのでシンプルな形にまとまっていますね。式($\ref{eq:fm}$)や式($\ref{eq:w}$)をそのまま愚直に微分してみると、違いが実感できると思います。

次に、1パラメータ1回の更新に必要な計算量について考えてみましょう。実際には全パラメータについて収束するまで値更新を繰り返すので、さらにパラメータ数と繰り返し数を乗じたものが全体の計算量になることに注意してください。

基本的には式($\ref{eq:orig_theta}$)の通りに計算すれば、$\theta$を算出できます。時間がかかるのは$\theta=v_{i, j}$のときなので、工夫なしに計算すると、$n$個のパラメータの組み合わせが$g_{(\theta)}(\mathbf{x}_{l})$の計算にあらわれるので計算量は$O(s \, k \, n^2 )$となります。レコメンデーションでは、コンテキスト数はユーザー数やアイテム数より少ないことが多いので、$n$はユーザー数とアイテム数の和と同じオーダーになることが多いです。問題設定にもよりますが弊社の場合、$n$のオーダーは数万から数十万程度になるので、$O(s \, k \, n^2)$だと現実的な時間で計算を終わらせるのは難しいことが多いです。

計算を効率化する方法はいくつかあって、FMが最初に提案された論文のLemma 3.1を利用すると、式($\ref{eq:fm}$)の交互作用項は

$$ \begin{equation} \sum^n_{i=1}\sum^n_{j=i+1}\sum^k_{f=1}{v_{i,f} v_{j,f}} x_i x_j = \frac{1}{2} \sum_{f=1}^{k}\left(\left(\sum_{i=1}^{n} v_{i, f} x_{i}\right)^{2}-\sum_{i=1}^{n} v_{i, f}^{2} x_{i}^{2}\right) \label{eq:interaction_term} \end{equation} $$

と変形できるので、計算量は$O(s \, k \, n)$になります。さらに、データがスパースな場合、1サンプルあたりの非ゼロデータの個数の平均を$\overline{m}_R$とすると、$O(s \, k \, \overline{m}_R)$になります。レコメンデーションなどで使う場合は、$\overline{m}_R \ll n$となることがほとんどです。例えば、ユーザー数とアイテム数が数万のオーダーとして$n \sim O( 10^4 )$、1サンプルあたりの非ゼロデータ数が百程度として$\overline{m}_R \sim O(10^2)$となっている場合、何も工夫をしなかったときと比較すると$O(10^6)$、つまり百万倍速くなります。これぐらいになると、現実的な時間内で計算が終わります。しかし、この計算を全パラメータについて行うと、交互作用項の計算に必要なパラメータ$\bf{V}$のサイズが$n \times k$ なので、$O(s \, n \, k^2 \, \overline{m}_R)$となり、因子数$k$を大きくすると計算時間が$O(k^2)$で急激に増えてしまいます。表現能力を高めるためにオーバーフィットしない範囲で因子数を大きくすることが多いですが、これだと気軽に大きくはできません。

事前計算による高速学習

さて、本題の効率的な計算方法について説明します。

計算を効率化するポイントは、共通する計算は一度で済ませ、差分のみ計算するところにあります。着目すべきは、全データサンプルについての和を計算している部分に含まれる、更新されるパラメータ$\theta$について線形な部分です。例えば、この線形な部分を$f(\mathbf{x}, \theta)=g(\mathbf{x}) + \theta h(\mathbf{x})$と書き、更新後のパラメータを$\theta^{\ast}$とすると$f(\mathbf{x}, \theta^{\ast})=g(\mathbf{x}) + \theta^{\ast} h(\mathbf{x}) = f(\mathbf{x}, \theta) + (\theta ^{\ast} - \theta) h(\mathbf{x})$のように更新後の$f(\mathbf{x}, \theta^{\ast})$を計算できます。$f(\mathbf{x}, \theta)$は更新前のものなので、前のステップで記憶しておけば計算量は$O(1)$です。そのため、$g(\mathbf{x})$の計算量がどれだけ多くとも、$h(\mathbf{x})$の計算量のみに依存することになります。前のステップで計算したものを使うので、ここではこの処理を事前計算と呼びます。

これをふまえ、効率化の方針としては、式($\ref{eq:orig_theta}$)からパラメータ$\theta$について線形な部分を探し、前のステップで記憶しておくべき部分と更新式の整理をすることで計算量の削減を図ります。式($\ref{eq:orig_theta}$)の分子は$g_{(\theta)}({\bf x}_l) - y_l$と$h_{(\theta)}(\mathbf{x}_l)$の積になっていて一度に扱うと複雑なので、各項について効率化を図っていきましょう。$g_{(\theta)}({\bf x}_l) - y_l$と$h_{(\theta)}(\mathbf{x}_l)$の計算量はそれぞれ$O(k \, \overline{m}_R)$、$O(\overline{m}_R)$なので、計算量の大きい$g_{(\theta)}({\bf x}_l) - y_l$から先に考えます。

残差$e(\mathbf{x}_l, y_l | \Theta) = \hat{y}(\mathbf{x}_l | \Theta) - y_l$を使うと

$$ \begin{eqnarray} g_{(\theta)}({\bf x}_l) - y_l &=& \hat{y}(\mathbf{x}_l | \Theta) - y_l - \theta h_{(\theta)}(\mathbf{x}_l) \nonumber \\ &=& e(\mathbf{x}_l, y_l | \Theta) - \theta h_{(\theta)}(\mathbf{x}_l) \end{eqnarray} $$

と書けます。$e(\mathbf{x}_l, y_l | \Theta)$は$\theta$について線形なので、更新後のパラメータを$\theta^{\ast}$を含むパラメータ集合を$\Theta^{\ast}$とすると

$$ \begin{equation} e(\mathbf{x}_l, y_l | \Theta^{\ast}) = e(\mathbf{x}_l, y_l | \Theta) + (\theta^{\ast} - \theta)h_{(\theta)}(\mathbf{x}_l) \label{eq:e} \end{equation} $$

と更新できます。更新前の$e(\mathbf{x}_l, y_l | \Theta)$を記憶しておけば、計算量は$O(\overline{m}_R)$になるので、$k$倍速くなりますね。

次に、$h_{(\theta)}(\mathbf{x}_l)$についても考えてみましょう。$\theta=w_i$の場合は、$h_{(w_i)}(\mathbf{x}_l) = x_{l, i}$なので常に$O(1)$となるので簡単です。$\theta=v_{i, f}$の場合、式($\ref{eq:fm}$)、式($\ref{eq:w}$)、式($\ref{eq:par_y}$)より

$$ \begin{eqnarray} h_{(v_{i, f})}(\mathbf{x}_l) &=& \frac{\partial \hat{y}(\mathbf{x}_l)}{\partial v_{i, f}} \nonumber \\ &=& x_{l, i} \sum_{j=1}^{n} v_{j, f} x_{l, j} - x^2_{l, i} v_{i, f} \label{eq:orig_h} \end{eqnarray} $$

と計算できます。交互作用項の微分は式($\ref{eq:interaction_term}$)の形を使ったほうが計算ミスしにくいかもしれません。ここで$q_{l, f}(\Theta) = \sum_{j=1}^{n} v_{j, f} x_{l, j}$に着目し$\theta=v_{j, f}$と考えると、$q_{l, f}(\Theta) $は$\theta$について線形なので

$$ \begin{equation} q_{l, f}(\Theta^{\ast}) = q_{l, f}(\Theta) + (v^{\ast}_{i, f} - v_{i, f}) x_{l, i} \label{eq:q} \end{equation} $$

と更新でき、

$$ \begin{equation} h_{(v_{i,f})}(\mathbf{x}_l) = x_{l, i} q_{l, f}(\Theta) - x^2_{l, i} v_{i, f} \label{eq:h} \end{equation} $$

と整理できます。つまり、$q_{l, f}(\Theta)$を記憶しておけば、$h_{(\theta)}(\mathbf{x}_l)$も$O(1)$で計算できるということです。そのため、式($\ref{eq:orig_theta}$)の分母にある$h^2_{(\theta)}(\mathbf{x}_l)$も$O(1)$で計算できるので、結局、式($\ref{eq:orig_theta}$)は$O(s)$で計算できることがわかります。

さらに、$x_{l, i}=0$だと、式($\ref{eq:q}$)、($\ref{eq:h}$)より$h_{\theta}(\mathbf{x}_l)=0$なので、計算の必要がありません。1パラメータに対応する非ゼロデータの個数の平均を$\overline{m}_C$とすると、式($\ref{eq:orig_theta}$)は$O(\overline{m}_C)$となります。レコメンデーションの場合、ユーザーIDやアイテムIDに対応するカラムはほとんどゼロで$\overline{m}_C \ll s$となることがほとんどなので、さらに計算量は少なくなります。

では、事前計算によってどのぐらい計算量が削減されているか考えてみましょう。事前計算を使わないときの計算量は$O(s \, k \, \overline{m}_R)$でしたから、事前計算によって$s \, k \, \overline{m}_R / \overline{m}_C$倍速くなります。通常は評価サンプルデータ数$s$のほうがコンテキスト数$n$より多いので、$\overline{m}_C < \overline{m}_R$となります。例えば、$s \sim O(10^5)$、$k \sim O(10^2)$、$\overline{m}_R \sim O(10^2)$、$\overline{m}_C \sim O(10)$とすると、一億倍速くなるということになります。もちろん、計算のオーバーヘッドなどがあるため実際にはこれほど速くなることは稀ですが、それでも計算量削減にかなり有効であることはわかると思います。

最終的に、パラメータ数のオーダーが$O(n \, k)$であることを思い出すと、全パラメータを一回ずつ更新するのに必要な計算量は$O(n \, k \, \overline{m}_C )$となります。これぐらい速いと、弊社の事業規模では問題になることがほぼありません。

実装

では実装してみましょう。ここではJuliaを使います。少し余談ですが、最近フルスクラッチでアルゴリズムを書く場合は簡潔な表記が可能で計算も高速なJuliaを使うことが多いです。別記事でも紹介しているように弊社には機械学習基盤があるので、使いたい言語やライブラリで実装したアルゴリズムを実サービスに導入しやすくなっています。ここで紹介するコードも社内で使われているものをベースにしています。

実装しやすいようにモデルパラメータ$w_0$、$\bf{w}$、$\bf{V}$ごとに式($\ref{eq:orig_theta}$)を整理すると

$$ \begin{eqnarray} w_0 &=& -\frac{\sum^s_{l=1}{e({\bf x}_l, y_l | \Theta) - s w_0}}{s + \lambda_{(w_0)}} \\ w_j &=& -\frac{\sum^s_{l=1}{(e({\bf x}_l, y_l | \Theta) - w_j x_{l, j}) x_{l, j}}}{\sum^s_{l=1} x^2_{l, j} + \lambda_{(w_j)}} \\ v_{j, f} &=& -\frac{\sum^s_{l=1}{(e({\bf x}_l, y_l | \Theta) - v_{j, f} h_{(v_{j, f})}({\bf x}_l)) h_{(v_{j, f})}({\bf x}_l)}}{\sum^s_{l=1}h_{(v_{j, f})}({\bf x}_l) + \lambda_{(v_{j, f})}} \end{eqnarray} $$

となります。 これをコードに落とすと、モデルパラメータ推定のコードは以下のようになります。

using Distributions
using SparseArrays
using LinearAlgebra

function y_hat(x_, w₀, w, v)
    (i, x) = findnz(x_)  # 非ゼロデータのインデックスと値
    n = nnz(x_)          # 非ゼロデータの数
    k = size(v)[2]       # 因子数

    ΣΣwᵢⱼxᵢxⱼ = 0.0
    for f_ in 1:k
        Σvx = 0.0
        Σv²x² = 0.0
        for j_ in 1:n
            vx = v[i[j_], f_] * x[j_]
            Σvx += vx
            Σv²x² += vx^2
        end
        ΣΣwᵢⱼxᵢxⱼ += Σvx^2 - Σv²x²  # 式(13)
    end
    return w₀ + x ⋅ w[i] + 0.5 * ΣΣwᵢⱼxᵢxⱼ
end

function precompute(y, x, w₀, w, v)
    s = size(x)[1]
    k = size(v)[2]
    e = zeros(s)     # 残差
    q = zeros(s, k)  # 交互作用項のカラム非依存部分
    xᵗ = sparse(x')  # CSC行列なので行単位でアクセスする場合は転置して列単位でアクセス

    for l in 1:s
        e[l] = y_hat(xᵗ[:, l], w₀, w, v) - y[l]
        for f in 1:k
            (l_, x_) = findnz(xᵗ[:, l])
            q[l, f] = x_ ⋅ v[l_, f]
        end
    end
    return [e, q]
end

function train(y, x, k, λ, n_itr)
    s = size(x)[1]  # データ数
    n = size(x)[2]  # コンテキスト数(特徴量数)

    # Initialize the model parameters
    w₀ = 0.0
    w = zeros(n)
    v = rand(Normal(0.0, 0.001), n, k)

    # 事前計算
    e, q = precompute(y, x, w₀, w, v)
    h = zeros(Float64, s)

    # main optimization
    for itr in 1:n_itr
        # global bias
        w₀ᵃ = -(sum(e) - s * w₀) / s
        e .+= (w₀ᵃ - w₀)  # 式(15)
        w₀ = w₀ᵃ

        # 1-way interactions
        for j in 1:n
            (i_, x_) = findnz(x[:, j])  # 非ゼロデータのインデックスと値

            wᵃ = -sum((e[i_] .- w[j] .* x_) .* x_) / (sum(x_.^2) + λ)  # 式(20)
            e[i_] .+= (wᵃ - w[j]) .* x_                                # 式(15)
            w[j] = wᵃ
        end

        # 2-way interactions
        for f in 1:k
            for j in 1:n
                (i_, x_) = findnz(x[:, j])  # 非ゼロデータのインデックスと値

                h[i_] .= x_ .* q[i_, f] .- x_.^2 .* v[j, f]
                vᵃ = -sum((e[i_] .- v[j, f] .* h[i_]) .* h[i_]) / (sum(h[i_].^2) + λ)  # 式(21)
                e[i_] .+= (vᵃ - v[j, f]) .* h[i_]                                      # 式(15)
                q[i_, f] .+= (vᵃ .- v[j, f]) .* x_                                     # 式(17)
                v[j, f] = vᵃ
            end
        end
    end
    return [w₀, w, v]
end

Juliaを使っていることもあり、計算式をほぼそのままコードに置き換えるだけで実装できていることがわかると思います。実装上のポイントは、疎行列を使っているところと、その疎行列にカラム単位でアクセスしているところです。Juliaの疎行列はCompressed Sparse Column(CSC)形式なので、カラム単位のアクセスが高速です。そのため、事前計算で行単位のアクセスが必要なところでは転置した行列を使っています。ALSでは元々カラム単位で処理するので、パラメータ更新時に使われるデータは転置していません。

なお、コードをシンプルにするため、今回のテーマから外れる事項については、簡単な方法を使っています。例えば、ALSでは、モデルパラメータの更新順序が推定値の収束速度に影響しますが、本記事の主題から外れるので、オリジナル論文と同じく添え字順に$w_i$を更新後、$v_{i, j}$を更新する方法になっています。また、計算停止条件も固定回数で停止させる簡単な方法を使っています。正則化係数$\lambda_{(\theta)} $もモデルパラメータによらず一定の$\lambda$にしています。このあたりの話題も機会があれば記事にするかもしれません。

呼び出しコードは以下のようになります。評価数や因子数を増やしても線形にしか計算時間が増えないことを確認してみてください。

# サンプルデータ作成
s = 100           # 評価数
n = 100           # コンテキスト数
sparseness = 0.5  # 非ゼロの比率
y = rand(1:5, s)  # 1~5点の評価がついている想定
x = convert(SparseMatrixCSC{Int64,Int64}, sprand(Bool, s, n, sparseness))
xᵗ = sparse(x')   # CSC行列なので列単位でアクセスできるよう転置

# 調整パラメータ
k = 10     # 因子数
λ = 0.1    # 正則化係数
n_itr = 5  # 何回更新するか
@time w₀, w, v = train(y, x, k, λ, n_itr)

# 誤差が小さくなっているか確認
e = [y_hat(xᵗ[:, l], w₀, w, v) - y[l] for l in 1:n]
rmse = e.^2 |> mean |> sqrt

# 評価数を10倍にすると、計算時間もほぼ10倍になる
n = 1000
k = 10
x = convert(SparseMatrixCSC{Int64,Int64}, sprand(Bool, s, n, sparseness))
@time w₀, w, v = train(y, x, k, λ, n_itr)

# 因子数を10倍にしても、計算時間は10倍にしかならない
n = 100
k = 100
x = convert(SparseMatrixCSC{Int64,Int64}, sprand(Bool, s, n, sparseness))
@time w₀, w, v = train(y, x, k, λ, n_itr)

最後に

今回は、効率的な学習が可能になるALSによるFMのパラメータ推定について紹介しました。少しの工夫で計算量を大幅に削減しているところが実用的です。FMはMF派生モデルの一般化になっているというところに目がいきがちなのですが、計算量の点でも優れていることがわかると思います。この計算方法は弊社の一部のサービスで利用されていますが、モデルパラメータ推定の計算時間が問題になったことは今のところありません。計算量が問題になっていると並列・分散処理で何とかしようと考えてしまいがちですが、力技だけだとコストがかかりすぎる場合はこのような方法も検討する価値があるかもしれません。

今回はFMのモデルパラメータ推定を扱いましたが、FMをレコメンデーションで使う場合は評価推定値計算の計算量も問題になりやすいです。なぜかというと、各ユーザーに対してレコメンド対象アイテムの評価推定値を計算するので、組み合わせが多くなってしまうためです。学習データで交差検証を行ったりコンペで使ったりしただけだと問題にならないので気づきにくいのですよね。この話題については、後日、別の記事で扱う予定です。

DigdagとEmbulkで行うDB同期の管理

データプラットフォームグループの松原です。 弊社各サービスのデータ分析基盤であるLivesense Analytics(以降LA)の開発、運用を行っています。
今回はLAで行っている分析のためにサービス側のデータ(テーブル)を、Redshiftへ同期を行う処理について紹介します。

概要

LAではデータウェアハウスとしてRedshiftを運用しており、社内から比較的自由に利用できる様にしています。
LAで取り扱っているデータはアクセスログが中心ですが、分析を行う利用者からはLA由来のデータ以外にも自分たちのサービスのデータを用いて分析を行いたい、という要望がよく出てきます。
サービスのデータには個人情報を含むものも少なくありませんが、分析基盤として社内にデータを解放するためにはそのような情報は削る必要があります。
そこで個人情報をマスキングしたサービス側データを利用できるよう、Redshiftに同期しています。

システム構成(概要)

大まかなシステム構成としては、下図のようになっています。

f:id:livesense-analytics:20190227151830p:plain:w650

多くのテーブルを同期しているので、カラム単位のマスキング処理や加工処理はEmbulkで行わず、同期元のデータベースであらかじめ行っておきます。

Digdagの選定理由

BigData-JAWS勉強会でAirflowのことを話してきましたにもあるように、すでにAirflowを運用していますが、ここではDigdagを選定しています。
主な選定理由としては以下があります。

  1. 構築や運用の容易さ
    Digdagはサーバーモードで動かしても、JavaとPostgreSQLの動く環境があれば運用を開始できます。
    また、Airflowと比べると、今のところ構築・アップグレードなどの運用は容易です。
  2. やりたいことがシンプル
    今回はsh(embluk)、redshift、httpオペレータで用途として足りそうで、それぞれのタスク間の依存関係も複雑では無いです。
    そのためタスク間の依存関係はYAMLで宣言的に書いたほうがメンテンスしやすいと考えました。
    また、DAG自体も複雑で無いため、どこまで実行できたか・どこで失敗したのかの可視性は求めていないのでダッシュボードも簡易なもので問題ありませんでした。

これらの理由により、Airflowで統一するより用途によりツールを使い分けた方が運用が容易なのでは、という結論になりました。

規模感

Redshiftへ同期しているデータに関する情報ですが以下のとおりです。

同期元のデータベース: 13個
同期を行っているテーブル数: 280テーブル
同期対象のデータベースの種類: 2種類(MySQL、PostgreSQL)
同期先: 2種類(Reshift、Redshift Spectrum)

これらのテーブルは、毎日業務開始前に前日のデータを同期しています。
同期はデータの増分を追加するのではなく、全量差し替えています。

Digファイルの依存関係

現時点では同期対象のテーブル数が280テーブル程度あるため、テーブル個別のデータ変換処理はなるべく行わないようにしています。
embulkやdigファイルを共通化しておくことで、同期対象テーブルの追加などの依頼があった場合にはテーブルとカラムの情報が書かれたファイル(下記の例だとtest1_tables.dig)のみを変更すれば良いようにしています。
また、テーブル個別のデータ変換処理はできるだけ行わないようにしていますが、変換が必要な場合はAirflow側で処理を行うようにしています。

2つのDBと同期を行う際のdigファイルの依存関係は、下図ようになります。

それぞれのファイルは以下のような役割で分けています。

ファイル名 概要
test1.dig Workflowを表すdig
test1_secret.dig 同期元への接続情報を保持しているdig
test1_tables.dig 同期対象のTable,Columnを定義しているdig
from-mysql-to-redshift.dig Embulkの実行・Redshiftへの処理を定義しているdig
in-mysql-out-s3.yml.liquid Embulkの設定ファイル
create.sql 一意になるテーブル名を作成
copy.sql EmbulkでS3においたファイルを、create.sqlで作成したテーブルにCOPY
swap.sql 既存のテーブルとSWAPし既存のテーブルを削除

スケジュール設定、通知・エラー処理などを省略すると、主だったdigファイルは以下のようになります。

--test1.dig
_export:
  mysql_database: MySQLの接続先DB名(ex. tes1)
  la_schema: redshift上のスキーマ名
  !include : digdag/environment/env.dig
  redshift:
    host: redshiftのホスト名
    database: redshiftのDB名
    user: la_importer
    ssl: true
    schema: ${la_schema}
    strict_transaction: false
    connect_timeout: 600s

+task:
  _export:
    !include : digdag/secret/test1_secret.dig

  for_each>:
    !include : digdag/media/test1_tables.dig
  _do:
    !include : digdag/flow/from-mysql-to-redshift.dig
--digdag/media/test1_tables.dig
mysql_table_info:
  - table: table1
    column: id, created_at, updated_at
  - table: table2
    column: id, created_at, updated_at
--digdag/flow/from-mysql-to-redshift.dig
_export:
  la_table: ${mysql_table_info.table}
  s3_file_path: mediadb/${la_schema}/${la_table}

+from-mysql-to-s3:
  sh>: embulk run -b /home/digdag/embulk_bundle /home/digdag/dag/embulk/in-mysql-out-s3.yml.liquid
  _export:
    mysql_table: ${mysql_table_info.table}
    mysql_select: ${mysql_table_info.column}

+mysql_redshift_create_temptable:
  redshift>: digdag/flow/queries/create.sql

+mysql_redshift_copy_2_temptable:
  redshift>: digdag/flow/queries/copy.sql

+mysql_redshift_swap_table:
  redshift>: digdag/flow/queries/swap.sql

運用上行っていること

以下のようなことを行って、運用コストを下げています。

  • Digdagで同期するテーブル情報の作成・Redshift用のCreate Table文(SORTKEY, DISTKEYは手動で設定)の作成のスクリプト化
  • タスクのログをS3に出力し、(shオペレーターから呼び出した)EmblukのログをLambdaでパース処理を行いエラー内容をSlackへ通知
  • Redashで同期済みデータのヘルスチェック
  • Errbotとmogを用いてChatOps(DAGの実行)
  • Redshift上に同期したが、1年以上利用されてないテーブルの割り出しと、今後も同期するのかの確認(不要テーブルを同期対象から外す)

これらを含めると、全体では以下のような構成になります。
f:id:livesense-analytics:20190220113717p:plain:w650

まとめ

もともとは Airflow を用いたデータフロー分散処理にあるバッチ処理と同様にRakeとwhenever(Cron)で運用されていたものをDigdagに置き換えました。
置き換えを行うことで、メンテナンスコストはだいぶ下げることが出来たのではないかと思います。
現在はデータソースがどこにあるのかと処理の複雑さによって、AirflowとDigdagのどちらを使うのかを使い分けています。

今後やっていきたいこと

今後もDigdagを用いた同期の改善の他にも、以下のようなこともやってきたいと考えています。

  • DigdagとAirflowの連携の強化(同期完了をトリガーとしてAirflowのDAG実行)
  • マスキング処理にProxySQLを使うことで、任意のタイミングでの同期の実行
  • CDC(Change Data Capture)を用いた変更内容の(ほぼ)リアルタイムの同期

UXデザインが総論賛成、各論疑問になる理由と、プロジェクト設計で意識したい3つの条件【中編】

 テクノロジカルマーケティング部 データマーケティンググループにてUXリサーチャーをしている佐々木と申します。普段は、UXデザイン(以下、UXDと略記)に関するプロジェクトを事業部横断で支援する業務についております。

 前回の私のブログでは、前編として「UXデザインが総論賛成、各論疑問になる理由」と「プロジェク設計で意識したい3つの条件の<その1>サービス・ドミナント・ロジックを中核とするサービスかどうか」について述べさせて頂きました。 analytics.livesense.co.jp

今回は、中編として<その2>潜在ニーズを探る必要性の有無、について述べさせて頂きます。

前編でも述べさせて頂きましたがUXDのプロジェクト設計で意識したい3つの条件は

  • <その1>サービス・ドミナント・ロジックを中核とするサービスかどうか
  • <その2>潜在ニーズを探る必要性の有無
  • <その3>改善・改良を目的とした既存事業・既存サービス

になります。今回は3条件の中の2つ目です。

4.1 潜在ニーズ有無による特徴

 プロジェクト設計で意識したい2つ目の条件として、「潜在ニーズを探る必要の有無」を挙げさせて頂きました。 ここでは、まず、潜在ニーズの有無による新規ソリューション案(事業案)の特徴について考えてみます。

 一般的に「顕在ニーズ」を対象にしたソリューション案(事業案)は、購買欲求が高く自明な顕在ニーズを対象にしているので早期に市場が立ち上がることが期待できます。しかしながら、デメリットとして、競合が多く、差別化を作り難く、価格競争になりがちな傾向があります。

 一方、「潜在ニーズ」を対象にしたソリューション案(事業案)は、近未来における社会やユーザーの変化に対応したサービスにより差別化を作り易く、先行利益を得やすいです。しかしながら、デメリットとして、サービス市場が立ち上がるまで安定した需要が見込めず事業成長の不確実性が高くなる傾向があります。

 この様な特徴を考慮して「潜在ニーズを探る必要の有無」により、そのソリューション案(事業案)の種を探す工数や、説得材料を揃えて検証する工数を大きく変えて設計した方が良いと考えてます。図4.1.1に示したデザインプロセスにおけるダブルダイヤモンドで例えると、前後のフェーズで共に設計を変える必要があるのです。

f:id:livesense-analytics:20180926172204p:plain
図4.1.1 デザインプロセスにおけるダブルダイヤモンド

4.2「問題の発見・収束」における設計の違い

 ダブルダイヤモンドの前半である「問題の発見・収束」のステップについて、新規事業や新規サービスを検討する場合について考えます。対象となる問題が「顕在ニーズ」「潜在ニーズ」のどちらなのか?と、その新規性が「機能」もしくは「体験価値」の場合で考えてみます。

4.2.1 「顕在ニーズ」の場合

 差別化要素となる新規性が機能に有り、その機能が解決するのが「顕在ニーズ」の場合、どの様な問題(顕在ニーズ)を対象にするのかが自明なのでダブルダイヤモンドの前半である「問題の発見・収束」フェーズに掛ける工数は少なくすることができます。

 潜在ニーズを探る必要が余り無いのは、検討しているサービスの事業領域において世の中のサービスに不満が多く存在し”なんとなく不満なサービス”が世の中に溢れている状況になっている時、とも言えます。

 例えば図4.2.1 の様に「事業やサービス領域において、既存技術や新規技術で解決できる顕在ニーズが一定規模以上で存在している」状況などを挙げることができます。 ※図4.2.1 の丸角四角は、個別の顕在ニーズを表し、その大きさはニーズを持つ人の規模を表現しています。青塗りの丸角四角は、すでにソリューションが世の中に存在しているニーズ、白塗りの丸角四角は、まだソリューションが世の中に存在していないニーズ、を表します。

 高度成長時代に技術イノベーションにより産業成長が続いていた時は、【Ⅰ】【Ⅱ】を繰り返していたとも言えます。ですので比較的に技術的な発展による新興サービスが該当することが多いです。また、既存事業等で解決したい問題が明らかになっており、その解決案の目処がたっている時も該当すると言えます。

 この様な状況下では、従来の「定量的なマーケットリサーチの判断基準」で判断することができます。ダブルダイヤモンドの左側でユーザーのニーズについて深いリサーチをかける必要は余りありません。定量的に把握可能な自明な顕在ニーズに対して、素早く製品・サービス開発を行い市場に投入した方が事業成果を得やすいことが多いからです。

f:id:livesense-analytics:20180531115416p:plain
図4.2.1 潜在ニーズを探る必要が余り無い状況

4.2.2 「潜在ニーズ」の場合

 差別化要素となる新規性が機能で有るものの、機能により解決される一定規模感の有る顕在ニーズが見当たらない場合や、機能に差別化する要素が乏しく差別化要素となる新規性を体験価値に求める場合は、潜在ニーズの探索が必要な場合が多いです。また、自明になっていない問題(潜在ニーズ)を対象にするので「問題の発見・収束」フェーズに掛ける工数を多く設計する必要が有ります。

 潜在ニーズを探る必要のあるのは、事業環境面では検討しているサービスの事業領域において世の中のサービスに大きな不満は無く、”なんとなく良いサービス”が世の中に溢れている状況になっている時、とも言えます。

 例えば図4.2.2の【III】【Ⅳ】の様に「事業やサービス領域において、既存技術で解決できるニーズはほぼソリューションが存在しており」、【III】「既存技術で解決できる未解決の顕在的なニーズは少数意見のみ」の状況や、【Ⅳ】は【III】に加えて「新規技術で解決できる未解決の顕在ニーズも少数意見のみ」の状況を挙げることができます。

 この様な状況は、成熟期の事業領域に多く、従来のマーケットリサーチの判断基準(一定数量のある未解決なニーズを対象にサービス開発を行う)だけでは、新規事業の芽を見つけ出すことは非常に困難です。この時、様々なアプローチ方法がありますが、その一つに潜在ニーズを探る手段があります。

 潜在ニーズを探す場合、ダブルダイヤモンドの左側で、"今まで、顕在ニーズとして少数の人しか必要としていないと思われていたけど、実は多くの人が求めていた潜在ニーズ"を探しだすことを目的とします。

 ここで述べる潜在ニーズとは、厳密な定義とは少しずれてしまうかもしれませんが、ウォンツとニーズにおける”ウォンツ”、ジョブ理論における”本質的に片付けたいジョブ”、UXDにおける”本質的に求めている未発見の体験価値”、等と重なる概念として考えております。

f:id:livesense-analytics:20180531115653p:plain
図4.2.2 潜在ニーズを探る必要のある状況

4.3 「解決案の発見・収束」における設計の違い

 次にダブルダイヤモンドの後半である「解決案の発見・収束」のステップにおいて考えてみます。「解決案の発見・収束」のステップでは、前半で対象とした「顕在ニーズ」「潜在ニーズ」のどちらの解決策を探索するのかにより必要な工数は異なります。

 「顕在ニーズ」を対象にした解決策は、顕在ニーズを対象にしているので想定価格や購入意向率を客観的に評価することができます。よって評価と検証がしやすいことから工数を少なくすることができます。

 しかしながら「潜在ニーズ」を対象にした解決策は、まだ無消費の市場であることが多いため客観的な評価はありえません。解決策はステップを経た検証が必要です。またその説得材料を揃えるにも不確実性が高く限られた材料になるので時間が掛かります。数ターンのアジャイルなプロトタイプの検証を通して、想定価格や購入意向率等を、その「世界観」や「体験価値を実感できるストーリー」のプロトタイプを用いて検証し徐々に確度を上げていく必要があります。 またその際は、不確実性が高い検証になりますので、有力な一つの「潜在ニーズを対象にした解決策」に絞るよりも、複数案を対象に検証す進め、その中から選別するプロセスを推奨します。

 更に最終的な検証はサービスのリリース後も継続されます。将来起こるであろう「社会の行動や価値感の変容」と共にサービスが世の中に浸透することになるからです。ですので、今回のプロジェクトで、どこまでの範囲を検証対象とするのか?を事前に確認して設計する必要が有ります。

 また複数の候補案が有り、「顕在ニーズ」「潜在ニーズ」が混在している場合は特に注意が必要です。同じ設計で同時並行的に進めようとすると「潜在ニーズ」を対象にした検証が時間不足で不十分になりがちで、中途半端な結果となり最終候補案として見送られてしまうことが多いからです。その必要性により十分な工数を確保して検証することを推奨します。

 この様に、事業としての成果を出すためには、一見同じ様なテーマのリサーチプロジェクトでも、「潜在ニーズ探索の必要性有無」により、大きく設計を変える必要があると考えてます。

5. 中編のまとめ

 以上、UXDのプロジェクトを選定する時に意識する3条件の2つ目である <その2>潜在ニーズを探る必要性の有無、について実践時に心掛けてきたことを中心にまとめてみました。

 次回は、後編として最後の条件である

<その3>改善・改良を目的とした既存事業・既存サービス

について述べさせて頂きます。