# 機能設計書 78-SVD++

## 概要

本ドキュメントは、Apache Spark GraphXにおけるSVD++（SVD Plus Plus）アルゴリズムの設計を記述する。

### 本機能の処理概要

SVD++は、協調フィルタリングのための行列分解ベースの推薦アルゴリズムである。論文「Factorization Meets the Neighborhood: a Multifaceted Collaborative Filtering Model」（Koren, 2008）に基づく実装。ユーザーとアイテムの潜在因子を学習し、暗黙的フィードバック（ユーザーがどのアイテムを評価したか）も考慮する。

**業務上の目的・背景**：EC・コンテンツ配信サービスなどにおけるレコメンデーションシステムの構築。ユーザーの評価履歴に基づき未評価アイテムの予測評価を算出する。

**機能の利用シーン**：映画推薦、商品推薦、コンテンツ推薦。既知の評価データから未知の評価を予測する。

**主要な処理内容**：
1. エッジ（ユーザー-アイテム間の評価）からグラフを構築
2. グローバル平均評価uを算出
3. 初期バイアスとノルム（|N(u)|^-0.5）を計算
4. maxIters回の反復で以下を実行:
   - Phase 1: ユーザーノードで pu + |N(u)|^-0.5 * sum(y) を計算
   - Phase 2: 予測と実測の誤差に基づきp, q, y, バイアスを更新
5. 訓練データ上の二乗誤差を計算

**関連システム・外部連携**：GraphXのグラフ構造データ管理（No.71）とSparkのBLAS（線形代数）ライブラリに依存。Pregelは使用せず、aggregateMessagesを直接使用。

**権限による制御**：特に権限による制御は行われない。

## 関連画面

本機能に直接関連するUI画面はない。

## 機能種別

計算処理 / 機械学習アルゴリズム

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| edges | RDD[Edge[Double]] | Yes | ユーザーID(src) - アイテムID(dst) 間の評価値エッジ | - |
| conf | SVDPlusPlus.Conf | Yes | アルゴリズム設定 | maxIters > 0, maxVal > minVal |

### Confパラメータ詳細

| フィールド | 型 | 説明 |
|-----------|-----|------|
| rank | Int | 潜在因子の次元数 |
| maxIters | Int | 最大反復回数 |
| minVal | Double | 予測値の下限クリップ |
| maxVal | Double | 予測値の上限クリップ |
| gamma1 | Double | バイアス学習率 |
| gamma2 | Double | 因子学習率 |
| gamma6 | Double | バイアス正則化係数 |
| gamma7 | Double | 因子正則化係数 |

### 入力データソース

RDD[Edge[Double]] - 各エッジはユーザー(srcId) からアイテム(dstId) への評価値(attr) を表す。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| Graph[(Array[Double], Array[Double], Double, Double), Double] | Graph | 頂点属性: (p/q, y/pu+|N|^-0.5*sum(y), bias, norm/error) |
| u | Double | グローバル平均評価値 |

頂点属性の4要素:
- _1: Array[Double] - ユーザーの場合 p（潜在因子）、アイテムの場合 q（潜在因子）
- _2: Array[Double] - ユーザーの場合 pu + |N(u)|^-0.5 * sum(y)、アイテムの場合 y（暗黙因子）
- _3: Double - バイアス項 bu / bi
- _4: Double - ユーザーの場合 |N(u)|^-0.5、アイテムの場合 訓練誤差

### 出力先

メモリ上の (Graph, Double) タプル

## 処理フロー

### 処理シーケンス

```
1. 初期化
   ├─ グローバル平均評価 u を計算: sum(ratings) / count(ratings)
   ├─ Graph.fromEdges でグラフ構築（頂点属性: ランダム初期化）
   └─ 初期バイアス/ノルム計算:
       ├─ bu = avg(ratings[u]) - u
       └─ norm = 1 / sqrt(|N(u)|)

2. 反復更新 (maxIters回)
   ├─ Phase 1: ユーザーノードの複合因子計算
   │   ├─ aggregateMessages: アイテムの y をユーザーに送信
   │   └─ outerJoinVertices: pu + norm * sum(y) を計算
   │
   └─ Phase 2: パラメータ更新
       ├─ aggregateMessages (sendMsgTrainF):
       │   ├─ 予測値 pred = u + bu + bi + q^T * (pu + norm*sum(y))
       │   ├─ pred をminVal/maxValでクリップ
       │   ├─ 誤差 err = actual - pred
       │   ├─ updateP = (err * q - gamma7 * p) * gamma2
       │   ├─ updateQ = (err * (pu+norm*sum(y)) - gamma7 * q) * gamma2
       │   ├─ updateY = (err * norm * q - gamma7 * y) * gamma2
       │   └─ bias更新 = (err - gamma6 * bias) * gamma1
       └─ outerJoinVertices: パラメータ更新適用

3. 訓練誤差計算
   ├─ sendMsgTestF で予測と実測の二乗誤差を計算
   └─ アイテムノードの _4 に誤差を蓄積

4. 結果返却: (Graph, u)
```

### フローチャート

```mermaid
flowchart TD
    A[評価エッジRDD] --> B[グローバル平均u計算]
    B --> C[Graph.fromEdges + ランダム初期化]
    C --> D[初期バイアス/ノルム計算]
    D --> E{maxIters回反復}
    E -->|Phase 1| F[ユーザー複合因子計算: pu + norm*sum_y]
    F -->|Phase 2| G[誤差計算 + パラメータ更新]
    G --> E
    E -->|完了| H[訓練誤差計算]
    H --> I[Graph + u を返却]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-78-01 | 予測式 | rui = u + bu + bi + qi^T * (pu + \|N(u)\|^-0.5 * sum(yj)) | 全評価 |
| BR-78-02 | クリッピング | 予測値をminVal/maxValの範囲にクリップ | Phase 2 |
| BR-78-03 | 正則化 | gamma6でバイアス正則化、gamma7で因子正則化 | パラメータ更新時 |
| BR-78-04 | BLAS使用 | ベクトル内積・スカラー乗算・ベクトル加算にnativeBLASを使用 | 全ベクトル演算 |

### 計算ロジック

- **予測式**: `u + usr._3 + itm._3 + BLAS.nativeBLAS.ddot(rank, q, 1, usr._2, 1)` (SVDPlusPlus.scala 106行目)
- **p更新**: `(err * q - gamma7 * p) * gamma2` (110-113行目)
- **q更新**: `(err * usr._2 - gamma7 * q) * gamma2` (114-117行目)
- **y更新**: `(err * usr._4 * q - gamma7 * y) * gamma2` (118-121行目)
- **バイアス更新**: `(err - gamma6 * bias) * gamma1` (122-123行目)

## データベース操作仕様

GraphXはデータベースを直接操作しない。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| IllegalArgumentException | 入力検証 | maxIters <= 0 | 正の整数を指定 |
| IllegalArgumentException | 入力検証 | maxVal <= minVal | maxVal > minValを保証 |

### リトライ仕様

RDDの耐障害性メカニズムに従う。

## トランザクション仕様

トランザクション機構は存在しない。

## パフォーマンス要件

- nativeBLAS（OpenBLAS等）の使用によりベクトル演算を高速化
- 各イテレーションでcache()/unpersist()を使用しメモリを管理
- materialize(g) で明示的にRDDの計算を強制（vertices.count() + edges.count()）

## セキュリティ考慮事項

特になし。

## 備考

- ランダム初期化（Random.nextDouble()）を使用するため、結果は非決定的。TODO: 固定シードの使用が検討中（68行目のコメント）
- Phase 2のmergeMessage実装にバグの可能性あり：out2の計算で`g2._2`を2回使用している（159-160行目）

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: データ構造を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | SVDPlusPlus.scala | `graphx/src/main/scala/org/apache/spark/graphx/lib/SVDPlusPlus.scala` | Conf設定クラス (30-39行目) と頂点属性のタプル型 (Array[Double], Array[Double], Double, Double) |

**読解のコツ**: 頂点属性の4要素タプルはユーザーノードとアイテムノードで異なる意味を持つ。_1はp(ユーザー)/q(アイテム)、_2はpu+|N|^-0.5*sum(y)(ユーザー)/y(アイテム)、_3はバイアス、_4はノルム(ユーザー)/訓練誤差(アイテム)。

#### Step 2: 初期化を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | SVDPlusPlus.scala | `graphx/src/main/scala/org/apache/spark/graphx/lib/SVDPlusPlus.scala` | defaultF (67-72行目), グローバル平均u (75-77行目), 初期バイアス/ノルム (85-96行目) |

#### Step 3: 反復更新を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | SVDPlusPlus.scala | `graphx/src/main/scala/org/apache/spark/graphx/lib/SVDPlusPlus.scala` | Phase 1 (129-149行目), Phase 2のsendMsgTrainF (98-124行目), Phase 2の集約+更新 (152-176行目) |

**主要処理フロー**:
- **58-59行目**: run メソッドのシグネチャ。入力はRDD[Edge[Double]]とConf
- **67-72行目**: defaultF - ランダムベクトルで初期化
- **75-77行目**: グローバル平均評価u計算
- **80行目**: Graph.fromEdges でグラフ構築
- **85-96行目**: 初期バイアスとノルム計算
- **126-177行目**: メイン反復ループ
- **180-203行目**: 訓練誤差計算

### プログラム呼び出し階層図

```
SVDPlusPlus.run(edges, conf)
    |
    +-- edges.map(e => (e.attr, 1L)).fold [グローバル平均u計算]
    +-- Graph.fromEdges(edges, defaultF(rank))
    +-- g.aggregateMessages [初期バイアス/ノルム計算]
    +-- g.outerJoinVertices(t0) [初期化適用]
    |
    +-- for (i <- 0 until maxIters):
    |       |
    |       +-- Phase 1:
    |       |   +-- g.aggregateMessages [yベクトル集約]
    |       |   +-- g.outerJoinVertices [pu + norm*sum(y)]
    |       |
    |       +-- Phase 2:
    |           +-- g.aggregateMessages(sendMsgTrainF) [誤差計算+更新量]
    |           +-- g.outerJoinVertices [パラメータ更新適用]
    |
    +-- g.aggregateMessages(sendMsgTestF) [訓練誤差計算]
    +-- (Graph, u) を返却
```

### データフロー図

```
[入力]                       [処理]                         [出力]

RDD[Edge[Double]] ------> グローバル平均u計算
(ユーザーID,                    |
 アイテムID,             Graph構築 + 初期化
 評価値)                       |
                         反復更新
                         Phase1: 暗黙因子集約
                         Phase2: SGD更新
                               |
                         訓練誤差計算 -------> (Graph, u)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| SVDPlusPlus.scala | `graphx/src/main/scala/org/apache/spark/graphx/lib/SVDPlusPlus.scala` | ソース | SVD++アルゴリズム実装 |
| Graph.scala | `graphx/src/main/scala/org/apache/spark/graphx/Graph.scala` | ソース | グラフ抽象クラス |
| BLAS.scala | `mllib/src/main/scala/org/apache/spark/ml/linalg/BLAS.scala` | ソース | 線形代数演算 |
