[Spark 學習小筆記] 如何使用Java 實作 vectorization (1)

Vectorization 的重要性

還記得上Anfrew Ng 的deep-learning課程前幾堂課就講到vectorization的重要性，以及對於效能會有怎樣的影響，對於矩陣運算，最直覺的反應就是寫個for loop，然後針對每個emlement 去做運算，但是其實CPU&GPU 有專門的指令集可以用來平行化專門處理這種運算，於是透過 vectorization 就可以得到顯著的效能改善，下圖就是老師上課時用python 的範例，相差了400多倍！？

Anfrew Ng 最後的結論就是盡量不要使用foor loop，盡量使用vectorization

其它什麼都可以忘掉，但是這個我倒是記起來了....

計算 Document Frequency  

最近的工作是用Spark 來計算文章的Document Frequency(DF)，因為有太多新的東西要學，所以我都會請我們家的資料科學家先舉個簡單的例子讓我比較好理解，下面就是個簡單的範例：

首先我們有四篇文章{1,2,3,4}，而文章內的集合是斷詞後的結果{A B C D E F}，每個字母代表一個詞。

1　{ A B A B }
2　{ C D C E }
3　{ E F }
4　{A}

一般來說有兩種紀錄方式，一種是Term Frequency Matrix，紀錄每篇文章分別出現哪些字的次數，另一種是Binary Frequency Matrix，單純紀錄這個字有沒有在這篇文章出現。

Term Frequency Matrix

     A B C D E F
1  2  2  0 0  0 0
2  0  0  2 1  1 0
3  0  0  0  0 1  1
4  1 0  0   0 0 0   

Binary Term Frequency Matrix

     A B C D E F
1  1  1  0 0  0 0
2  0  0  1 1 1 0
3  0  0  0 0 1  1
4  1  0  0 0 0 0   

而 Document Frequency 就是紀錄某個字總共在多少文章出現過，計算的方式就是把每篇文章的Vector 相加：

[1 1 0 0 0 0] + [0 0 1 1 1 0] + [0 0 0 0 1 1] + [1 0 0 0 0 0]

結果如下：

DF = 2 1 1  1 2 1

最後再Mapping 回去產生字對應到的DF數目

sorted DF

A 2
B 2
E 2
C 1
D 1
F 1

Spark有提供什麼樣的工具

首先我們可以利用 Spark 提供的 CountVectorizer，取得Binary Term Frequency Matrix，這邊要注意預設取得的是 Term Frequency Matrix，必須多設定setBinary(true) 才會變成Binary

CountVectorizerModel cvModel = new CountVectorizer().setInputCol("text")
                                                    .setOutputCol("feature")
                                                    .setBinary(true)
                                                    .fit(textOnly);

這時候問題來了，Spark幫我們產生的是一個SparseVector，關於SparseVector 可以參考這篇文章：Getting started with Spark — day 5，然而Spark 並沒有提供任何針對SparseVector 得運算功能(至少Java確定沒有)，網路上也是一堆人再問，通常的解法就是把他轉成 breeze的vector 來運算 (numerical processing library for Scala)，或者是轉成Python的套件來運算，收集到的討論如下：

• In Apache-spark, how to add the sparse vector?
• Scalable Sparse Matrix Multiplication in Apache Spark
• Matrix Computations and Optimization in Apache Spark 
• Matrix Operation in Spark MLlib in Java
• Matrix Libraries for Java
• Java Matrix Benchmark
• The Very Sad and Disturbing State of JVM Based Sparse Matrix Packages

還看到一個哭哭的結論(Java臭了嗎~~XD)

Breeze just doesn't provide a Java-friendly API. (And, speaking as the main author, I have no plans to: it would hamstring the API too much.)
You can probably exploit the fact that MTJ uses the same dense matrix representation as we do. (Well, almost. Their API doesn't expose majorStride, but that shouldn't be an issue for you.)

Java 矩陣運算的Solution

為了專案進度，我當然只能先用暴力的方法去做矩陣運算 (先求有再求好...Orz..)

public static SparseVector add(SparseVector s1,SparseVector s2) {

    //暴力轉成Dense vector 相加

    double[] values1 = s1.toDense().values();    double[] values2 = s2.toDense().values();

    double[] values = new double[values1.length];
    for (int i = 0; i < values.length; i++) {

        values[i] = values[i] + values1[i] + values2[i];    }

    return new DenseVector(values).toSparse();
}

但是難道沒有更好的方法嗎？應該有...

根據上網的線索目前找到兩個套件：

• MTJ
• ND4J

這兩個的底層都是使用 netlib-java 來幫忙實現硬體加速的部分，而ND4J 比較吸引我的原因是他的另一個母專案deeplearning4j

 Open-Source, Distributed, Deep Learning Library for the JVM

並且有支援Apache Spark！

故事結束了嗎？不，看樣子還有得研究，因為初步使用結果

INDArray        sum  take 6 sec
SparseVector sum  take 3 sec

我把SparkVector 轉成 INDArray去運算，速度居然比我用for loop 暴力相加還要慢...Orz..
縱使可能還沒正確設定native lib 甚至使用到GPU加速，但是這差距也未免太大？
初步懷疑是因為要做許多額外的轉換造成 overhead ，如果純矩陣運算也許會贏?

如果有任何想法，和更好的方法歡迎提供~~
或是退一萬步，改用 java去呼叫Numpy的方法?比如說 Numpy4J?
且讓我繼續研究下去~~