SparseVector

author: 371tti, t3tra-dev, ChatGPT

article, search, information-retrieval

疎ベクトルとは

疎ベクトル（Sparse Vector）は、多くの要素がゼロであるベクトルを指します。これに対して、ほとんどの要素がゼロではないベクトルは密ベクトル（Dense Vector）と呼ばれます。

例えば、次のようなベクトルを考えます：

密ベクトル: $𝐯 = [\begin{matrix} 1 & 2 & 3 & 4 & 5 \end{matrix}]$
疎ベクトル: $𝐯 = [\begin{matrix} 1 & 0 & 0 & 0 & 5 \end{matrix}]$

疎ベクトルは、ゼロ以外の要素が少ないため、効率的なデータ表現と計算が可能です。

疎ベクトルの疎性 (スパース性)

疎ベクトルの「疎性」とは、データの効率的な表現と計算を可能にする特性を指すことがあります。具体的には、以下のような利点が挙げられます：

メモリ効率
- ゼロ要素を保存しないことで、メモリ使用量を大幅に削減できます。ただし、実際にメモリ使用量が削減されるかどうかは、実装方法やデータ構造に依存します。例えば、辞書型やリスト型を使用する場合、インデックスやポインタの管理に追加のメモリが必要となるため、必ずしも効率的とは限りません。
計算効率
- ゼロ要素を無視して計算を行うため、処理速度が向上します。
スケーラビリティ
- 大規模なデータセットに対しても効率的に操作を行うことができます。

この疎性により、疎ベクトルは機械学習や科学計算などの分野で広く利用されています。

疎ベクトルの実装方法

疎ベクトルは、ゼロ以外の要素を効率的に管理するために、以下のようなデータ構造を使用して実装されます。これらの方法は、特定のプログラミング言語に依存せず、一般的な概念として理解できます。

辞書型（連想配列）
- キーにインデックス、値に非ゼロ要素を格納します。
- メリット：ランダムアクセスが高速。
- デメリット：インデックスと値のペアを管理するため、追加のメモリが必要。
リスト型（インデックスと値のペアの配列）
- 非ゼロ要素のインデックスと値をペアとして格納します。
- メリット：メモリ効率が比較的高い。
- デメリット：ランダムアクセスが遅い。
圧縮行形式（Compressed Row Storage, CRS）
- 主に行列の疎な表現に使用されますが、ベクトルにも応用可能です。
- 3つの配列を使用：
  - 値の配列（非ゼロ要素のみを格納）
  - インデックスの配列（非ゼロ要素の位置を格納）
  - 行の開始位置を示す配列（行列の場合）。
- メリット：メモリ効率が非常に高い。
- デメリット：実装がやや複雑。
ビットマップ表現
- 各要素がゼロか非ゼロかを示すビットマップを使用し、非ゼロ要素のみを別の配列に格納します。
- メリット：ゼロ要素の管理が簡単。
- デメリット：ビットマップの管理に追加の計算コストがかかる。

Rustによるリスト型の疎ベクトル実装例

以下は、リスト型を使用した疎ベクトルのRustによる実装例です。この方法では、非ゼロ要素のインデックスと値をペアとして格納します。

#[derive(Debug)]
struct SparseVector {
    elements: Vec<(usize, f64)>,
}

impl SparseVector {
    // 新しい疎ベクトルを作成
    fn new() -> Self {
        SparseVector { elements: Vec::new() }
    }

    // 要素を設定
    fn set(&mut self, index: usize, value: f64) {
        if let Some(pos) = self.elements.iter().position(|&(i, _)| i == index) {
            if value != 0.0 {
                self.elements[pos] = (index, value);
            } else {
                self.elements.remove(pos);
            }
        } else if value != 0.0 {
            self.elements.push((index, value));
        }
    }

    // 要素を取得
    fn get(&self, index: usize) -> f64 {
        self.elements.iter().find(|&&(i, _)| i == index).map_or(0.0, |&(_, v)| v)
    }

    // 内積計算
    fn dot(&self, other: &SparseVector) -> f64 {
        let mut result = 0.0;
        for &(i, v) in &self.elements {
            if let Some(&(_, ov)) = other.elements.iter().find(|&&(oi, _)| oi == i) {
                result += v * ov;
            }
        }
        result
    }
}

fn main() {
    let mut vec1 = SparseVector::new();
    vec1.set(0, 1.0);
    vec1.set(4, 5.0);

    let mut vec2 = SparseVector::new();
    vec2.set(0, 2.0);
    vec2.set(4, 3.0);

    println!("vec1: {:?}", vec1);
    println!("vec2: {:?}", vec2);
    println!("Dot product: {}", vec1.dot(&vec2));
}

この実装では、Vecを使用して非ゼロ要素を格納し、内積計算などの操作を効率的に行います。

疎ベクトルの応用例

疎ベクトルは、以下のような分野で広く使用されています：

機械学習
- TF-IDF（単語の重要度を表す指標）やワード埋め込みで使用されます。
- 例：文書の特徴量を疎ベクトルで表現することで、計算効率を向上。
グラフ理論
- 隣接行列の表現に使用されます。
- 疎なグラフでは、隣接リストや疎行列を使用することでメモリ効率を向上。
科学計算
- 大規模なシミュレーションや数値計算で使用されます。
- 疎行列を用いた連立方程式の解法（例：共役勾配法）。

疎ベクトルの課題

疎ベクトルには以下のような課題も存在します：

実装の複雑さ
- データ構造の選択や操作が密ベクトルに比べて複雑です。
特定の操作での非効率性
- 要素の挿入や削除が頻繁に行われる場合、効率が低下することがあります。
キャッシュ効率の低下
- 疎ベクトルはメモリ上で連続して格納されないため、キャッシュ効率が悪化する可能性があります。

疎ベクトルは、データの性質や用途に応じて適切に選択・実装する必要があります。