# 機能設計書 122-SDCA操作

## 概要

本ドキュメントは、TensorFlowにおけるSDCA（Stochastic Dual Coordinate Ascent）操作の機能設計を記述する。大規模線形分類・回帰問題のための確率的双対座標上昇法アルゴリズムを提供する。

### 本機能の処理概要

**業務上の目的・背景**：大規模データセットにおける線形モデル（ロジスティック回帰、線形回帰、SVM等）の効率的な学習が必要な場面で、SDCAアルゴリズムはL1/L2正則化付きの最適化を双対空間で実行することにより、高速な収束と優れたスケーラビリティを実現する。特にスパースな特徴量を持つ大規模データに適している。

**機能の利用シーン**：広告クリック率予測、スパムフィルタリング、大規模テキスト分類など、数百万〜数十億のサンプルと高次元のスパース特徴量を持つ線形モデルの学習に使用される。

**主要な処理内容**：
1. スパース特徴量と密特徴量を受け取り、SDCA最適化ステップを実行
2. 複数の損失関数（logistic_loss, squared_loss, hinge_loss, smooth_hinge_loss, poisson_loss）をサポート
3. L1/L2正則化によるモデルの汎化性能向上
4. SdcaShrinkL1によるL1正則化の適用（重み縮小）
5. SdcaFprintによる特徴量のフィンガープリント計算

**関連システム・外部連携**：TensorFlowの学習パイプラインに組み込まれ、tf.estimatorのLinearClassifier/LinearRegressorの内部実装として利用される。

**権限による制御**：特になし。全ユーザが利用可能な最適化操作である。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | 本機能はバックエンド最適化操作であり、直接関連する画面はない |

## 機能種別

計算処理（最適化アルゴリズムの実行）

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| sparse_example_indices | num_sparse_features * int64 | Yes | スパース特徴量のサンプルインデックス | - |
| sparse_feature_indices | num_sparse_features * int64 | Yes | スパース特徴量のフィーチャーインデックス | - |
| sparse_feature_values | num_sparse_features_with_values * float | Yes | スパース特徴量の値 | - |
| dense_features | num_dense_features * float | Yes | 密特徴量 | - |
| example_weights | float | Yes | サンプル重み | - |
| example_labels | float | Yes | サンプルラベル | - |
| sparse_indices | num_sparse_features * int64 | Yes | スパース重みのインデックス | - |
| sparse_weights | num_sparse_features * float | Yes | スパース重み | - |
| dense_weights | num_dense_features * float | Yes | 密特徴量の重み | - |
| example_state_data | float | Yes | サンプルごとの状態データ | - |
| loss_type | string | Yes | 損失関数の種類 | logistic_loss/squared_loss/hinge_loss/smooth_hinge_loss/poisson_loss |
| l1 | float | Yes | L1正則化パラメータ | - |
| l2 | float | Yes | L2正則化パラメータ | - |
| num_loss_partitions | int | Yes | 損失のパーティション数 | >= 1 |
| num_inner_iterations | int | Yes | 内部イテレーション数 | >= 1 |
| adaptive (V2) / adaptative (V1) | bool | No | 適応的学習率の使用 | デフォルト false |

### 入力データソース

学習データパイプラインから供給されるスパース/密特徴量テンソルおよびラベル。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| out_example_state_data | float [unknown, 4] | 更新されたサンプル状態データ |
| out_delta_sparse_weights | num_sparse_features * float | スパース重みの更新差分 |
| out_delta_dense_weights | num_dense_features * float | 密重みの更新差分 |

### 出力先

重み更新差分は既存の重みに加算され、モデルパラメータが更新される。

## 処理フロー

### 処理シーケンス

```
1. 入力データの受け取り
   └─ スパース特徴量、密特徴量、ラベル、重みを受け取り
2. SDCA最適化ステップの実行
   └─ 双対変数の更新と原始変数の更新差分を計算
3. L1/L2正則化の適用
   └─ 正則化項を考慮した重み更新差分の計算
4. 出力
   └─ 更新された状態データと重み差分を出力
```

### フローチャート

```mermaid
flowchart TD
    A[入力: 特徴量, ラベル, 重み] --> B[損失関数の選択]
    B --> C[SDCA双対座標上昇ステップ]
    C --> D[双対変数の更新]
    D --> E[原始変数差分の計算]
    E --> F{L1正則化?}
    F -->|Yes| G[SdcaShrinkL1による重み縮小]
    F -->|No| H[出力: delta_weights, state_data]
    G --> H
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-122-1 | 損失関数選択 | 5種類の損失関数から1つを指定 | 常時 |
| BR-122-2 | 正則化パラメータ | L1, L2正則化パラメータは非負 | 常時 |
| BR-122-3 | V1/V2互換性 | V1はadaptative（typo）、V2はadaptiveに修正 | Op選択時 |
| BR-122-4 | パーティション分割 | num_loss_partitionsによる並列処理対応 | 分散学習時 |

### 計算ロジック

SDCA最適化は以下の双対問題を解く：
- 双対変数αの更新: α_i ← α_i + Δα_i（座標上昇ステップ）
- 原始変数の更新差分: Δw = (1/λn) * Σ Δα_i * x_i
- L1正則化: SdcaShrinkL1により |w_j| < threshold の重みをゼロに縮小

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

### 操作別データベース影響一覧

本機能はデータベース操作を行わない。全ての処理はインメモリのテンソル演算である。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| InvalidArgument | パラメータエラー | 未対応のloss_typeが指定された | 有効なloss_typeを指定 |
| InvalidArgument | パラメータエラー | num_loss_partitions < 1 | 1以上の値を指定 |
| InvalidArgument | 入力形状エラー | スパース特徴量の次元不整合 | 入力データの整合性を確認 |

### リトライ仕様

リトライは不要。決定論的な最適化計算。

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

トランザクション管理なし。重み更新差分を出力するため、適用は呼び出し元で管理する。

## パフォーマンス要件

SDCAは線形モデルに対して高速に収束する。特にスパース特徴量の場合、サンプルあたりの計算コストが非ゼロ特徴量数に比例するため効率的。

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

特になし。計算グラフ内部で使用される最適化操作。

## 備考

- SdcaOptimizerV2はV1の"adaptative"タイプミスを"adaptive"に修正した版
- SdcaFprintは文字列入力をint64のフィンガープリントに変換するユーティリティOp
- SdcaShrinkL1はRef型のfloatテンソルを直接更新する

---

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

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

### 推奨読解順序

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

SDCAの入出力構造は複雑なため、まずOp定義から入出力テンソルの関係を把握する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | sdca_ops.cc | `tensorflow/core/ops/sdca_ops.cc` | スパース/密特徴量の入力構造とdelta重みの出力構造 |

**読解のコツ**: `num_sparse_features * int64`のような記法は、num_sparse_features個のint64テンソルのリストを意味する。TensorFlowのリスト入力は動的な数のテンソルをOpに渡す仕組み。

#### Step 2: エントリーポイントを理解する

SdcaOptimizerの形状推論関数が入出力の関係を定義する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | sdca_ops.cc | `tensorflow/core/ops/sdca_ops.cc` | ApplySdcaOptimizerShapeFn関数 |

**主要処理フロー**:
1. **26-39行目**: ApplySdcaOptimizerShapeFn - sparse_weightsとdense_weightsの形状をそのまま出力形状として設定し、out_example_state_dataを[unknown, 4]に設定
2. **41-66行目**: SdcaOptimizer (V1) - 5種類の損失関数と"adaptative"(typo)属性
3. **69-94行目**: SdcaOptimizerV2 - typoを修正した"adaptive"属性
4. **96-101行目**: SdcaShrinkL1 - L1正則化による重み縮小（Ref型入力で直接更新）
5. **103-113行目**: SdcaFprint - 文字列のフィンガープリント計算（出力: [入力長, 2]）

#### Step 3: サポートOp群を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | sdca_ops.cc | `tensorflow/core/ops/sdca_ops.cc` | SdcaShrinkL1, SdcaFprint |

**主要処理フロー**:
- **96-101行目**: SdcaShrinkL1 - num_features個のRef(float)テンソルを直接操作してL1正則化を適用
- **103-113行目**: SdcaFprint - 1次元文字列テンソルを入力し、[N, 2]のint64テンソルを出力

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

```
sdca_ops.cc (Op定義)
    |
    +-- ApplySdcaOptimizerShapeFn (形状推論: V1/V2共通)
    |
    +-- REGISTER_OP("SdcaOptimizer")      ... V1 (adaptative typo)
    +-- REGISTER_OP("SdcaOptimizerV2")    ... V2 (adaptive 修正)
    +-- REGISTER_OP("SdcaShrinkL1")       ... L1正則化
    +-- REGISTER_OP("SdcaFprint")         ... フィンガープリント
```

### データフロー図

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

sparse_example_indices ──┐
sparse_feature_indices ──┤
sparse_feature_values  ──┤
dense_features         ──┼──▶ SdcaOptimizer ──────▶ out_example_state_data
example_weights        ──┤                            out_delta_sparse_weights
example_labels         ──┤                            out_delta_dense_weights
sparse_weights         ──┤
dense_weights          ──┤
example_state_data     ──┘

sparse_weights ──────────▶ SdcaShrinkL1 ──────▶ (weights直接更新)

input (string) ──────────▶ SdcaFprint ────────▶ output [N, 2] (int64)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| sdca_ops.cc | `tensorflow/core/ops/sdca_ops.cc` | ソース | Op定義（4つのOp登録） |
| common_shape_fns.h | `tensorflow/core/framework/common_shape_fns.h` | ヘッダ | 共通形状推論ユーティリティ |
| op.h | `tensorflow/core/framework/op.h` | ヘッダ | REGISTER_OPマクロ |
| shape_inference.h | `tensorflow/core/framework/shape_inference.h` | ヘッダ | 形状推論フレームワーク |
