О способах экономии памяти при решении задач классификации линейным методом опорных векторов
Аннотация
Рассмотрена автоматическая классификация с использованием линейного метода опорных векторов с целыми коэффициентами, получаемыми при помощи округления вещественных. С помощью экспериментальных расчетов на реальном примере продемонстрировано, как можно достичь сокращения требуемого объёма памяти вычислительной системы за счёт представления использующихся в классификаторе целочисленных линейных полиномов.
Изучены и применены два способа: способ, основанный на экономном представлении совпадающих частей линейных полиномов, и способ, базирующийся на экономном представлении наиболее часто встречающихся в полиномах коэффициентов.
Для экспериментальных расчетов взяты наборы данных 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 Мб.
Использование результатов работы возможно при разработке программно-аппаратных средств для автоматической классификации.
Литература
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.
