Abstract
This article proposes to use a binary random matrix with the elements {0,1} to project input floating-point vectors onto output floating-point vectors of smaller dimension. The accuracies of estimates of the scalar product, Euclidean distance, and norm of input vectors are analyzed with respect to output vectors. It is analytically and experimentally shown that an error for the proposed random projection is smaller than that for a ternary random matrix.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
V. I. Gritsenko, D. A. Rachkovskij, A. D. Goltsev, V. V. Lukovych, I. S. Misuno, E. G. Revunova, S. V. Slipchenko, and A. M. Sokolov, “Neural distributed representation for intelligent information technologies and modeling of thinking,” Cybernetics and Computer Engineering, 173, 7–24 (2013).
D. A. Rachkovskij, “Representation and processing of structures with binary sparse distributed codes,” IEEE Trans. on Knowledge and Data Engineering, 13, No. 2, 261–276 (2001).
D. A. Rachkovskij, “Some approaches to analogical mapping with structure sensitive distributed representations,” J. Experimental and Theoretical Artificial Intelligence, 16, No. 3, 125–145 (2004).
S. V. Slipchenko and D. A. Rachkovskij, “Analogical mapping using similarity of binary distributed representations,” International J. Information Theories and Applications, 16, No. 3 269–290 (2009).
D. A. Rachkovskij and S. V. Slipchenko, “Similarity-based retrieval with structure-sensitive sparse binary distributed representations,” Computational Intelligence, 28, No. 1, 106–129 (2012).
C. J. C. Burges, “Dimension reduction: A guided tour,” Foundations and Trends in Machine Learning, 2, No. 4, 275–365 (2010).
P. Indyk and R. Motwani, “Approximate nearest neighbors: Towards removing the curse of dimensionality,” in: Proc. 30th ACM Symposium on Theory of Computing (1998), pp. 604–613.
S. S. Vempala, The Random Projection Method, American Mathematical Society, Providence, RI (2004).
D. Achlioptas, “Database-friendly random projections: Johnson–Lindenstrauss with binary coins,” J. Computer and System Sciences, 66, No. 4, 671–687 (2003).
P. Li, T. J. Hastie, and K. W. Church, “Very sparse random projections,” in: Proc. 12th ACM SIGKDD Intern. Conf. on Knowledge Discovery and Data Mining, ACM Press, Philadelphia, PA, USA (2006), pp. 287–296.
D. A. Rachkovskij, I. S. Misuno, and S. V. Slipchenko, “Randomized projective methods for construction of binary sparse upsilon vector representations,” Cybernetics and Systems Analysis, 48, No. 1, 140–150 (2012).
P. Li, “Very sparse stable random projections for dimension reduction in l α(0 < α ≤ 2) norm,” in: Proc. 13th ACM SIGKDD Intern. Conf. on Knowledge Discovery and Data Mining, ACM Press, San Jose, CA, USA (2007), pp. 440–449.
D. L. Donoho, “Compressed sensing,” IEEE Trans. Inform. Theory, 52, No. 4, 1289–1306 (2006).
D. A. Rachkovskij and E. G. Revunova, “Randomized method for solving discrete ill-posed problems,” Cybernetics and Systems Analysis, 48, No. 4, 621–635 (2012).
P. Kanerva, G. Sjodin, J. Kristoferson, R. Karlsson, B. Levin, A. Holst, J. Karlgren, and M. Sahlgren, “Computing with large random patterns,” in: Foundations of Real-World Intelligence, CSLI Publications, Stanford, California (2001), pp. 251–311.
I. S. Misuno, D. A. Rachkovskij, and S. V. Slipchenko, “Vector and distributed representations reflecting semantic relatedness of words,” Math. Machines and Systems, No. 3, 50–67 (2005).
A. Sokolov, “LIMSI: learning semantic similarity by selecting random word subsets,” in: Proc. 6th Intern. Workshop on Semantic Evaluation (SEMEVAL’12), Association for Computational Linguistics (2012), pp. 543–546.
A. Sokolov and S. Riezler, “Task-driven greedy learning of feature hashing functions,” in: Proc. NIPS of 13 Workshop “Big Learning: Advances in Algorithms and Data Management,” Lake Tahoe, USA (2013), pp. 1–5.
A. Frolov, A. Kartashov, A. Goltsev, and R. Folk, “Quality and efficiency of retrieval for Willshaw-like autoassociative networks. I. Correction,” Network: Computation in Neural Systems, 6, No. 4, 513–534 (1995).
A. Frolov, A. Kartashov, A. Goltsev, and R. Folk, “Quality and efficiency of retrieval for Willshaw-like autoassociative networks. II. Recognition,” Network: Computation in Neural Systems, 6, No. 4, 535–549 (1995).
A. A. Frolov, D. Husek, and I. P. Muraviev, “Informational capacity and recall quality in sparsely encoded Hopfield-like neural network: Analytical approaches and computer simulation,” Neural Networks, 10, No. 5, 845–855 (1997).
A. A. Frolov, D. Husek, and P. Yu. Polyakov, “Recurrent-neural-network-based Boolean factor analysis and its application to word clustering,” IEEE Trans. on Neural Networks, 20, No. 7, 1073–1086 (2009).
A. A. Frolov, D. A. Rachkovskij, and D. Husek, “On informational characteristics of sparsely encoded binary auto-associative memory,” in: Proc. 9th Intern. Conf. on Neural Information Processing ICONIP’02, Orchid Country Club, Singapore (2002), pp. 235–238.
A. A. Frolov, D. A. Rachkovskij, and D. Husek, “On information characteristics of Willshaw-like auto-associative memory,” Neural Network World, 12, No. 2, 141–158 (2002).
A. A. Frolov, D. Husek, and D. A. Rachkovskij, “Time of searching for similar binary vectors in associative memory,” Cybernetics and Systems Analysis, 42, No. 5, 615–623 (2006).
D. W. Nowicki and O. K. Dekhtyarenko, “Averaging on Riemannian manifolds and unsupervised learning using neural associative memory,” in: Proc. ESANN 2005, Bruges, Belgium (2005), pp. 181–189.
D. Nowicki and H. Siegelmann, “Flexible kernel memory,” PLoS ONE, 5, No. 6 (2010): e10955. doi:10.1371/journal.pone.0010955
D. Nowicki, P. Verga, and H. Siegelmann, “Modeling reconsolidation in kernel associative memory,” PloS ONE, 8, No. 8 (2013): e68189. doi:10.1371/journal.pone.0068189
B. Emruli, R. W. Gayler, and F. Sandin, “Analogical mapping and inference with binary spatter codes and sparse distributed memory,” in: Proc. Intern. Joint Conf. On Neural Networks (IJCNN) (2013), pp. 1–8.
E. M. Kussul and D. A. Rachkovskij, “Multilevel assembly neural architecture and processing of sequences,” in: A. V. Holden and V. I. Kryukov (eds.), Neurocomputers and Attention, Vol. II, Connectionism and Neurocomputers, Manchester University Press, Manchester–New York (1991), pp. 577–590.
N. M. Amosov, T. N. Baidyk, A. D. Goltsev, A. M. Kasatkin, L. M. Kasatkina, E. M. Kussul, and D. A. Rachkovskij, Neurocomputers and Intelligent Robots [in Russian], Naukova Dumka, Kyiv (1991).
D. A. Rachkovskij, S. V. Slipchenko, E. M. Kussul, and T. N. Baidyk, “A binding procedure for distributed binary data representations,” Cybernetics and Systems Analysis, 41, No. 3, 319–331 (2005).
A. Letichevsky, A. Godlevsky, A. Letichevsky Jr, V. S. Potiyenko, and V. Peschanenko, “Properties of a predicate transformer of the VRS system,” Cybernetics and Systems Analysis, 46, No. 4, 521–532 (2010).
A. Letichevsky, A. Letychevsky Jr, and V. Peschanenko, “Insertion modeling system,” Lecture Notes in Comput. Sci., 7162, 262–274 (2011).
S. I. Gallant and T. W. Okaywe, “Representing objects, relations, and sequences,” Neural Computation, 25, No. 8, 2038–2078 (2013).
D. A. Rachkovskij, E. M. Kussul, and T. N. Baidyk, “Building a world model with structure-sensitive sparse binary distributed representations,” Biologically Inspired Cognitive Architectures, 3, 64–86 (2013).
A. A. Letichevsky, “Theory of interaction, insertion modeling, and cognitive architectures,” Biologically Inspired Cognitive Architectures, 8, 19–32 (2014).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 157–166, November–December, 2014.
Rights and permissions
About this article
Cite this article
Rachkovskij, D.A. Vector Data Transformation Using Random Binary Matrices. Cybern Syst Anal 50, 960–968 (2014). https://doi.org/10.1007/s10559-014-9687-4
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10559-014-9687-4