О способах экономии памяти при решении задач классификации линейным методом опорных векторов

  • Андрей [Andrey] Игоревич [I.] Мамонтов [Mamontov]
Ключевые слова: линейные полиномы, целые числа, метод опорных векторов, классификация

Аннотация

Рассмотрена автоматическая классификация с использованием линейного метода опорных векторов с целыми коэффициентами, получаемыми при помощи округления вещественных. С помощью экспериментальных расчетов на реальном примере продемонстрировано, как можно достичь сокращения требуемого объёма памяти вычислительной системы за счёт представления использующихся в классификаторе целочисленных линейных полиномов.

Изучены и применены два способа: способ, основанный на экономном представлении совпадающих частей линейных полиномов, и способ, базирующийся на экономном представлении наиболее часто встречающихся в полиномах коэффициентов.

Для экспериментальных расчетов взяты наборы данных Reuters-21578 и 20Newsgroups. Отмечено, что в эксперименте с набором Reuters-21578 количество необходимых для классификации признаков оптимизировалось, а в эксперименте с набором 20Newsgroups — нет.

В эксперименте с набором данных Reuters-21578 для представления коэффициентов полиномов использовано восемь бит. При хранении коэффициентов без округлений необходимо 3,81 Мб. Хранение округленных коэффициентов без применения предложенных способов требует 0,48 Мб, с использованием первого способа — 0,16 Мб, а второго — 0,148 Мб. В сжатом виде хранение округленных коэффициентов требует 0,12 Мб при первом способе и 0,09 Мб — при втором.

В эксперименте с набором 20Newsgroups для представления коэффициентов полиномов использовали двенадцать бит. При хра­нении коэффициентов без округлений нужно 19,86 Мб. При хранении округленных коэффициентов без применения способов — 4,96 Мб, при использовании первого способа — 4,2 Мб, второго — 3,98 Мб. При хранении округленных коэффициентов в сжатом виде первым способом потребовалось 1,45 Мб, а вторым — 1,27 Мб.

Использование результатов работы возможно при разработке программно-аппаратных средств для автоматической классификации.

Сведения об авторе

Андрей [Andrey] Игоревич [I.] Мамонтов [Mamontov]

кандидат технических наук, доцент кафедры математического и компьютерного моделирования НИУ «МЭИ», e-mail: MamontovAI@yandex.ru

Литература

1. Anguita, D., Ghio, A., Pischiutta, S., Ridella, S. A Support Vector Machine with Integer Parameters // Neurocomputing. 2008. V. 72. No. 1—3. Pp. 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. 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.
Опубликован
2019-11-20
Раздел
Теоретические основы информатики (05.13.17)