PNNU: Parallel Nearest-Neighbor Units for Learned Dictionaries

详细信息    查看全文

• 关键词：Nearest neighbor ; NNU ; PNNU ; Data analytics ; Sparse coding ; Learned dictionary ; Parallel processing ; Multi ; core programming ; Speedup ; Matching pursuit ; Signal processing ; Computer vision ; KTH ; CIFAR
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9519
• 期：1
• 页码：223-237
• 全文大小：726 KB
• 参考文献：1.Aharon, M., Elad, M., Bruckstein, A.: K-SVD: an algorithm for designing overcomplete dictionaries for sparse representation. IEEE Trans. Sig. Process. 54(11), 4311–4322 (2006)CrossRef
  2.Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1), 33–61 (1998)CrossRef MathSciNet
  3.Datar, M., Immorlica, N., Indyk, P., Mirrokni, V.S.: Locality-sensitive hashing scheme based on p-stable distributions. In: Proceedings of the Twentieth Annual Symposium on Computational Geometry, pp. 253–262. ACM (2004)
  4.Efron, B., Hastie, T., Johnstone, I., Tibshirani, R., et al.: Least angle regression. Ann. Stat. 32(2), 407–499 (2004)CrossRef MathSciNet MATH
  5.Gkioulekas, I.A., Zickler, T.: Dimensionality reduction using the sparse linear model. In: Advances in Neural Information Processing Systems, pp. 271–279 (2011)
  6.Indyk, P.: Nearest neighbors in high-dimensional spaces (2004)
  7.Jolliffe, I.: Principal component analysis. Wiley Online Library (2002)
  8.Krizhevsky, A., Hinton, G.: Learning multiple layers of features from tiny images. Technical report, Computer Science Department, University of Toronto (2009)
  9.Krizhevsky, A., Sutskever, I., Hinton, G.E.: Imagenet classification with deep convolutional neural networks. In: Advances in Neural Information Processing Systems, pp. 1097–1105 (2012)
  10.Kung, H., McDanel, B., Teerapittayanon, S.: NNU Source Repository. https://​gitlab.​com/​steerapi/​nnu
  11.Mallat, S.G., Zhang, Z.: Matching pursuits with time-frequency dictionaries. IEEE Trans. Signal Process. 41(12), 3397–3415 (1993)CrossRef MATH
  12.Mathieu, M., Henaff, M., LeCun, Y.: Fast training of convolutional networks through ffts. arXiv preprint arxiv:​1312.​5851 (2013)
  13.Peterson, L.E.: K-nearest neighbor. Scholarpedia 4(2), 1883 (2009)CrossRef
  14.Rifai, S., Muller, X., Glorot, X., Mesnil, G., Bengio, Y., Vincent, P.: Learning invariant features through local space contraction. arXiv preprint arxiv:​1104.​4153 (2011)
  15.Roberts, L.: Picture coding using pseudo-random noise. IRE Trans. Inf. Theory 8(2), 145–154 (1962)CrossRef
  16.Saha, S.: Image compression-from DCT to wavelets: a review. Crossroads 6(3), 12–21 (2000)CrossRef
  17.Schuldt, C., Laptev, I., Caputo, B.: Recognizing human actions: a local svm approach. In: Proceedings of the 17th International Conference on Pattern Recognition, vol. 3, pp. 32–36 (2004)
  18.Shakhnarovich, G., Indyk, P., Darrell, T.: Nearest-Neighbor Methods in Learning and Vision: Theory and Practice. MIT Press, Cambridge (2006)
  19.Tropp, J.A., Gilbert, A.C.: Signal recovery from random measurements via orthogonal matching pursuit. IEEE Trans. Inf. Theory 53(12), 4655–4666 (2007)CrossRef MathSciNet MATH
  20.Wang, H., Klaser, A., Schmid, C., Liu, C.L.: Action recognition by dense trajectories. In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 3169–3176 (2011)
  21.Wess, S., Althoff, K.-D., Derwand, G.: Using k-d trees to improve the retrieval step. In: Wess, S., Richter, M., Althoff, K.-D. (eds.) EWCBR 1993. LNCS, vol. 837, pp. 167–181. Springer, Heidelberg (1994)CrossRef
  
• 作者单位：H. T. Kung (16)
  Bradley McDanel (16)
  Surat Teerapittayanon (16)
  
  16. Harvard University, Cambridge, MA, 02138, USA
  
• 丛书名：Languages and Compilers for Parallel Computing
• ISBN：978-3-319-29778-1
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

We present a novel parallel approach, parallel nearest neighbor unit (PNNU), for finding the nearest member in a learned dictionary of high-dimensional features. This is a computation fundamental to machine learning and data analytics algorithms such as sparse coding for feature extraction. PNNU achieves high performance by using three techniques: (1) PNNU employs a novel fast table look up scheme to identify a small number of atoms as candidates from which the nearest neighbor of a query data vector can be found; (2) PNNU reduces computation cost by working with candidate atoms of reduced dimensionality; and (3) PNNU performs computations in parallel over multiple cores with low inter-core communication overheads. Based on efficient computation via techniques (1) and (2), technique (3) attains further speed up via parallel processing. We have implemented PNNU on multi-core machines. We demonstrate its superior performance on three application tasks in signal processing and computer vision. For an action recognition task, PNNU achieves 41x overall performance gains on a 16-core compute server against a conventional serial implementation of nearest neighbor computation. Our PNNU software is available online as open source.