[解析手法] - RDBを用いた行列計算の手法
はじめに
リレーショナルデータベース（RDB)の元となっている Edgar.F.Codd の理論「関係代数」（論文：A Relational Model of Data for Large Shared Data Banks）は 「集合論」 をその土台として直接的に用いています。
実際、SQLで行うデータ操作は一部の例外を除き集合論においての集合演算そのものです。
現代数学の大部分が集合論の上に成り立っていることを考えれば、集合の要素を格納でき、集合操作を行うことができる RDB は「データを格納する」ということ以上に、出来ることが数多くあると考えられ、そしてそれは真です。
「データを格納して検索して引き出す」という用途にだけ利用するのであれば、今流行りの Redis などに代表される NoSQL の方が優っているところはあるのも事実だと思いますが、RDBの真骨頂はそんなところではない と私は思っています。
今回はそんな数多くある RDB の応用利用のうち、「RDBを用いた行列計算」を書かせて頂こうと思います。
動機
なぜこんなことを考えたのかを記載しておきます。
私が以前携わっていた業務において、顧客に対してリコメンドを出す仕組みを作る機会がありました。
個別の顧客に対してその顧客に最適な購買確率が高い商品を推薦するというものです。
今回の SQLで行列計算を行うことを思いついたのは、この機会においての現実的な制約を突破する為でした。
いろいろなリコメンド手法を検討した結果、現実的な方法として「協調フィルタリング」のアルゴリズムを採用することになりました。
協調フィルタリングでは類似度を計算する必要があります。
この時はcos距離を採用しました。
このcos距離を計算するために行列計算が必要になります。
対象となる顧客と製品は、数百万人の顧客に対して数千の商品です。
そのため、巨大行列計算を行う必要がありました。
しかし困ったことに、現実的な時間内で顧客毎の推薦リストを計算することが出来るサーバーマシンが存在しませんでした。
当時は３大クラウドが企業に本格的に受け入れられる前でしたので、計算リソースと言えば社内のオンプレミスのサーバー群だけでした。
また、行列のスパース性を用いても社内のサーバーではとても現実的な時間では終わらなかったのです。
その時の社内計算リソースとして最も高速であったのが、データベースとして利用していた Oracle社の Exadata というデータベースアプライアンスでした。
（大変高速かつ大容量のデータベースアプライアンスです）
そこで私は巨大な行列計算をこの Exadata にまかせることを思いつきました。
そして、今回の手法を用いることで、プログラムからは計算の指示やリストの整形などの指示だけを出す形にして、数分以内に推薦リストの作成計算を終わらせることに成功しました。
以上が、私が行列計算をSQLで行おうと思った動機です。
昔語りが長くなりましたが、この手法は使用場所によっては大変有用な手法だと思います。
実際、RDBの集合計算は自前でプログラムを行うより大変高速です。
データの管理とデータに関する計算はRDB内でDBMSに行わせ、プログラム側は出来た結果だけを受け取る、というのはある意味理にかなっており効率が良いと私はこの時感じました。
是非みなさんも機会があればこのようにシステムを作ってみてはいかがでしょうか。
「推薦」いたします。
今回の結論
先に今回の結論を以下に記載しておきます。
以下の3つの行列演算について記述します。
- 定数倍
- 和
- 積
尚、記載しているSQL文は、SQLite にて動作を検証しています。
(こちらの DB Browser for SQLite を使うと便利です。)
また、関係代数に関する数式に関しては、こちら をご参照ください。
定数倍
対象の行列を
この定数倍を関係代数理論に則った集合論の記号で記述すれば、
SQLに即して詳しく書けば以下。
SQLで記述すれば、
SELECT row, col, α * value as value
FROM A;
となります。
和
対象の行列を
ただし、
数式はこちら。
ここで添字
SQLは以下。
SELECT A.row, A.col, A.value + B.value as value
FROM A, B
WHERE A.row = B.row AND A.col = B.col;
※ A.row, A.col は A.row, B.col,B.row, A.col, B.row, B.col でも構いません。
ここで行番号と列番号の組（row, col）に欠損がある場合（COO形式の場合）は、上のSQLでは間違った結果が返ります。
これを回避するための修正版は以下になります。
SELECT D.row, D.col, ifnull(A.value, '0') + ifnull( B.value, '0') as value
FROM (
SELECT A.row, A.col FROM A
UNION
SELECT B.row, B.col FROM B
) AS D
LEFT OUTER JOIN A
ON D.row = A.row AND D.col = A.col
LEFT OUTER JOIN B
ON D.row = B.row AND D.col = B.col ;
これに対する数式は以下
となります。
積
同じく対象の行列を
ただし行列
数式はこちら。
SQLは
SELECT Arow as row, Bcol as col, sum(value) as value
FROM (
SELECT A.row as Arow, A.col as Acol, B.row as Brow, B.col as Bcol, A.value * B.value as value
FROM A, B
WHERE A.col = B.row
)
GROUP BY Arow, Bcol;
となります。
解説
以下、上記の結論を解説していきます。
準備
例示に使用する行列
今回の説明で例示に使用する３つの行列を以下とします。
もちろん、例示に用いるだけで、今回の手法がこれらの行列や行列型に限定されるわけではありません。
RDB上の行列表現
RDB上には、行列を以下のように表現して格納します。
| row | col | value |
|---|---|---|
| 1 | 1 | |
| 1 | 2 | |
| i | j | |
| m | n |
上記の例示行列
A
| row | col | value |
|---|---|---|
| 1 | 1 | 5 |
| 1 | 2 | 4 |
| 1 | 3 | 5 |
| 2 | 1 | 0 |
| 2 | 2 | 8 |
| 2 | 3 | 9 |
B
| row | col | value |
|---|---|---|
| 1 | 1 | 6 |
| 1 | 2 | 0 |
| 1 | 3 | 2 |
| 2 | 1 | 4 |
| 2 | 2 | 5 |
| 2 | 3 | 0 |
C
| row | col | value |
|---|---|---|
| 1 | 1 | 5 |
| 1 | 2 | 4 |
| 1 | 3 | 0 |
| 2 | 1 | 1 |
| 2 | 2 | 0 |
| 2 | 3 | 6 |
| 3 | 1 | 3 |
| 3 | 2 | 6 |
| 3 | 3 | 8 |
よく言われるデータの「縦持ち形式」です。
今回記載している演算方法を使用するには、この縦持ち形式の形で行列がRDBに格納されている必要があります。
上の形式をみるとデータに
この箇所はレコードごと削除してしまって構いません。
例えば
B
| row | col | value |
|---|---|---|
| 1 | 1 | 6 |
| 1 | 3 | 2 |
| 2 | 1 | 4 |
| 2 | 2 | 5 |
この形式は Coordinate(COO)形式 として知られている形式です。
並列計算に向いていないと言われているようですが、今回は計算はRDBに任せてしまうので関係ありません。
このCOO形式で格納した場合、行列の中の値に
定数倍と積は変わりませんが、和の場合は少々複雑になります。
どちらを使うかは、ケースによって変わるかと思います。
各演算の解説
以下、各演算の詳細を記載します。
定数倍
定数倍は全ての要素に一定値をかける演算なので、全ての要素を取り出して精数倍
関係代数としてちゃんとわかるように、変化するカラム名としないカラム名も明記して、
とかけます。
これをSQLで実現するには、value の行を全て定数倍してやればよいです。
SELECT row, col, α * value as value
FROM A;
これで行列の定数倍が実行されます。
和
行列の和は、同じ場所にある要素同士を足せば良いです。
よって、行と列それぞれの添字が同じ要素同士を足し合わせることで実現できます。
これをSQLにすると、
SELECT A.row, A.col, A.value + B.value as value
FROM A, B
WHERE A.row = B.row AND A.col = B.col;
です。ここで、A.row, A.col は A.row, B.col,B.row, A.col, B.row, B.col でも構いません。
全ての行と列の添字が row,col 列にある場合はこれで良いですが、COO形式を使用して 0 の部分のレコードを削除している場合、このSQLを使用するとどちらか一方の行列添字の値が 0 の箇所が足し合わせされず 0 をとなってしまいます。
※ 実行結果がこのような間違った行列を返してきます。
NULL の処理を行いつつ正しい結果を出すには工夫が必要です。
まず、
SELECT A.row, A.col FROM A
UNION
SELECT B.row, B.col FROM B ;
次に、行列
SELECT *
FROM (
SELECT A.row, A.col FROM A
UNION
SELECT B.row, B.col FROM B
) as D
LEFT OUTER JOIN A
ON D.row = A.row AND D.col = A.col ;
さらに行列
SELECT *
FROM (
SELECT A.row, A.col FROM A
UNION
SELECT B.row, B.col FROM B
) AS D
LEFT OUTER JOIN A
ON D.row = A.row AND D.col = A.col
LEFT OUTER JOIN B
ON D.row = B.row AND D.col = B.col ;
値の場所がNULLだった場合、0 に置換する関数
ifnull(value, '0')
を各値に適用して、足し算を実行します。
SELECT D.row, D.col, ifnull(A.value, '0') + ifnull( B.value, '0') as value
FROM (
SELECT A.row, A.col FROM A
UNION
SELECT B.row, B.col FROM B
) AS D
LEFT OUTER JOIN A
ON D.row = A.row AND D.col = A.col
LEFT OUTER JOIN B
ON D.row = B.row AND D.col = B.col ;
これで行列の和が実行されます。
積
行列の積は、左行列の列と右行列の行を互いに掛け合わせて和をとります。
その為、左行列の列番号と右行列の行番号を内部結合してテーブルを作り、その後掛け合わせ、足し合わせを実行してやればよいです。
ここでは対象の例示行列は
そして、同時に value 同士を掛け合わせます。
SELECT A.row as Arow, A.col as Acol, C.row as Crow, C.col as Ccol, A.value * C.value as value
FROM A, C
WHERE A.col = C.row ;
または
SELECT A.row as Arow, A.col as Acol, B.row as Brow, B.col as Bcol, A.value * B.value as value
FROM A INNER JOIN B
ON A.col = B.row ;
ここではCOO形式を使用していたとしても、行列の和演算の時のようなNULLの処理をしてやる必要がありません。
なぜならNULLの部分は 0 に該当するので、掛け合わせると 0 になり、この後の足し算に影響しなくなるからです。
正直これはとても嬉しい性質でした。
次に
SELECT Arow as row, Ccol as col, sum(value) as value
FROM (
SELECT A.row as Arow, A.col as Acol, C.row as Crow, C.col as Ccol, A.value * C.value as value
FROM A, C
WHERE A.col = C.row
)
GROUP BY Arow, Ccol;
これで行列の積が実行されます。
これで行列の 定数倍・和・積 が計算できるようになりました。
おわりに
行列の 定数倍・和・積 が計算できるようになったので、ベクトル演算や内積計算もRDBで行うことができます。
またさらに演算を工夫して、今度はテンソル計算までできるように挑戦してみようかと思っています。
リコメンドシステムや、特定のバッチデータ解析システムなどにおいて、サーバーでゴリゴリ計算を行うのではなく、行列演算をRDBに任せるようなシステムを組んでみても面白いと思います。
ぜひ感想など聞かせてください。
Discussion