On Memory Saving Methods in Solving Classification Problems by Using the Linear Support Vector Machine Techniques
DOI:
https://doi.org/10.24160/1993-6982-2020-4-129-135Keywords:
linear polynomials, integers, support vector machine, classificationAbstract
Automatic classification carried out using the linear support vector machine techniques with integer coefficients obtained from real ones by rounding them is considered. It is demonstrated, by means of experimental calculations for a real example, how the required amount of computing system memory can be reduced by representing the integer linear polynomials used in the classifier.
Two methods are considered: a method based on an economical representation of the matching parts of linear polynomials and a method based on an economical representation of the coefficients most frequently encountered in the polynomials.
For experimental computations, the Reuters-21578 and 20Newsgroups data sets were used. In the experiment with the Reuters-21578 data set, the number of features necessary for classification was optimized, and in the experiment with the 20Newsgroups data set, this was not done.
In the experiment with the Reuters-21578 data set, eight bits were used to represent polynomial coefficients. In storing coefficients without rounding, 3.81 MB of memory space is needed. For storing the rounded coefficients without using the proposed methods, 0.48 MB of memory space is required; in the cases of using the first and second methods, 0.16 and 0.148 MB of memory space, respectively, are required. For storing rounded coefficients in a compressed form, 0.12 and 0.09 MB of memory space, respectively, are required in the cases of using the first and second methods.
In the experiment with the 20Newsgroups data set, twelve bits were used to represent polynomial coefficients. For storing coefficients without rounding, 19.86 MB of memory space is required. For storing rounded coefficients without using the proposed methods, 4.96 MB of memory space is required; in the cases of using the first and second methods, 4.2 and 3.98 MB of memory space, respectively, are required. For storing rounded coefficients in a compressed form, 1.45 and 1.27 MB of memory space, respectively, are required in the cases of using the first and second methods. The obtained study results can be used in developing software and hardware for solving automatic classification problems.
References
2. Tschiatschek S., Paul K., Pernkopf F. Integer Bayesian Network Classifiers // Machine Learning and Knowledge Discovery in Databases. Lecture Notes in Computer Science. 2014. V. 8726. Pp. 209—224.
3. Han S., Mao H., Dally W.J. Deep Compression: Compressing Deep Neural Network with Pruning, Trained Quantization and Huffman Coding // Proc. Intern. Conf. Learning Representation. San Juan, 2016. Pp. 1—14.
4. Liu B., Wang M., Foroosh H., Tappen M., Penksy M. Sparse Convolutional Neural Networks // IEEE Trans. Conf. Computer Vision and Pattern Recognition. Boston, 2015. Pp. 806—814.
5. Lan L., Wang Z., Zhe S., Cheng W., Wang J., Zhang K. Scaling Up Kernel SVM on Limited Resources: a Low-rank Linearization Approach // IEEE Trans. Neural Networks and Learning Systems. 2019. V. 30. Iss. 2. Pp. 369—378.
6. Белага Э.Г. О вычислении значений многочлена от одного переменного с предварительной обработкой коэффициентов // Проблемы кибернетики. 1961. Вып. 5. С. 7—15.
7. Пан В.Я. Некоторые схемы для вычисления значений полиномов с вещественными коэффициентами // Там же. С. 17—29.
8. Селезнева С.Н. Сложность систем функций алгебры логики и систем функций трехзначной логики в классах поляризованных полиномиальных форм // Дискретная математика. 2015. Т. 27. Вып. 1. С. 111—122.
9. Маркелов Н.К. Нижняя оценка сложности функций трехзначной логики в классе поляризованных полиномов // Вестник Московского университета. Серия «Вычислительная математика и кибернетика». 2012. Вып. 3. С. 40—45.
10. Алексиадис Н.Ф. Алгоритмическая неразрешимость проблемы полноты для полиномов с целыми коэффициентами // Вестник МЭИ. 2015. № 3. С. 110—117.
11. Алексиадис Н.Ф. Алгоритмическая неразрешимость задачи о нахождении базиса конечной полной системы полиномов с целыми коэффициентами // Интеллектуальные системы. Теория и приложения. 2016. Т. 20. Вып. 3. С. 19—23.
12. Мамонтов А.И. Применение функциональных систем полиномов при классификации и поиске информации // Вестник МЭИ. 2012. № 6. С. 117—123.
13. Мамонтов А.И., Мещанинов Д.Г. Проблема полноты в функциональной системе линейных полиномов с целыми коэффициентами // Дискретная математика. 2010. Т. 22. № 4. С. 64—82.
14. Мамонтов А.И., Мещанинов Д.Г. Алгоритм распознавания полноты в функциональной системе L(Z) // Дискретная математика. 2014. Т. 26. № 1. С. 85—95.
15. Мамонтов А.И. Об использующем суперпозиции способе эффективного вычисления систем линейных полиномов с целыми коэффициентами // Интеллектуальные системы. Теория и приложения. 2016.Т. 20. Вып. 3. С. 58—63.
16. Мамонтов А.И., Рябинов С.М. Об одном методе экономии памяти при классификации текстов // Программные системы: теория и приложения. 2017. Т. 8. № 4(35). С. 133—147.
17. Мамонтов А.И. О повышении эффективности вычислений при классификации изображений // Вестник МЭИ. 2019. № 5. С. 129—134.
18. Gorban A.N., Wunsch D.C. The General Approximation Theorem // IEEE Trans. World Congress on Computational Intelligence. Anchorage, 1998. Pp. 1271—1274.
19. Горбань А.Н. Обобщенная аппроксимационная теорема и вычислительные возможности нейронных сетей // Сибирский журнал вычислительной математики. 1998. Т. 1. № 1. С. 11—24.
20. Половников В.С. О нелинейных характеристиках нейронных схем в произвольных базисах // Интеллектуальные системы. 2013. Т. 17. № 1—4. С. 87—90.
21. Anguita D., Pischiutta S., Ridella S., Sterpi D. Feed–forward SVM without Multipliers // IEEE Trans. Neural Networks. 2006. V. 17. Pp. 1328—1331.
22. Tschiatschek S., Pernkopf F. On Bayesian Net-work Classifiers with Reduced Precision Parameters // IEEE Trans. Pattern Analysis and Machine Intelligence. 2015. V. 37(4). Pp. 774—785.
23. Yi Y., Hangping Z., Bin Z. A New Learning Algorithm for Neural Networks with Integer Weights and Quantized Non-linear Activation Functions // Artificial Intelligence in Theory and Practice. Boston: Springer, 2008. Pp. 427—431.
24. Shuang Wu, Guoqi Li, Feng Chen, Luping Shi. Training and Inference with Integers in Deep Neural Networks // Proc. VI Intern. Conf. Learning Representations. 2018. Pp. 1—14.
25. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. М.: Наука, 1974.
26. Fan R.-E., Chang K.-W., Hsieh C.-J., Wang X.-R., Lin C.-J. LIBLINEAR: a Library for Large Linear Classification // J. Machine Learning Research. 2008. V. 9. Pp. 1871—1874.
---
Для цитирования: Мамонтов А.И. О способах экономии памяти при решении задач классификации линейным методом опорных векторов // Вестник МЭИ. 2020. № 4. С. 129—135. DOI: 10.24160/1993-6982-2020-4-129-135.
#
1. Anguita, D., Ghio, A., Pischiutta, S., Ridella, S. A Support Vector Machine with Integer Parameters. Neurocomputing. 2008;72;1—3:480—489.
2. Tschiatschek S., Paul K., Pernkopf F. Integer Bayesian Network Classifiers. Machine Learning and Knowledge Discovery in Databases. Lecture Notes in Computer Science. 2014;8726:209—224.
3. Han S., Mao H., Dally W.J. Deep Compression: Compressing Deep Neural Network with Pruning, Trained Quantization and Huffman Coding. Proc. Intern. Conf. Learning Representation. San Juan, 2016:1—14.
4. Liu B., Wang M., Foroosh H., Tappen M., Penksy M. Sparse Convolutional Neural Networks. IEEE Trans. Conf. Computer Vision and Pattern Recognition. Boston, 2015:806—814.
5. Lan L., Wang Z., Zhe S., Cheng W., Wang J., Zhang K. Scaling Up Kernel SVM on Limited Resources: a Low-rank Linearization Approach. IEEE Trans. Neural Networks and Learning Systems. 2019;30;2:369—378.
6. Belaga E.G. O Vychislenii Znacheniy Mnogochlena ot Odnogo Peremennogo s Predvaritel'noy Obrabotkoy Koeffitsientov. Problemy Kibernetiki. 1961;5:7—15. (in Russian).
7. Pan V.Ya. Nekotorye Skhemy dlya Vychisleniya Znacheniy Polinomov s Veshchestvennymi Koeffitsientami. Tam zhe:17—29. (in Russian).
8. Selezneva S.N. Slozhnost' Sistem Funktsiy Algebry Logiki i Sistem Funktsiy Trekhznachnoy Logiki v Klassakh Polyarizovannykh Polinomial'nykh Form. Diskretnaya Matematika. 2015;27;1:111—122. (in Russian).
9. Markelov N.K. Nizhnyaya Otsenka Slozhnosti Funtsiy Trekhznachnoy Logiki v Klasse Polyarizovannykh Polinomov. Vestnik Moskovskogo Universiteta. Seriya «Vychislitel'naya Matematika i Kibernetika». 2012;3:40—45. (in Russian).
10. Aleksiadis N.F. Algoritmicheskaya Nerazreshimost' Problemy Polnoty dlya Polinomov s Tselymi Koeffitsientami. Vestnik MEI. 2015;3:110—117. (in Russian).
11. Aleksiadis N.F. Algoritmicheskaya Nerazreshimost' Zadachi o Nakhozhdenii Bazisa Konechnoy Polnoy Sistemy Polinomov s Tselymi Koeffitsientami. Intellektual'nye Sistemy. Teoriya i Prilozheniya. 2016;20;3:19—23. (in Russian).
12. Mamontov A.I. Primenenie Funktsional'nykh Sistem Polinomov pri Klassifikatsii i Poiske Informatsii. Vestnik MEI. 2012;6:117—123. (in Russian).
13. Mamontov A.I., Meshchaninov D.G. Problema Polnoty v Funktsional'noy Sisteme Lineynykh Polinomov s Tselymi Koeffitsientami. Diskretnaya Matematika. 2010; 22;4:64—82. (in Russian).
14. Mamontov A.I., Meshchaninov D.G. Algoritm Raspoznavaniya Polnoty v Funktsional'noy Sisteme L(Z). Diskretnaya Matematika. 2014;26;1:85—95. (in Russian).
15. Mamontov A.I. Ob Ispol'zuyushchem Superpozitsii Sposobe Effektivnogo Vychisleniya Sistem Lineynykh Polinomov s Tselymi Koeffitsientami. Intellektual'nye Sistemy. Teoriya i Prilozheniya. 2016;20;3:58—63. (in Russian).
16. Mamontov A.I., Ryabinov S.M. Ob Odnom Metode Ekonomii Pamyati pri Klassifikatsii Tekstov. Programmnye Sistemy: Teoriya i Prilozheniya. 2017;8; 4(35):133—147. (in Russian).
17. Mamontov A.I. O Povyshenii Effektivnosti Vychisleniy pri Klassifikatsii Izobrazheniy. Vestnik MEI. 2019;5:129—134. (in Russian).
18. Gorban A.N., Wunsch D.C. The General Approximation Theorem. IEEE Trans. World Congress on Computational Intelligence. Anchorage, 1998:1271—1274.
19. Gorban' A.N. Obobshchennaya Approksimatsionnaya Teorema i Vychislitel'nye Vozmozhnosti Neyronnykh Setey. Sibirskiy Zhurnal Vychislitel'noy Matematiki. 1998; 1;1:11—24. (in Russian).
20. Polovnikov V.S. O Nelineynykh Kharakteristikakh Neyronnykh Skhem v Proizvol'nykh Bazisakh. Intellektual'nye Sistemy. 2013;17;1—4:87—90. (in Russian).
21. Anguita D., Pischiutta S., Ridella S., Sterpi D. Feed–forward SVM without Multipliers. IEEE Trans. Neural Networks. 2006;17:1328—1331.
22. Tschiatschek S., Pernkopf F. On Bayesian Net-work Classifiers with Reduced Precision Parameters. IEEE Trans. Pattern Analysis and Machine Intelligence. 2015; 37(4):774—785.
23. Yi Y., Hangping Z., Bin Z. A New Learning Algorithm for Neural Networks with Integer Weights and Quantized Non-linear Activation Functions. Artificial Intelligence in Theory and Practice. Boston: Springer, 2008:427—431.
24. Shuang Wu, Guoqi Li, Feng Chen, Luping Shi. Training and Inference with Integers in Deep Neural Networks. Proc. VI Intern. Conf. Learning Representations. 2018:1—14.
25. Vapnik V.N., Chervonenkis A.Ya. Teoriya Raspoznavaniya Obrazov. M.: Nauka, 1974.
26. Fan R.-E., Chang K.-W., Hsieh C.-J., Wang X.-R., Lin C.-J. LIBLINEAR: a Library for Large Linear Classification. J. Machine Learning Research. 2008;9: 1871—1874.
---
For citation: Mamontov A.I. On Memory Saving Methods in Solving Classification Problems by Using the Linear Support Vector Machine Techniques. Bulletin of MPEI. 2020;4:129—135. (in Russian). DOI: 10.24160/1993-6982-2020-4-129-135.

