SVD及常见的Embedding应用详解

作者: 笑傲NLP江湖 | 来源:发表于2021-09-16 10:20 被阅读0次

写这篇文章的原因是因为在一个推荐任务中使用SVD,deepwalk进行embedding之后，模型效果得到了提升，并且SVD的应用超出了进行降维的认知，感觉其中值得思考的东西很多，所以对SVD和embedding的一些方法进行整理总结。

1.奇异值分解SVD(Singular Value Decomposition)

1.1 SVD降维

SVD是对矩阵进行分解,假设A是一个 $m\times n$ 的矩阵，则 $X$ 的SVD为:
$X = U\sum V^T\$

其中 $U$ 是一个𝑚×𝑚的矩阵， $\sum$ 是一个𝑚×𝑛的矩阵，除了主对角线上的元素以外全为0，主对角线上的每个元素都称为奇异值，V是一个𝑛×𝑛的矩阵。 $U$ 和 $V$ 都是酉矩阵，即满足: $𝑈^T𝑈=𝐼,𝑉 ^ T𝑉=𝐼 \$

在奇异矩阵中( $\sum$ )奇异值(对角线元素)是按照从大到小排列的，并且奇异值的减少特别快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和99%以上的比例，所以可以认为前10%甚至1%的奇异值包含了全部的奇异值99%的信息。那么，则可以用最大的k个奇异值和对应的左右奇异向量来近似描述矩阵，即：
$X_{m\times\ n} = U_{m\times m} \sum_{m\times n}V_{n\times n}^T\approx U_{m\times k}\sum_{k\times k}V_{k\times n}^T \$

其中k要比n小很多，也就是一个大的矩阵A可以用三个小的矩阵 $U_{m\times k} ,\sum_{k\times k},V_{k\times n}^T$ 来表示，因此，SVD可以用来降维，用于处理数据压缩和去燥。

1.2 基于SVD的word embedding

奇异值分解的做法是，首先遍历数据集，通过矩阵 $X$ 存储单词出现的共现次数(共现矩阵)，然后对X进行奇异值分解。可以将 $U$ 的行值可以作为词表中所有词的word embedding。

举个例子，数据集中有三句话，窗口大小为1:

1. I enjoy flying.
2. I like NLP.
3. I like deep learning.

可以得到共现矩阵为：

使用SVD得到， $X=U∑V^T$ ,选择U的前k个维度，得到k维的词向量。这种方法虽然存在着不足，但也通过上下文分布来表示一个词，而不再是孤立的''独热''。共现矩阵也可以替换成tf-idf矩阵，再使用SVD进行降维。

虽然得到了词向量，但是通过矩阵分解得到词向量的解释并不是很好理解，所以再深一步进行探索，首先看一下Word2vec的结构图：

在不考虑激活函数的情况下，这是一个V维输入，中间节点是N个，V维输出的三层神经网络。用公式表达为： $Y=XWW^T$ ，这个公式和SVD的公式太像了，确切的说应该是和skip-gram像，skip-gram的输入可以看成多个one-hot的和作为输入，和SVD中共现矩阵中的每一行结构基本相同。所以可以简单的认为两者结构相同，只不过Word2Vec，可以看作是通过前后词来预测当前词，而自编码器或者SVD则是通过前后词来预测前后词；并且Word2Vec最后接的是softmax来预测概率，也就是说实现了一个非线性变换，而SVD并没有。

当然，SVD和word2vec相比，除了没有经过非线形变换外，还存在着其他不足：

（1）添加新词之后，预料库的大小发生变化(word2vec中可以用unk或者增量训练解决这个问题)。

（2）矩阵过于稀疏，大部分的单词不会同时出现。

（3）矩阵维度高( $\approx10^6\times10^6$ )，训练成本大( $O(mn^2)$ )

1.3 推荐系统中的SVD

推荐系统中的SVD，我们比较熟悉就是电影评分的案例。矩阵中的分数代表用户对电影的喜爱程度，其中大部分数据处于缺失状态。

这是一个稀疏矩阵，这里把这个评分矩阵记为X，其中的元素表示user对item的打分，其中有很多缺失的，也是需要预测的，最终把预测评分最高的前K个电影推荐给用户。首先SVD的公式可以由 $X = U\sum V^T$ 简化一下，令 $Z = U\sum,Y=V^T$ ,所以对于评分矩阵X可以用两个矩阵Z和Y的乘积表示：

$X_{m\times\ n} = Z_{m\times k} Y_{k\times n} \$

其中的m表示user的数量，n表示item的数量，可以看到评分矩阵已经分解成了两个矩阵，形象一点的表示：

评分矩阵是已知的，在分解成两个矩阵之后得到的是每个用户对于每种类型电影的评分(类型是为了好解释构造出来的，实际是将电影之间的潜在特征)，和每种类型下每个电影的评分。

某个用户u对电影i的预测评分等于User向量和Item向量的内积，因此可以得到每个用户对每部电影的预测评分了，但是这种评分一定是可靠的吗？这一点可以根据最开始的评分表中的已知数据和预测结果做比较，如果差别比较大，这种分解方法是否就没有用？其实这里已经有了深度学习的味道，有了预测值和真实值，则可以利用不断优化的方法进行更新user和item里面的数据，使得预测结果和真实结果接近。这里的损失函数可以是RMSE，MAE等。最终的评分表中评分值越大，表示用户喜欢该电影的可能性越大，该电影就越值得推荐给用户。

从效果上看，SVD是将评分矩阵电影类型进行了聚类。对于user矩阵可以看成对用户进行了user进行了聚类，item矩阵可以看成是对每个电影进行了聚类。矩阵的乘法，可以看成用户和电影的匹配。

1.4 基于SVD的embedding

上面已经讲了SVD的三种作用了，而我在推荐任务中用到的SVD的作用可以看作是聚类。在推荐任务中，有userid(用户id) 、feedid(视频id)等，就用这两个举例说明，而我们的目的是挖掘用户和不同视频之间的潜在关系。做法也比较简单，首先构建两个特征的共现矩阵

import datatable as dt
from tqdm import tqdm
from scipy.sparse import lil_matrix, csr_matrix

def build_inter_matrix(path, row_item, col_item, row_vocab, col_vocab):
    total_df = dt.fread(path).to_pandas()
    matrix = lil_matrix((len(row_vocab), len(col_vocab)), dtype=np.float32)
    for _, row in tqdm(total_df.iterrows(), total=len(total_df), desc=f'Building {row_item}-{col_item} matrix'):
        row_val = row[row_item]
        if col_item == 'feedid':
            col_val = row[col_item]
        else:
            col_val = feed_dict[row['feedid']][col_item]
        matrix[row_vocab[row_val], col_vocab[col_val]] += 1.0
    return matrix.tocsr()

其中path是数据集路径，在例子中row_item='userid'，col_item = 'feedid', row_vocab 是userid 中的token对应的每个id(比如用户A对用的id是1，用户B对应的id是2),col_vocab是feedid中的token对应的每个id(比如:视频x1对应的id是1，视频x2对应的id是2),为了节约内存，共现矩阵保存在稀疏矩阵中。将共现矩阵分解成两个矩阵即可以得到userid对应的向量和feedid对应的向量，userid中的一个向量可以看成一个用户和不同视频的映射关系(比如喜欢程度)，feedid中的一个向量可以看成一个视频和不同户用之间的映射关系，这种映射关系可以当作变量来输入模型中，同时也可以解决冷启动问题。

from functools import partia
#为了加快速度，利用了多进程，
func = partial(build_inter_matrix, row_item='userid', col_item='feedid', 
               row_vocab=user_token2id, col_vocab=feed_token2id)
uid_fid_sparse = parallelize(user_df, func)
u_SVD_vector, f_SVD_vector = SVD(uid_fid_sparse, dim=64)

from multiprocessing import cpu_count, Pool, Manage
def parallelize(df, func):
    part = 10 #cpu_count() // 2
    data_split = np.array_split(df, part)
    
    if not os.path.exists(os.path.join(TRAIN_TEST_DATA_PATH, 'user_act_part0.csv')):
        data_path = []
        for i, part_data in tqdm(enumerate(data_split), desc='split data'):
            part_path = os.path.join(TRAIN_TEST_DATA_PATH, f'user_act_part{i}.csv')
            part_data.to_csv(part_path, index=False, encoding='utf8')
            data_path.append(part_path)
    else:
        data_path = [os.path.join(TRAIN_TEST_DATA_PATH, path) for path in os.listdir(TRAIN_TEST_DATA_PATH) if 'user_act' in path]

    pool = Pool(part)
    data = sum(pool.map(func, data_path))
    pool.close()
    pool.join()
    return data

2.TFIDF-SVD

这一部分内用源自于微信大数据竞赛Trick--如何3ID上0.706+,在这里整理出来只是为了和上面的方法进行比较区分。还是用userid和feedid举例，目的是希望找到基于视频的用户共现性，如果某些视频某些用户总是一起出现，那么就说明这些用户大概率有相同的爱好，就很可能一起转发，一起评论并且同时关注了。可以通过TFIDF得到：

userid,feedid的两个向量；
  groupby(userid)[feedid).agg(list);
  groupby(feedid)[userid).agg(list);

这里是根据userid分组，然后将feedid放到一起，即构建了每个用户的视频向量特征。如果不好理解，可以想象成userid是文章，feedid是文字，然后使用tfidf得到向量。

from sklearn.feature_extraction.text import TfidfVectorizer, CountVectorizer 
from sklearn.decomposition import TruncatedSVD

def tfidf_SVD(data, f1, f2, n_components=100):
    n_components = 100 
    tmp     = data.groupby(f1, as_index=False)[f2].agg({'list': lambda x: ' '.join(list(x.astype('str')))})
    tfidf   = TfidfVectorizer(max_df=0.95, min_df=3, sublinear_tf=True)
    res     = tfidf.fit_transform(tmp['list']) 
    print('SVD start')
    SVD     = TruncatedSVD(n_components=n_components, random_state=2021)
    SVD_res = SVD.fit_transform(res)
    print('SVD finished')
    for i in (range(n_components)):
        tmp['{}_{}_tfidf_SVD_{}'.format(f1, f2, i)] = SVD_res[:, i]
        tmp['{}_{}_tfidf_SVD_{}'.format(f1, f2, i)] = tmp['{}_{}_tfidf_SVD_{}'.format(f1, f2, i)].astype(np.float32)
    del tmp['list']
    return tmp

def get_first_SVD_features(f1_, n_components = 100):  
    # userid_id_dic : 用户的mapping字典；
    # first_cls_dic[f1_] : f1的mapping字典； 
    f1_embedding_userid = pd.DataFrame({f1_:list(first_cls_dic[f1_].values())})
    f1_embedding_userid_tmp = tfidf_SVD(df_train_val[[f1_, 'userid']], f1_, 'userid', n_components)  
    f1_embedding_userid = f1_embedding_userid.merge(f1_embedding_userid_tmp, on = f1_, how = 'left')
    f1_embedding_userid = f1_embedding_userid.fillna(0)
    f1_embedding_userid = f1_embedding_userid[[c for c in f1_embedding_userid.columns if c not in [f1_]]].values
    np.save(embedding_path + '{}_embedding_userid.npy'.format(f1_),f1_embedding_userid)
    del f1_embedding_userid,f1_embedding_userid_tmp
    gc.collect()
    userid_embedding_f1 = pd.DataFrame({'userid':list(userid_id_dic.values())})
    userid_embedding_f1_tmp = tfidf_SVD(df_train_val[['userid', f1_]], 'userid', f1_, n_components)  
    userid_embedding_f1 = userid_embedding_f1.merge(userid_embedding_f1_tmp, on = 'userid', how = 'left')
    userid_embedding_f1 = userid_embedding_f1.fillna(0)
    userid_embedding_f1 = userid_embedding_f1[[c for c in userid_embedding_f1.columns if c not in ['userid']]].values
    np.save(embedding_path + 'userid_embedding_{}.npy'.format(f1_),userid_embedding_f1)
    del userid_embedding_f1,userid_embedding_f1_tmp
    gc.collect()

get_first_SVD_features('feedid')
get_first_SVD_features('authorid')

TFIDF-SVD进行embedding和SVD进行embedding，从操作上看，这个只是用TFIDF构成的矩阵代替了共现矩阵，但是本质上存在着区别。

1）TFIDF-SVD方法是首先利用TFIDF操作得到用户向量特征，只不过维度太大，使用SVD的目的是为了降维，而SVD进行embedding的方法中，SVD可以看作是起到聚类的作用。

2）从结果上看TFIDF-SVD只是利用分解之后的第一个向量，即利用的是 $X = U\sum V^T$ 中的U向量作为特征向量，而SVD进行embedding的方法中，使用的是 $U$ 向量和 $V^T$ 作为特征向量的。

3.deepwalk

deepwalk（2014年）是采用随机游走的方法模拟任何两个变量之间的关系。它的主要思想是在由物品组成的图结构上进行随机游走，产生大量物品序列，然后将这些物品序列作为训练样本输入word2vec进行训练，得到物品的embedding。整个DeepWalk的算法流程可以分为四步：

1）展示了原始的用户行为序列

2）基于这些用户行为序列构建了物品相关图

def build_graph(df, graph, f1, f2):
    for item in df[[f1, f2]].values:
        if isinstance(item[1], str):
            if not item[1]: continue
            for token in item[1].split(';'):
                graph['item_' + token].add('user_' + str(item[0]))
                graph['user_' + str(item[0])].add('item_' + token)
        else:
            graph['item_' + str(item[1])].add('user_' + str(item[0]))
            graph['user_' + str(item[0])].add('item_' + str(item[1]))

3）采用随机游走的方式随机选择起始点，重新产生物品序列。

4）最终将这些物品序列输入word2vec模型，生成最终的物品Embedding向量。

def deepwalk(train_df, test_df, f1, f2, flag, emb_size):
    print("deepwalk:", f1, f2)
    print('Building graph ...')
    graph = defaultdict(set)
    build_graph(train_df, graph, f1, f2)
    build_graph(test_df, graph, f1, f2)
    # print('graph:',graph)
    print("Creating corpus ...")
    path_length = 10
    sentences = []
    length = []
    keys = graph.keys()
    for key in tqdm(keys, total=len(keys), desc='Walk'):
        sentence = [key]
        while len(sentence) != path_length:
            key = random.sample(graph[sentence[-1]], 1)[0]
            if len(sentence) >= 2 and key == sentence[-2]:
                break
            else:
                sentence.append(key)

        sentences.append(sentence)
        length.append(len(sentence))
        if len(sentences) % 100000 == 0:
            print(len(sentences))

    print(f'Mean sentences length: {np.mean(length)}')
    print(f'Total {len(sentences)} sentences ...')
    print('Training word2vec ...')
    random.shuffle(sentences)
    model = Word2Vec(sentences, vector_size=emb_size, window=4, min_count=1, sg=1, workers=10, epochs=20)
    print('Outputing ...')

    values = np.unique(np.concatenate([np.unique(train_df[f1]), np.unique(test_df[f1])], axis=0))

    w2v = {}
    for v in tqdm(values):
        if 'user_' + str(v) not in model.wv:
            vec = np.zeros(emb_size)
        else:
            vec = model.wv['user_' + str(v)]
        w2v[v] = vec
    pickle.dump(
        w2v,
        open('./data/wedata/deepwalk/' + f1 + '_' + f2 + '_' + f1 + '_' + flag + '_deepwalk_' + str(emb_size) + '.pkl',
             'wb')
    )

    if 'list' in f2:
        values = [items.split(';') for items in train_df[f2].values] + [items.split(';') for items in
                                                                        test_df[f2].values]
        values = set([token for v in values for token in v])
    else:
        values = np.unique(np.concatenate([np.unique(train_df[f2]), np.unique(test_df[f2])], axis=0))

    w2v = {}
    for v in tqdm(values):
        if 'item_' + str(v) not in model.wv:
            vec = np.zeros(emb_size)
        else:
            vec = model.wv['item_' + str(v)]
        w2v[v] = vec
    print(list(w2v.items())[:5])
    pickle.dump(
        w2v,
        open('./data/wedata/deepwalk/' + f1 + '_' + f2 + '_' + f2 + '_' + flag + '_deepwalk_' + str(emb_size) + '.pkl',
             'wb')
    )

deepwalk(train, test, 'userid', 'feedid', 'dev', 64)

因为是随机模拟一个user对于视频的表示，所以即使出现冷启动，这种embedding也能解决。

4.总结

本文总结了SVD的各种应用和TFIDF-SVD和DeepWalk在embedding上的应用。SVD的主要作用是降维、word embedding和聚类(在推荐系统的作用理解成聚类吧)。并且和TFIDF-SVD、DeepWalk一样，在userid和feedid的例子中，可以起到embedding的作用，这种作用不仅可以解决冷启动问题，还能很好的表示user和feed的之间的隐藏关系。不管是SVD的作用还是集中embedding方法，希望可以给大家一个参考。