Deeplearning Algorithms tutorial

谷歌的人工智能位于全球前列，在图像识别、语音识别、无人驾驶等技术上都已经落地。而百度实质意义上扛起了国内的人工智能的大旗，覆盖无人驾驶、智能助手、图像识别等许多层面。苹果业已开始全面拥抱机器学习，新产品进军家庭智能音箱并打造工作站级别Mac。另外，腾讯的深度学习平台Mariana已支持了微信语音识别的语音输入法、语音开放平台、长按语音消息转文本等产品，在微信图像识别中开始应用。全球前十大科技公司全部发力人工智能理论研究和应用的实现，虽然入门艰难，但是一旦入门，高手也就在你的不远处！ AI的开发离不开算法那我们就接下来开始学习算法吧！

局部线性嵌入(Locally Linear Embedding)

数据降维是指通过线性的或非线性的映射关系将高维数据转换成低维数据的过程。一般情况下，该低维数据代表了原始高维数据的主要成分（图1），并描述了原始高维数据的空间分布结构。由于经过降维后的数据更易于被分类、识别、可视化以及存储等，故数据降维技术在诸多科研领域受到了越来越多地关注。

从数据本身的的性质特征来看，数据降维可以大致分为线性降维和非线性降维两种技术方法。其中，线性降维技术仅对于数据维数相对较低、且具有全局线性结构的数据有着很好的降维效果。然而，在实际的科学研究中，科研工作者却需要面对海量的非线性高维数据。因此，能够有效处理高维非线性数据的方法亟待被提出，本文将介绍一种用于处理高维非线性数据的降维方法。

局部线性嵌入（Locally linear embedding, LLE）是一种非线性的降维方法，该算法由 Sam T.Roweis等人于2000年提出并发表在《Science》杂志上。LLE试图保留原始高维数据的局部性质，通过假设局部原始数据近似位于一张超平面上，从而使得该局部的某一个数据可以由其邻域数据线性表示。

Sam T.Roweis 和 Lawrence K.Saul提出局部线性嵌入（Locally linear embedding, LLE）算法，它是针对非线性数据的一种新的降维技术，并且能够使降维后的数据保持原有的拓扑结构。 LLE算法可以广泛的应用于非线性数据的降维、聚类以及图像分割等领域。

局部线性嵌入(Locally linear embedding, LLE)是最新提出的非线性降维方法。该算法即具有处理非线性数据的优点又有线性降维方法计算性能的优越性。 简单的讲，该方法是将高维流型用剪刀剪成很多的小块，每一小块可以用平面代替，然后再低维中重新拼合出来， 且要求保留各点之间的拓扑关系不变。整个问题最后被转化为两个二次规划问题。

局部线性嵌入(Locally linear embedding, LLE)算法可以归结为三步:

  1. 寻找每个样本点的k个近邻点；
  2. 由每个样本点的近邻点计算出该样本点的局部重建权值矩阵；
  3. 由该样本点的局部重建权值矩阵和其近邻点计算出该样本点的输出值。

局部线性嵌入算法的第一步是计算出每个样本点的k个近邻点。把相对于所求样本点距离最近的k个样本点规定为所求样本点的k个近邻点。k是一个预先给定值。Sam T.Roweis 和 Lawrence K.Saul算法采用的是欧氏距离，则减轻复杂的计算。然而本文是假定高维空间中的数据是非线性分布的，采用了diijstra距离。Dijkstra 距离是一种测地距离，它能够保持样本点之间的曲面特性，在ISOMAP算法中有广泛的应用。针对样本点多的情况，普通的dijkstra算法不能满足LLE算法的要求。

应用示例：

  2. import numpy
  3. import sources
  5. from sklearn import manifold
  6. from sklearn.utils.extmath import randomized_svd
  7. from sklearn.neighbors import NearestNeighbors
  10. from wordreps import WordReps
  11. from scipy.sparse import csr_matrix, eye
  12. from scipy.sparse.linalg import eigsh
  13. from scipy.sparse.linalg.eigen.arpack.arpack import ArpackNoConvergence
  15. from scipy.io import savemat, loadmat
  17. import sys
  18. import time
  19. import argparse
  20. import collections
  23. class MetaEmbed():
  25.     def __init__(self, wordreps, words):
  26.         self.words = words
  27.         self.ids = {}
  28.         for (i,word) in enumerate(words):
  29.             self.ids[word] = i
  31.         self.reps = wordreps
  32.         self.dims = [x.dim for x in self.reps]
  33.         self.embeds = []
  34.         N = len(words)
  36.         # Create the source embedding matrices
  37.         write("Creating source embedding matrices...")
  38.         for i in range(len(self.reps)):
  39.             M = numpy.zeros((self.reps[i].dim, N), dtype=numpy.float64)
  40.             for j in range(N):
  41.                 M[:,j] = self.reps[i].vects[self.words[j]]
  42.             self.embeds.append(M)
  43.         write("done\n")
  44.         pass
  46.     def compute_neighbours(self, nns):
  47.         """
  48.         Compute the nearest neighbours for each embedding.
  49.         """
  50.         self.NNS = []
  51.         for i in range(len(self.embeds)):
  52.             start_time = time.clock()
  53.             write("Computing nearest neighbours for embedding no = %d ..." % i)
  54.             nbrs = NearestNeighbors(n_neighbors=nns, algorithm='ball_tree').fit(self.embeds[i].T)
  55.             distances, indices = nbrs.kneighbors(self.embeds[i].T)
  56.             self.NNS.append(indices[:,1:])
  57.             end_time = time.clock()
  58.             write("Done (%s sec.)\n" % str(end_time - start_time))
  59.         pass
  61.     def show_nns(self, word ,nns):
  62.         """
  63.         Print nearest neigbours for a word in different embeddings.
  64.         """
  65.         for i in range(len(self.embeds)):
  66.             print "Showing nearest neighbours for = %s" % word
  67.             print "\nEmbedding no = %d" % i
  68.             for s in self.NNS[i][self.ids[word], :][:nns]:
  69.                 print self.words[s]
  70.         pass
  72.     def compute_weights(self):
  73.         """
  74.         Computes the reconstruction weights.
  75.         """
  76.         start_time = time.clock()
  77.         T = 10  # no. of iterations.
  78.         alpha = 0.01  # learning rate.
  79.         N = len(self.words)
  80.         self.W = numpy.zeros((N, N), dtype=numpy.float64)
  82.         # initialise the weights.
  83.         for i in range(N):
  84.             nns = set()
  85.             for j in range(len(self.embeds)):
  86.                 for x in self.NNS[j][i,:]:
  87.                     nns.add(x)
  88.             val = 1.0 / float(len(nns))
  89.             for j in nns:
  90.                 self.W[i,j] = val
  92.         # iterate
  93.         for i in range(N):
  94.             write("\x1b[2K\rLearning weights for (%d of %d) = %s" % (i, N, self.words[i]))
  95.             for t in range(T):                       
  96.                 d = [self.embeds[j][:,i] - numpy.sum([self.W[i,k] * self.embeds[j][:,k] for k in self.NNS[j][i,:]], axis=0) for j in range(len(self.embeds))]
  97.                 #for j in range(len(self.embeds)):
  98.                 #    d.append(self.embeds[j][:,i] - numpy.sum([self.W[i,k] * self.embeds[j][:,k] for k in self.NNS[j][i,:]], axis=0))
  100.                 grad = numpy.zeros(N, dtype=numpy.float64)
  101.                 for j in range(len(self.embeds)):
  102.                     for k in self.NNS[j][i,:]:
  103.                         grad[k] += -2.0 * numpy.dot(d[j], self.embeds[j][:,k])
  105.                 self.W[i,:] -= (alpha * grad)
  107.             total = numpy.sum(self.W[i,:])
  108.             if total != 0:
  109.                 self.W[i,:] = self.W[i,:] / total
  110.         write("\n")
  111.         end_time = time.clock()
  112.         write("Done (took %s seconds)\n" % str(end_time - start_time))
  113.         pass
  115.     def save_weights(self, fname):
  116.         """
  117.         Save the weight matrix to a disk file.
  118.         """
  119.         savemat(fname, {"W":self.W})
  120.         pass
  122.     def load_weights(self, fname):
  123.         """
  124.         Load the weight matrix from a disk file.
  125.         """
  126.         self.W = loadmat(fname)["W"]
  127.         pass
  129.     def test_compute_weights(self):
  130.         """
  131.         Check whether the weights are computed correctly
  132.         """
  133.         N = len(self.words)
  134.         # Check whether non-neighbours have weights equal to zero.
  135.         write("Checking whether non-neighbours have zero weights...\n")
  136.         for i in range(N):
  137.             pred_nns = set(numpy.where(self.W[i,:] != 0)[0])
  138.             nns = set()
  139.             for j in range(len(self.embeds)):
  140.                 nns = nns.union(set(self.NNS[j][i,:]))
  141.             assert(pred_nns == nns)
  143.         # Check whether reconstruction weights add upto one.
  144.         write("Checking whether weights add to 1...\n")
  145.         for i in range(N):
  146.             assert(numpy.allclose(numpy.sum(self.W[i,:]), 1)) 
  148.         # print nearest neighbours and their weights
  149.         nn_file = open("../work/nn.csv", 'w')
  150.         for i in range(N):
  151.             nn_file.write("%s, " % self.words[i])
  152.             L = []
  153.             for j in range(N):
  154.                 if self.W[i,j] != 0:
  155.                     L.append((self.words[j], self.W[i,j]))
  156.             L.sort(lambda x, y: -1 if x[1] > y[1] else 1)
  157.             for (w, val) in L:
  158.                 nn_file.write("%s, %f, " % (w, val))
  159.             nn_file.write("\n")
  160.         nn_file.close()
  161.         pass
  163.     def compute_M(self):
  164.         """
  165.         Compute the smallest eigenvectors of M = (I - W')\T(I - W').
  166.         """
  167.         # Building W'
  168.         N = len(self.words)
  169.         start_time = time.clock()
  170.         write("Computing W'...")
  171.         for i in range(N):
  172.             z = numpy.zeros(N)
  173.             write("Completed %d of %d\r" % (i, N))
  174.             for nns in self.NNS:
  175.                 z[nns[i,:]] += 1
  176.             self.W[i,:] = z * self.W[i,:]
  177.         end_time = time.clock()
  178.         write("Done (took %s seconds)\n" % str(end_time - start_time))
  180.         # Computing M.
  181.         start_time = time.clock()
  182.         write("Computing M....")
  183.         self.W = csr_matrix(self.W)
  184.         M = eye(N, format=self.W.format) - self.W
  185.         M = (M.T * M).tocsr()
  186.         end_time = time.clock()
  187.         write("Done (took %s seconds)\n" % str(end_time - start_time))
  188.         return M
  190.     def compute_embeddings(self, k, M, embed_fname):
  191.         """
  192.         Perform eigen decomposition.
  193.         """
  194.         N = len(self.words)
  195.         start_time = time.clock()
  196.         write("Computing Eigen decomposition...")
  197.         s, V =  eigsh(M, k+1, tol=1E-6, which="SA", maxiter=100)
  198.         end_time = time.clock()
  199.         write("Done (took %s seconds)\n" % str(end_time - start_time))
  200.         P = V[:, 1:]
  201.         err = numpy.sum(s[1:])
  202.         write("Projection error = %f\n" % err)
  204.         write("Writing embeddings to file...")
  205.         # Write embeddings to file.
  206.         with open(embed_fname, 'w') as embed_file:
  207.             for i in range(N):
  208.                 embed_file.write("%s %s\n" % (self.words[i], " ".join([str(x) for x in P[i,:]])))
  209.         write("Done\n")
  210.         pass
  213. def write(msg):
  214.     sys.stdout.write(msg)
  215.     sys.stdout.flush()
  216.     pass
  219. def meta_embed(embeddings, words, nns, comps, embed_path):
  220.     """
  221.     Perform meta-embedding using LLE.
  222.     """
  223.     ME = MetaEmbed(embeddings, words)
  224.     ME.compute_neighbours(nns)
  225.     #ME.show_nns("king", 5)
  227.     #ME.compute_weights_parallel()
  228.     ME.compute_weights()
  230.     #ME.save_weights("../work/weights_%d" % nns)
  231.     #ME.load_weights("../work/weights+n=%d.meta" % nns)
  232.     #ME.test_compute_weights()
  233.     M = ME.compute_M()
  234.     for k in comps:
  235.         embed_fname = "%s/n=%d+k=%d" % (embed_path, nns, k)
  236.         write("Embedding NNS = %d, Components (k) = %d\n" % (nns, k))
  237.         try:
  238.             ME.compute_embeddings(k, M, embed_fname)
  239.         except ArpackNoConvergence as e:
  240.             print e
  241.     return ME
  244. def baseline_concatenate(embeddings, words, embed_fname):
  245.     """
  246.     Concatenate embeddings to create co-embeddings.
  247.     """
  248.     dim = sum([x.dim for x in embeddings])
  250.     print "Concatenation dimension =", dim
  251.     # concatenate the vectors.
  252.     with open(embed_fname, 'w') as embed_file:
  253.         for (i,word) in enumerate(words):
  254.             L = []
  255.             for x in embeddings:
  256.                 w = 8 if x.dim == 300 else 1
  257.                 #w = 1
  258.                 L.append(w * x.vects[word])
  260.             z = numpy.concatenate(L)            
  261.             embed_file.write("%s %s\n" % (word, " ".join([str(x) for x in z])))
  262.     pass
  264. def get_common_words(embeddings):
  265.     words = set(embeddings[0].vocab)
  266.     for i in range(1, len(embeddings)):
  267.         words = words.intersection(set(embeddings[i].vocab))
  268.     return words
  271. def get_selected_words(fname):
  272.     words = []
  273.     with open(fname) as F:
  274.         for line in F:
  275.             words.append(line.strip())
  276.     return words
  278. def perform_embedding(nns, comps):
  279.     print "Neigbourhood size = %d" % nns
  281.     #embed_sett
  282.     embed_settings = sources.embed_settings
  283.     embeddings = []
  284.     for (embd_fname, dim) in embed_settings:
  285.         start_time = time.clock()
  286.         sys.stdout.write("Loading %s -- (%d dim) ..." % (embd_fname, dim))
  287.         sys.stdout.flush()        
  288.         WR = WordReps()
  289.         WR.read_model(embd_fname, dim)
  290.         end_time = time.clock()
  291.         sys.stdout.write("\nDone. took %s seconds\n" % str(end_time - start_time))
  292.         sys.stdout.flush()
  293.         embeddings.append(WR)
  295.     common_words = get_common_words(embeddings)
  296.     selected_words = get_selected_words("../work/selected-words")
  297.     words = []
  298.     for word in selected_words:
  299.         if word in common_words and word not in words:
  300.             words.append(word)
  301.     print "No. of common words =", len(common_words)
  302.     print "Vocabulary size =", len(words)
  303.     ME = meta_embed(embeddings, words, nns, comps, "../work/meta-embeds")
  304.     pass
  306. def save_embedding(words, WR, fname):
  307.     F = open(fname, 'w')
  308.     for w in words:
  309.         if w in WR.vects:
  310.             F.write("%s " % w)
  311.             F.write("%s\n" % " ".join([str(x) for x in WR.vects[w]]))
  312.         # elif w.lower() in WR.vects:
  313.         #     F.write("%s " % w.lower())
  314.         #     F.write("%s\n" % " ".join([str(x) for x in WR.vects[w.lower()]]))
  315.     F.close()
  316.     pass
  318. def main():
  319.     parser = argparse.ArgumentParser()
  320.     parser.add_argument("-nns", type=int, help="number of nearest neighbours")
  321.     parser.add_argument("-comps", type=str, help="components for the projection")
  322.     args = parser.parse_args()
  323.     comps = [int(x) for x in args.comps.split(',')]
  324.     perform_embedding(args.nns, comps)
  325.     pass
  327. if __name__ == '__main__':
  328.     main()
  329.     pass