[2020/07/30] Machine Learning 輪講

[agatan]

Why

Machine Learning 輪講は最新の技術や論文を追うことで、エンジニアが「技術で解決できること」のレベルをあげていくことを目的にした会です。

prev. #59

What

話したいことがある人はここにコメントしましょう！ 面白いものを見つけた時点でとりあえず話すという宣言だけでもしましょう！

[yuko-i]

A Counterfactual Framework for Seller-Side A/B Testing on Marketplaces

https://research.fb.com/publications/a-counterfactual-framework-for-seller-side-a-b-testing-on-marketplaces/

SIGIR 2020から。

FaceBook Marketplaces で、販売者と購入者の両方の体験を向上させたい。通常、購入者側の目的を最適化したランキングを作成する (クリック率・購入率)。しかし、サービスの長期的な成功には、販売者側が良い体験をしていること大切。しかし、販売者側のA/Bテストは、ランキングの変更の影響を計測するのが難しい。そのため、新しいフレームワークを提案する。

• control グループ (既存アルゴリズム mAによって、購入者側の目的の最適化で作成されたランキング)
• Treatment グループ (新アルゴリズム mBによって、購入者側と販売者側の両方の目的で最適化で作成されたランキング)

なぜ、販売者側のA/Bテストを正しく行うのは難しいか

販売者側のA/Bテストを行うとする。販売者の1%をTreatment グループ(mB)、別の 1%をcontrol グループ(mA)とする。

mBは「新規販売者のアイテムをブーストさせる」という処理が入る。Treatment グループの新規販売者のアイテム(図3でいうとitem4)は高ランクになる。リリース時は全新規販売者のアイテムがブーストするので、A/Bテストで高ランクであったitem4のランクが低くなりうる。

因果関係における仮定、stable unit treatment value assumption (SUTVA : 該当個人の結果は、他者の結果や露出率に影響を受けないという仮定) に反しているので、A/Bテストが正しくできていない。

counterfactual experiment frameworkの提案

• Pre-test : Treatment グループのアイテムの順位をmBで決定。それ以外 (99%) は全てmAで順位を決定。
• Back-test : Control グループのアイテムの順位をmAで決定。それ以外 (99%) は全てmBで順位を決定。 オンラインテストの途中でPre-testからBack-testに切り替える。

販売者が受け取るメッセージ数の影響を最小化し、Pre-test(青)とBack-test(オレンジ)の両方で、販売率を約2.5％、統計的有意に改善された。SUTVAに反しておらず、テスト中とリリース後の販売者側の指標の結果は一貫する。

このフレームワークで購入者側のA/Bも行うことができる。Treatment 購入者グループに、ルール(多分 Pre-test)を適応し、 Control 購入者グループには適応しない。メッセージ送信数を比べる。

Treatment2,3は新規販売者のアイテムをよりアグレッシブにブーストするランキング。 購入者のメッセージ送信数のA/Bの差 (青)と、販売者側のメッセージ受信数のA/Bの差 (オレンジ) がTreatmentごとにほぼ同じ結果である。販売者側のA/Bテストが信頼できることを表している。

[agatan]

ProNE: Fast and Scalable Network Representation Learning

• https://www.microsoft.com/en-us/research/publication/prone-fast-and-scalable-network-representation-learning/
• https://www.ijcai.org/Proceedings/2019/0594.pdf
• IJCAI 2019

爆速 Network Embedding 手法。 ちょっと試して感動したので共有します。

whose single-thread version is 10–400× faster than efficient network embedding benchmarks with 20 threads, including LINE, DeepWalk, node2vec, GraRep, and HOPE.

とか

the single-thread ProNE requires only 29 hours to embed a network of hundreds of millions of nodes while it takes LINE weeks and DeepWalk months by using 20 threads.

とあってかなり激しい。

まず、Negative Sampling ベースの Network Embedding 学習方法を、Sparse Matrix Factorization に落とし込む。 SMF は、randomized truncated SVD で高速に解くことができるので、これによって爆速でそれなりに良い Embedding を得ることができる。

さらに、上記のプロセスによって得た Embedding は局所的な特徴しか捉えられていないため、Spectral Propagation によって帯域的な特徴を加味した Embedding になるよう、先の Embedding を Enhance する手法を提案している。 （こちらは既存の NE に追加で適用可能で、実験では DeepWalk や LINE に Spectral Propagation を行うことで性能が向上することを確かめている。）

SMF の計算量は O(|V|d^2 + |E|) で、 Spectral Propagation の計算量は O(|V|d ^ 2 + k|E|) なので、全体の計算量は O(|V|d ^ 2 + k|E|) となる。 空間計算量は O(|V|d + |E|) らしい（こっちは論文中では詳細が省かれているが、まぁ確かにそうかなという感じ）

実際に動かしてみたところ、数千万エッジ & 数百万ノードのグラフに対して、32 次元ベクトルを学習させるくらいなら 3 分で終わる（ノードを連番 ID に変換する処理の方がボトルネックになるくらいでビビる） 性能は PBG で 8h くらいかけて育てた Embedding と同等かやや良いくらい。 パッと試すには十分すぎる性能なので、積極的に使ってみても良いかも？

著者実装が https://github.com/THUDM/ProNE にある。 ↓データの読み込み部分が Networkx 経由で、手元のデータだとメモリがしんどすぎたので、直接 csr_matrix に読むように書き換えてちょっと utility 足した版

```python """Implementation of ProNE (https://www.microsoft.com/en-us/research/publication/prone-fast-and-scalable-network-representation-learning/) Original code: https://github.com/THUDM/ProNE. """ from typing import Optional, Sequence, Any, List, Tuple, Union import numpy as np import scipy.sparse import scipy.linalg import scipy.special import sklearn.base from sklearn import preprocessing from sklearn.utils.extmath import randomized_svd class ProNE(sklearn.base.BaseEstimator): def __init__( self, dim: int, step: int = 10, alpha: float = 0.75, mu: float = 0.1, theta: float = 0.5, encode_labels: bool = True, verbose: bool = False, random_state: Union[int, np.random.RandomState, None] = None, ) -> None: super().__init__() self.dim = dim self.step = step self.alpha = alpha self.mu = mu self.theta = theta self.verbose = verbose self.random_state = random_state self.encode_labels = encode_labels self.label_encoder_: Optional[preprocessing.LabelEncoder] = None def fit( self, nodes_a: Sequence[Any], nodes_b: Sequence[Any], ): if self.encode_labels: nodes = np.concatenate([nodes_a, nodes_b]) self.label_encoder_ = preprocessing.LabelEncoder() nodes = self.label_encoder_.fit_transform(nodes) if self.verbose: print(f"[ProNE] Construct label dictionary: {len(self.label_encoder_.classes_)} classes") nodes_a = nodes[:len(nodes_a)] nodes_b = nodes[len(nodes_a):] self.node_number_ = max(nodes_a.max(), nodes_b.max()) + 1 matrix0 = scipy.sparse.csr_matrix( (np.ones(len(nodes_a), dtype=np.float32), (nodes_a, nodes_b),), shape=(self.node_number_, self.node_number_), ) if self.verbose: print("[ProNE] Start Pre Factorization") features_matrix = self._pre_factorization(matrix0) if self.verbose: print("[ProNE] Start Chebyshev Gaussian") self.embeddings_ = self._chebyshev_gaussian(matrix0, features_matrix) print(f"[ProNE] RMSE: {np.sqrt(np.sum((features_matrix - self.embeddings_) ** 2)):.4f}") def _encode_nodes(self, nodes) -> np.ndarray: if self.encode_labels: return self.label_encoder_.transform(nodes) return nodes def _inverse_nodes(self, nodes) -> np.ndarray: if self.encode_labels: return self.label_encoder_.inverse_transform(nodes) return nodes def transform(self, nodes) -> np.ndarray: nodes = self._encode_nodes(nodes) return self.embeddings_[nodes] def get_embeddings(self, a: np.ndarray) -> np.ndarray: a = self._encode_nodes(a) return self.embeddings_[a] def similarity(self, a: np.ndarray, b: np.ndarray) -> np.ndarray: """Compute similarities between nodes. Args: a (np.ndarray): lhs nodes. b (np.ndarray): rhs nodes. Returns: np.ndarray: similarities. """ a_emb = self.get_embeddings(a) b_emb = self.get_embeddings(b) return np.sum(a_emb * b_emb, axis=-1) def most_similar(self, x, size=10) -> List[Tuple[Any, float]]: x_org = x x = self._encode_nodes([x])[0] scores = self.embeddings_ @ self.embeddings_[x] index = np.argsort(scores)[::-1][:size] similar_scores = scores[index] similar_nodes = self._inverse_nodes(index) return [(n, s) for n, s in zip(similar_nodes, similar_scores) if n != x_org] def _pre_factorization(self, matrix0): # Network Embedding as Sparse Matrix Factorization C1 = preprocessing.normalize(matrix0, "l1") neg = np.array(C1.sum(axis=0))[0] ** self.alpha # Convert matrix to an array. neg = neg / neg.sum() neg = scipy.sparse.diags(neg, format="csr") neg = matrix0.dot(neg) C1.data[C1.data <= 0] = 1 neg.data[neg.data <= 0] = 1 C1.data = np.log(C1.data) neg.data = np.log(neg.data) C1 -= neg F = C1 features_matrix = self._get_embedding_rand(F) return features_matrix def _get_embedding_rand(self, matrix): # Sparse randomized tSVD for fast embedding smat = scipy.sparse.csc_matrix(matrix) # convert to sparse CSC format U, Sigma, _ = randomized_svd( smat, n_components=self.dim, n_iter=5, random_state=self.random_state ) U = U * np.sqrt(Sigma) U = preprocessing.normalize(U, "l2") return U def _chebyshev_gaussian(self, A, a): # NE Enhancement via Spectral Propagation if self.step == 1: return a if self.verbose: print("[ProNE] Step 1") A = scipy.sparse.eye(self.node_number_) + A DA = preprocessing.normalize(A, norm="l1") L = scipy.sparse.eye(self.node_number_) - DA M = L - self.mu * scipy.sparse.eye(self.node_number_) Lx0 = a Lx1 = M.dot(a) Lx1 = 0.5 * M.dot(Lx1) - a conv = scipy.special.iv(0, self.theta) * Lx0 conv -= 2 * scipy.special.iv(1, self.theta) * Lx1 for i in range(2, self.step): if self.verbose: print(f"[ProNE] Step {i}") Lx2 = M.dot(Lx1) Lx2 = (M.dot(Lx2) - 2 * Lx1) - Lx0 # Lx2 = 2*L.dot(Lx1) - Lx0 if i % 2 == 0: conv += 2 * scipy.special.iv(i, self.theta) * Lx2 else: conv -= 2 * scipy.special.iv(i, self.theta) * Lx2 Lx0 = Lx1 Lx1 = Lx2 del Lx2 mm = A.dot(a - conv) emb = self._get_embedding_dense(mm) return emb def _get_embedding_dense(self, matrix): # get dense embedding via SVD U, s, _ = scipy.linalg.svd( matrix, full_matrices=False, check_finite=False, overwrite_a=True ) U = np.array(U) U = U[:, : self.dim] s = s[: self.dim] s = np.sqrt(s) U = U * s U = preprocessing.normalize(U, "l2") return U ```

[agatan]

[WIP] Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank

• https://arxiv.org/abs/1906.06826
• PVLDB 2020

速くて安くて directed グラフにも強くて Link Prediction にも強い Homogeneous Network Embedding 手法を提案している論文。 Approximate Personalized PageRank を使い、高速に良い Embedding を作っている。 forward/backward の 2 embeddings を各ノードに割り当てられるので、有向グラフに強く Link Prediction のようなタスクにも強いという性質を持つ（上に紹介した ProNE はこの性質を持たないため、Node Classification には強かったが Link Prediction の性能はいまいちだった）