Winograd’s Inequality: Effectiveness for Efficient Training of Deep Neural Networks

Full Text (PDF, 745KB), PP.49-58

Views: 0 Downloads: 0


D.T.V. Dharmajee Rao 1,* K.V. Ramana 2

1. Aditya Institute of Technology and Management, Tekkali-532201, Srikakulam, Andhra Pradesh, India

2. JNTUK College of Engineering, JNTUK University, Kakinada - 533003, Andhra Pradesh, India

* Corresponding author.


Received: 2 Nov. 2017 / Revised: 10 Feb. 2018 / Accepted: 24 Apr. 2018 / Published: 8 Jun. 2018

Index Terms

Deep Neural Networks, Backpropagation Algorithm, Boltzmann Machine Algorithm, Matrix multiplication algorithms: Naive, Strasen’s, Winograd’s algorithms


Matrix multiplication is widely used in a variety of applications and is often one of the core components of many scientific computations. This paper will examine three algorithms to compute the product of two matrices: the Naive, Strassen’s and Winograd’s algorithms. One of the main factors of determining the efficiency of an algorithm is the execution time factor, how much time the algorithm takes to accomplish its work. All the three algorithms will be implemented and the execution time will be calculated and we find that Winograd’s algorithm is the best and fast method experimentally for finding matrix multiplication. Deep Neural Networks are used for many applications. Training a Deep Neural Network is a time consuming process, especially when the number of hidden layers and nodes is large. The mechanism of Backpropagation Algorithm and Boltzmann Machine Algorithm for training a Deep Neural Network is revisited and considered how the sum of weighted input is computed. The process of computing the sum of product of weight and input matrices is carried out for several hundreds of thousands of epochs during the training of Deep Neural Network. We propose to modify Backpropagation Algorithm and Boltzmann Machine Algorithm by using fast Winograd’s algorithm. Finally, we find that the proposed methods reduce the long training time of Deep Neural Network than existing direct methods.

Cite This Paper

D.T.V. Dharmajee Rao, K.V. Ramana, "Winograd’s Inequality: Effectiveness for Efficient Training of Deep Neural Networks", International Journal of Intelligent Systems and Applications(IJISA), Vol.10, No.6, pp.49-58, 2018. DOI:10.5815/ijisa.2018.06.06


[1]Khaled Thabet, “Matrix Multiplication Algorithms”, IJCSNS, vol.12, No.2, February 2012, pp: 74-79.
[2]Rita Georgina Guimaraes, Renata L. Rosa, Denise De Gaetano, Demostenes Z. Rodriguez, and Graca Bressan, “Age Groups Classification in Social Network Using Deep Learning”, IEEE Access, Vol. 5, pp. 10805-10816, May 2017.DOI: 10.1109/ACCESS.2017.2706674
[3]Kamini Goyal, Dapinder Kaur,"A Novel Vehicle Classification Model for Urban Traffic Surveillance Using the Deep Neural Network Model", International Journal of Education and Management Engineering(IJEME), Vol.6, No.1, pp.18-31, 2016.DOI: 10.5815/ijeme.2016.01.03
[4]Xinhuai Zou, Ming Cheng, Cheng Wang, Yan Xia, and Jonathan Li, “Tree Classification in Complex Forest Point Clouds Based on Deep Learning”, IEEE Geoscience and Remote Sensing Letters, Vol. 14, No. 12, December 2017, pp. 2360-2364.
[5]C. Bhanuprakash, Y. S. Nijagunarya, and M. A. Jayaram, “Clustering of Faculty by Evaluating their Appraisal Performance by Using Feed Forward Neural Network Approach”, International Journal of Intelligent Systems and Applications (IJISA), Vol.9, No.3, pp.34-40, 2017.DOI: 10.5815/ijisa.2017.03.05
[6]Haytham M. Fayek, Margaret Lech, and Lawrence Cavedon, “Evaluating deep learning architectures for Speech Emotion Recognition”, Neural Networks, Special Issue 2017, Article in Press.
[7]Ruhi Srikaya, Geoffrey E. Hinton, and Anoop deoras, “Application of Deep Belief Networks for Natural Language Understanding”, IEEE/ACM Transactions on Audio, Speech, and Language Processing, Vol. 22, No. 4, April 2014.
[8]John Paul T. Yusiong, “Optimizing Artificial Neural Networks using Cat Swarm Optimization Algorithm,” I. J. Intelligent Systems and Applications, 2013, 01, 69-80, DOI: 10.5815/ijisa.2013.01.07
[9]Kuo-Liang Chung, Wen-Ming Yan, and Jung-Gen Wu, “A Simple Improved Full Search for Vector Quantization Based on Winograd’s Identity”, IEEE Signal Processing Letters, vol. 7, No. 12, December 2000, pp. 342-344.
[10]N.B. Venkteswarulu and P.S. V.S.K. Raju “Winograd’s method: Aperspective for some pattern recognintion problems”, Pattern Recognitions Letters, Vol-15, No.2, PP. 105-109, 1994.
[11]Ch. Ramesh, Dr. N. B. Venkateswarlu, and Dr. J. V. R. Murthy, “Fast DCT Algorithm using Winograd’s Method,” IJECET, vol. 3, Issue 1, January-June 2012, pp. 98-110.
[12]D. J. Nagendra Kumar, J.V.R. Murthy and N.B. Venkateswarlu, “Computation Reduction of Expectation Maximization Clustering using Winograd’s Method”, 4th International Conference on Electronics Computer Technology (ICECT 2012), pp. 255 to 259.
[13]Steven Huss-Lederman, Elaine M. Jacobson, Jeremy R. Johnson, Anna Tsao, and Thomas Turnbull, “Implementation of Strassen’s Algorithm for Matrix Multiplication”, IEEE Conference on Super Computing, January 1996. DOI: 10.1109/SUPERC.1996.183534.
[14]Udi Manber, Introduction to Algorithms: A Creative Approach, pp.301-304, Pearson Education, New Jersey, 1989.
[15]Shaminder Singh, and Jasmeen Gill, “Temporal Weather Prediction using Backpropagation based Genetic Algorithm Technique”, International Journal of Intelligent Systems and Applications, 2014, 12, 55-61. DOI:10.5815/ijisa.2014.12.08.
[16]Jurgen Schmidhuber, “Deep learning in neural networks: An overview”, Neural Networks, 61, 85-117,
[17]Musab Coskun, Ozal Yildirim, and Aysegul Ucar, and Yakup Demir, “An Overview of Popular Deep Learning Methods”, EJT,Vol. 7, Number 2, pp. 165-176, December 2017, DOI: 10.23884/EJT.2017.7.2.11
[18]Pierre Baldi, Peter Sadowski, and Zhiqin Lu, “Learning in the Machine: The Symmetries of the Deep Learning Channel,” Neural Networks 95(2017), pp. 110-114,
[19]C. L. Philip Chen, Chun-Yang Zhang, Long Chen, and Min Gan, “Fuzzy Restricted Boltzmann Machine for the Enhancement of Deep Learning”, IEEE Transactions on Fuzzy Systems, vol.23, No.6, Dec.2015, pp.2163-2173.
[20]Mohammad Rafiqul Alam, Mohammed Bennamoun, Roberto Togneri, and Ferdous Sohel, “A joint Deep Boltzmann Machine (jDBM) Model for Person Identification Using Mobile Phone Data”, IEEE Transactions on Multimedia, vol. 19, No. 2, February 2017, pp. 317-326.