On Increasing the Computation Efficiency in Classifying Images
Keywords:
image classification, polynomials, integers, Bayesian classifier
Abstract
Automatic classification of images using the Bayes classifier with integer coefficients is considered. It is shown that by representing the polynomials used in the classifier that differ from the generally accepted ones through indicating only nonzero coefficients, it is possible to save memory and reduce the number of operations while keeping the same classification quality.
The polynomial coefficients are rounded and represented using integers (fixed-point numbers). A polynomial storing method that makes it possible to store only nonzero coefficients of the polynomial is analyzed. In using this method, the vectors and numbers used for carrying out classification are stored in the usual way.
The MNIST database was used for carrying out the experiments. Seven bits were taken to represent the polynomial coefficients. For storing coefficients without rounding, 11.77 MB of memory is needed; for storing the rounded coefficients in the usual form, 2.93 MB of memory is needed; and for storing only nonzero rounded coefficients, 1.3 MB is needed. The number of addition and multiplication operations required to make a decision about the image class has been reduced significantly.
An economical method for storing matrices with polynomial coefficients on a disk is presented. In the experiment with the MNIST database, only 0.35 MB of memory had to be used for storing the polynomials in the database.
The study results can be used in elaborating software and hardware for automatic classification of images. It is also of interest to study similar techniques to improve the efficiency of computations in other classifiers.
References
1. Ту Дж. Р., Гонсалес Р. Принципы распознавания образов. М.: Мир, 1978.
2. Tschiatschek S., Paul K., Pernkopf F. Integer Bayesian Network Classifiers // Machine Learning and Knowledge Discovery in Databases. Berlin, Heidelberg: Springer, 2014. Pp. 209—224.
3. Белага Э.Г. О вычислении значений многочлена от одного переменного с предварительной обработкой коэффициентов // Проблемы кибернетики. М.: Физматгиз, 1961. Вып. 5. С. 7—15.
4. Пан В.Я. Некоторые схемы для вычисления значений полиномов с вещественными коэффициентами // Там же. С. 17—29.
5. Селезнева С.Н. Сложность систем функций алгебры логики и систем функций трехзначной логики в классах поляризованных полиномиальных форм // Дискретная математика. 2015. Т. 27. Вып. 1. С. 111—122.
6. Маркелов Н.К. Нижняя оценка сложности функций трехзначной логики в классе поляризованных полиномов // Вестник Московского университета. Серия 15. «Вычислительная математика и кибернетика». 2012. Вып. 3. С. 40—45.
7. Косовская Т.М. Самообучающаяся сеть с ячейками, реализующими предикативные формулы // Труды СПИИРАН. 2015. №. 6. С. 94—113.
8. Алексиадис Н.Ф. Алгоритмическая неразрешимость проблемы полноты для полиномов с целыми коэффициентами // Вестник МЭИ. 2015. № 3. С. 110—117.
9. Алексиадис Н.Ф. Алгоритмическая неразрешимость задачи о нахождении базиса конечной полной системы полиномов с целыми коэффициентами // Интеллектуальные системы. Теория и приложения. 2016. Т. 20. Вып. 3. С. 19—23.
10. Мамонтов А.И., Мещанинов Д.Г. Проблема полноты в функциональной системе линейных полиномов с целыми коэффициентами // Дискретная математика. 2010. Т. 22. № 4. С. 64—82.
11. Мамонтов А.И., Мещанинов Д.Г. Алгоритм распознавания полноты в функциональной системе L(Z) // Дискретная математика. 2014. Т. 26. № 1. С. 85—95.
12. Мамонтов А.И. Об использующем суперпозиции способе эффективного вычисления систем линейных полиномов с целыми коэффициентами // Интеллектуальные системы. Теория и приложения. 2016. Т. 20. Вып. 3. С. 58—63.
13. Мамонтов А.И., Рябинов С.М. Об одном методе экономии памяти при классификации текстов // Программные системы: теория и приложения. 2017. Т. 8. № 4 (35). С. 133—147.
14. Gorban A.N., Wunsch D.C. The General Approximation Theorem // Proc. IEEE IJCNN'98. 1998. Pp. 1271—1274.
15. Горбань А.Н. Обобщенная аппроксимационная теорема и вычислительные возможности нейронных сетей // Сибирский журнал вычислительной математики. 1998. Т. 1. № 1. С. 11—24.
16. Половников В.С. О нелинейных характеристиках нейронных схем в произвольных базисах // Интеллектуальные системы. 2013. Т. 17. № 1—4. С. 87—90.
17. Tschiatschek S., Pernkopf F. On Bayesian Network Classifiers with Reduced Precision Parameters // IEEE Trans. Pattern Analysis and Machine Intelligence. 2015. V. 37 (4). Pp. 774—785.
18. 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 II. Boston: Springer, 2008. V. 276. Pp. 427—431.
19. 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.
20. Shuang Wu, Guoqi Li, Feng Chen, Luping Shi. Training and Inference with Integers in Deep Neural Networks // Proc. ICLR. 2018. Pp. 1—14.
---
Для цитирования: Мамонтов А.И. О повышении эффективности вычислений при классификации изображений // Вестник МЭИ. 2019. № 5. С. 129—134. DOI: 10.24160/1993-6982-2019-5-129-134.
---
Работа выполнена при поддержке: РФФИ (проект № 17-01-00485а)
#
1. Tu Dzh. R., Gonsales R. Printsipy raspoznavaniya obrazov. M.: Mir, 1978. (in Russian).
2. Tschiatschek S., Paul K., Pernkopf F. Integer Bayesian Network Classifiers. Machine Learning and Knowledge Discovery in Databases. Berlin, Heidelberg: Springer, 2014:209—224.
3. Belaga E.G. O Vychislenii Znacheniy Mnogochlena ot Odnogo Peremennogo s Predvaritel'noy Obrabotkoy Koeffitsientov. Problemy Kibernetiki. M.: Fizmatgiz,1961;5:7—15. (in Russian).
4. Pan V.Ya. Nekotorye Skhemy dlya Vychisleniya Znacheniy Polinomov s Veshchestvennymi Koeffitsientami. Tam zhe:17—29. (in Russian).
5. Selezneva S.N. Slozhnost' Sistem Funktsiy Algebry Logiki i Sistem Funktsiy Trekhznachnoy Logiki v Klassah Polyarizovannyh Polinomial'nyh Form. Diskretnaya Matematika. 2015;27;1:111—122. (in Russian).
6. Markelov N.K. Nizhnyaya Otsenka Slozhnosti Funktsiy Trekhznachnoy Logiki v Klasse Polyarizovannyh Polinomov. Vestnik Moskovskogo Universiteta. Seriya 15. «Vychislitel'naya Matematika I Kibernetika». 2012;3: 40—45. (in Russian).
7. Kosovskaya T.M. Samoobuchayushchayasya Set' s Yacheykami, Realizuyushchimi Predikativnye Formuly. Trudy SPIIRAN. 2015;6:94—113. (in Russian).
8. Aleksiadis N.F. Algoritmicheskaya Nerazreshimost' Problemy Polnoty dlya Polinomov s Tselymi Koeffitsientami. Vestnik MEI. 2015;3:110—117. (in Russian).
9. Aleksiadis N.F. Algoritmicheskaya Nerazreshimost' Zadachi o Nahozhdenii Bazisa Konechnoy Polnoy Sistemy Polinomov s Tselymi Koeffitsientami. Intellektual'nye Sistemy. Teoriya I Prilozheniya. 2016;20;3:19—23. (in Russian).
10. Mamontov A.I., Meshchaninov D.G. Problema Polnoty v Funktsional'noy Sisteme Lineynyh Polinomov s Tselymi Koeffitsientami. Diskretnaya Matematika. 2010; 22;4:64—82. (in Russian).
11. Mamontov A.I., Meshchaninov D.G. Algoritm Raspoznavaniya Polnoty v Funktsional'noy Sisteme L(Z). Diskretnaya Matematika. 2014;26;1:85—95. (in Russian).
12. Mamontov A.I. Ob Ispol'zuyushchem Superpozitsii Sposobe Effektivnogo Vychisleniya Sistem Lineynyh Polinomov s Tselymi Koeffitsientami. Intellektual'nye Sistemy. Teoriya i Prilozheniya. 2016;20; 3:58—63. (in Russian).
13. 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).
14. Gorban A.N., Wunsch D.C. The General Approximation Theorem. Proc. IEEE IJCNN'98. 1998:1271—1274.
15. Gorban' A.N. Obobshchennaya approksimatsionnaya Teorema i Vychislitel'nye Vozmozhnosti Neyronnyh Setey. Sibirskiy Zhurnal vychislitel'noy matematiki. 1998;1;1:11—24. (in Russian).
16. Polovnikov V.S. O Nelineynyh Kharakteristikah Neyronnyh Skhem v Proizvol'nyh Bazisah. Intellektual'nye Sistemy. 2013;17;1—4:87—90. (in Russian).
17. Tschiatschek S., Pernkopf F. On Bayesian Network Classifiers with Reduced Precision Parameters. IEEE Trans. Pattern Analysis and Machine Intelligence. 2015; 37 (4):774—785.
18. 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 II. Boston: Springer, 2008;276:427—431.
19. Anguita D., Ghio A., Pischiutta S., Ridella S. A Support Vector Machine with Integer Parameters. Neurocomputing. 2008;72;1—3:480—489.
20. Shuang Wu, Guoqi Li, Feng Chen, Luping Shi. Training and Inference with Integers in Deep Neural Networks. Proc. ICLR. 2018:1—14.
---
For citation: Mamontov A.I. On Increasing the Computation Efficiency in Classifying Images. Bulletin of MPEI. 2019;5:129—134. (in Russian). DOI: 10.24160/1993-6982-2019-5-129-134.
---
The work is executed at support: RFBR (project No. 17-01-00485а)
2. Tschiatschek S., Paul K., Pernkopf F. Integer Bayesian Network Classifiers // Machine Learning and Knowledge Discovery in Databases. Berlin, Heidelberg: Springer, 2014. Pp. 209—224.
3. Белага Э.Г. О вычислении значений многочлена от одного переменного с предварительной обработкой коэффициентов // Проблемы кибернетики. М.: Физматгиз, 1961. Вып. 5. С. 7—15.
4. Пан В.Я. Некоторые схемы для вычисления значений полиномов с вещественными коэффициентами // Там же. С. 17—29.
5. Селезнева С.Н. Сложность систем функций алгебры логики и систем функций трехзначной логики в классах поляризованных полиномиальных форм // Дискретная математика. 2015. Т. 27. Вып. 1. С. 111—122.
6. Маркелов Н.К. Нижняя оценка сложности функций трехзначной логики в классе поляризованных полиномов // Вестник Московского университета. Серия 15. «Вычислительная математика и кибернетика». 2012. Вып. 3. С. 40—45.
7. Косовская Т.М. Самообучающаяся сеть с ячейками, реализующими предикативные формулы // Труды СПИИРАН. 2015. №. 6. С. 94—113.
8. Алексиадис Н.Ф. Алгоритмическая неразрешимость проблемы полноты для полиномов с целыми коэффициентами // Вестник МЭИ. 2015. № 3. С. 110—117.
9. Алексиадис Н.Ф. Алгоритмическая неразрешимость задачи о нахождении базиса конечной полной системы полиномов с целыми коэффициентами // Интеллектуальные системы. Теория и приложения. 2016. Т. 20. Вып. 3. С. 19—23.
10. Мамонтов А.И., Мещанинов Д.Г. Проблема полноты в функциональной системе линейных полиномов с целыми коэффициентами // Дискретная математика. 2010. Т. 22. № 4. С. 64—82.
11. Мамонтов А.И., Мещанинов Д.Г. Алгоритм распознавания полноты в функциональной системе L(Z) // Дискретная математика. 2014. Т. 26. № 1. С. 85—95.
12. Мамонтов А.И. Об использующем суперпозиции способе эффективного вычисления систем линейных полиномов с целыми коэффициентами // Интеллектуальные системы. Теория и приложения. 2016. Т. 20. Вып. 3. С. 58—63.
13. Мамонтов А.И., Рябинов С.М. Об одном методе экономии памяти при классификации текстов // Программные системы: теория и приложения. 2017. Т. 8. № 4 (35). С. 133—147.
14. Gorban A.N., Wunsch D.C. The General Approximation Theorem // Proc. IEEE IJCNN'98. 1998. Pp. 1271—1274.
15. Горбань А.Н. Обобщенная аппроксимационная теорема и вычислительные возможности нейронных сетей // Сибирский журнал вычислительной математики. 1998. Т. 1. № 1. С. 11—24.
16. Половников В.С. О нелинейных характеристиках нейронных схем в произвольных базисах // Интеллектуальные системы. 2013. Т. 17. № 1—4. С. 87—90.
17. Tschiatschek S., Pernkopf F. On Bayesian Network Classifiers with Reduced Precision Parameters // IEEE Trans. Pattern Analysis and Machine Intelligence. 2015. V. 37 (4). Pp. 774—785.
18. 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 II. Boston: Springer, 2008. V. 276. Pp. 427—431.
19. 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.
20. Shuang Wu, Guoqi Li, Feng Chen, Luping Shi. Training and Inference with Integers in Deep Neural Networks // Proc. ICLR. 2018. Pp. 1—14.
---
Для цитирования: Мамонтов А.И. О повышении эффективности вычислений при классификации изображений // Вестник МЭИ. 2019. № 5. С. 129—134. DOI: 10.24160/1993-6982-2019-5-129-134.
---
Работа выполнена при поддержке: РФФИ (проект № 17-01-00485а)
#
1. Tu Dzh. R., Gonsales R. Printsipy raspoznavaniya obrazov. M.: Mir, 1978. (in Russian).
2. Tschiatschek S., Paul K., Pernkopf F. Integer Bayesian Network Classifiers. Machine Learning and Knowledge Discovery in Databases. Berlin, Heidelberg: Springer, 2014:209—224.
3. Belaga E.G. O Vychislenii Znacheniy Mnogochlena ot Odnogo Peremennogo s Predvaritel'noy Obrabotkoy Koeffitsientov. Problemy Kibernetiki. M.: Fizmatgiz,1961;5:7—15. (in Russian).
4. Pan V.Ya. Nekotorye Skhemy dlya Vychisleniya Znacheniy Polinomov s Veshchestvennymi Koeffitsientami. Tam zhe:17—29. (in Russian).
5. Selezneva S.N. Slozhnost' Sistem Funktsiy Algebry Logiki i Sistem Funktsiy Trekhznachnoy Logiki v Klassah Polyarizovannyh Polinomial'nyh Form. Diskretnaya Matematika. 2015;27;1:111—122. (in Russian).
6. Markelov N.K. Nizhnyaya Otsenka Slozhnosti Funktsiy Trekhznachnoy Logiki v Klasse Polyarizovannyh Polinomov. Vestnik Moskovskogo Universiteta. Seriya 15. «Vychislitel'naya Matematika I Kibernetika». 2012;3: 40—45. (in Russian).
7. Kosovskaya T.M. Samoobuchayushchayasya Set' s Yacheykami, Realizuyushchimi Predikativnye Formuly. Trudy SPIIRAN. 2015;6:94—113. (in Russian).
8. Aleksiadis N.F. Algoritmicheskaya Nerazreshimost' Problemy Polnoty dlya Polinomov s Tselymi Koeffitsientami. Vestnik MEI. 2015;3:110—117. (in Russian).
9. Aleksiadis N.F. Algoritmicheskaya Nerazreshimost' Zadachi o Nahozhdenii Bazisa Konechnoy Polnoy Sistemy Polinomov s Tselymi Koeffitsientami. Intellektual'nye Sistemy. Teoriya I Prilozheniya. 2016;20;3:19—23. (in Russian).
10. Mamontov A.I., Meshchaninov D.G. Problema Polnoty v Funktsional'noy Sisteme Lineynyh Polinomov s Tselymi Koeffitsientami. Diskretnaya Matematika. 2010; 22;4:64—82. (in Russian).
11. Mamontov A.I., Meshchaninov D.G. Algoritm Raspoznavaniya Polnoty v Funktsional'noy Sisteme L(Z). Diskretnaya Matematika. 2014;26;1:85—95. (in Russian).
12. Mamontov A.I. Ob Ispol'zuyushchem Superpozitsii Sposobe Effektivnogo Vychisleniya Sistem Lineynyh Polinomov s Tselymi Koeffitsientami. Intellektual'nye Sistemy. Teoriya i Prilozheniya. 2016;20; 3:58—63. (in Russian).
13. 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).
14. Gorban A.N., Wunsch D.C. The General Approximation Theorem. Proc. IEEE IJCNN'98. 1998:1271—1274.
15. Gorban' A.N. Obobshchennaya approksimatsionnaya Teorema i Vychislitel'nye Vozmozhnosti Neyronnyh Setey. Sibirskiy Zhurnal vychislitel'noy matematiki. 1998;1;1:11—24. (in Russian).
16. Polovnikov V.S. O Nelineynyh Kharakteristikah Neyronnyh Skhem v Proizvol'nyh Bazisah. Intellektual'nye Sistemy. 2013;17;1—4:87—90. (in Russian).
17. Tschiatschek S., Pernkopf F. On Bayesian Network Classifiers with Reduced Precision Parameters. IEEE Trans. Pattern Analysis and Machine Intelligence. 2015; 37 (4):774—785.
18. 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 II. Boston: Springer, 2008;276:427—431.
19. Anguita D., Ghio A., Pischiutta S., Ridella S. A Support Vector Machine with Integer Parameters. Neurocomputing. 2008;72;1—3:480—489.
20. Shuang Wu, Guoqi Li, Feng Chen, Luping Shi. Training and Inference with Integers in Deep Neural Networks. Proc. ICLR. 2018:1—14.
---
For citation: Mamontov A.I. On Increasing the Computation Efficiency in Classifying Images. Bulletin of MPEI. 2019;5:129—134. (in Russian). DOI: 10.24160/1993-6982-2019-5-129-134.
---
The work is executed at support: RFBR (project No. 17-01-00485а)
Published
2018-11-08
Section
Theoretical Foundations of Computer Science (05.13.17)
