Nesta seção, apresento os resultados obtidos com as simulações descritas no Capítulo 3. Para maior clareza, utilizo o termo original para referenciar os resultados obtidos com os modelos originais D e w treinados com LAST e o termo proposto para referenciar os resultados obtidos com D e w modificados com as técnicas que proponho.
Os resultados obtidos nos conjuntos de testes das três bases de dados binárias são mostrados na Figura 4.4, na qual os três gráficos superiores mostram a quantidade de bits necessária para se realizar a classificação e os três gráficos inferiores mostram a acurácia de classificação.
Dictionary size 0 100 200 300 400 Number of bits D'X 0 10 20 30 40 50 60 Original Proposed N úm e ro de bi ts e m D T X Número de átomos
(a) bark versus woodgrain
Dictionary size 0 100 200 300 400 Number of bits D'X 0 10 20 30 40 50 60 Original Proposed N úm e ro de bi ts e m D TX Número de átomos
(b) pigskin versus pressedcl
Dictionary size 0 100 200 300 400 Number of bits D'X 0 10 20 30 40 50 60 Original Proposed N úm e ro de bi ts e m D T X Número de átomos
(c) CIFAR-10 deer versus horse
Dictionary size 0 100 200 300 400 Accuracy (%) 50 60 70 80 90 100 Original Proposed A c urá c ia (%) Número de átomos
(d) bark versus woodgrain
Dictionary size 0 100 200 300 400 Accuracy (%) 50 60 70 80 90 100 Original Proposed A c urá c ia (%) Número de átomos
(e) pigskin versus pressedcl
Dictionary size 0 100 200 300 400 Accuracy (%) 50 60 70 80 90 100 Original Proposed A c urá c ia (%) Número de átomos
(f) CIFAR-10 deer versus horse Figura 4.4: Comparação dos resultados das simulações com o modelos originais treinados com o LAST e os modelos modificados com as técnicas que proponho. Para a classificação em tempo de teste de cada base de dados binária, os gráficos apresentam o compromisso existente entre o número de bits necessário (parte de cima) e a acurácia de classificação (parte de baixo). Observe que as técnicas que proponho reduzem para quase metade a quantidade de bits necessária com uma perda limitada de acurácia de classificação. As bases de dados utilizadas estão descritas na Seção4.2.
Como apresentado nas Figura4.4(d),4.4(e) e 4.4(f) as técnicas que proponho produzem uma limitada diminuição na acurácia de classificação. Cabe lembrar que as técnicas que proponho reduzem o custo computacional de classificação em hardware, visto que operações em ponto flutuante são trocadas por operações em inteiro e cada multiplicação é substituída por um simples deslocamento de bit.
Além da redução promovida pela troca de operações custosas por operações mais eficientes em hardware, as técnicas que proponho também reduzem a quantidade de bits necessária para efetuar a computação da multiplicação D⊤X, que é a parte de maior custo
computacional da representação esparsa. Como apresentado na Figura 4.4(a), 4.4(b) e
para a multiplicação D⊤X.
Perceba que as acurácias originais na Figura4.4(d) e4.4(e) são inferiores às apresentadas em [13], mesmo para a configuração original do LAST. A razão dessa diferença se deve ao fato de eu ter utilizado um conjunto de treinamento disjunto do conjunto de testes para não superestimar a acurácia de classificação do modelo. Além disso, treinei D e w com apenas 80% do conjunto de treinamento, conforme descrito na Seção 4.2.
Apresento na Tabela 4.1 os resultados das simulações feitas com as bases de dados MNIST e CIFAR-10. Assim como no caso da classificação binária, as técnicas que proponho permitem o uso de operações eficientes em hardware ao custo de uma limitada perda de acurácia de classificação.
Tabela 4.1: Comparação dos resultados originais e propostos no quesito taxa de erro de classificação e número de bits necessário para o cálculo da multiplicação D⊤X, que é a operação de maior custo computacional da classificação em tempo de teste. As bases de dados MNIST e CIFAR-10 estão descritas na Seção 4.2.
MNIST CIFAR-10
Erro % Qtd de bits D⊤X Erro % Qtd de bits D⊤X
Original 2.48 61 60.00 55
Proposto 2.52 29 53.08 29
As taxas de erros que obtive para essas bases de dados multiclasse são maiores que as apresentadas em [13]. Provavelmente, isso foi causado pela natureza aleatória do LAST para bases de dados grandes, em que cada iteração de descida do gradiente o modelo é otimizado para um subconjunto dos dados de treinamento, chamada de mini-batch. Esse subconjunto é construído de forma aleatória a cada iteração a partir dos sinais do conjunto de treinamento. Além disso, conforme descrito na Seção 4.2, usei apenas 80% do conjunto de treinamento para gerar os modelos com o LAST e isso pode ter afetado negativamente suas capacidades de generalização para novos sinais.
Conforme apresentado na Tabela4.1, as técnicas que proponho podem resultar em um pequeno aumento do erro de classificação da base de dados MNIST. Entretanto, assim como no caso das bases binárias, essas técnicas reduzem para quase metade o número de
bits necessário para a multiplicação D⊤X, que é a parte de maior custo computacional
da representação esparsa.Cabe lembrar, novamente, que isso é benéfico para operações efetuadas em hardware.
Em relação aos resultados que obtive para a base de dados CIFAR-10, as técnicas que proponho produziram um modelo com taxa de erro menor que o produzido com o modelo original usando quase metade da quantidade de bits necessária para a classificação em tempo de teste. Provavelmente, essa diferença na taxa de erro também foi causada pela natureza aleatória do LAST, conforme discutido anteriormente.
Capítulo 5
Conclusão
Apresentei neste documento um conjunto de técnicas para a redução do custo computa- cional da classificação em tempo de teste para algoritmos de classificação baseados em transformadas e limiares suaves aprendidos a partir dos dados de treinamento. Desenvolvi essas técnicas a partir de um estudo preliminar que realizei sobre a operação mais onerosa da classificação em tempo de teste, que é a extração de características. Basicamente, essa operação é um produto matriz-vetor seguido de um limiar suave. Mostrei em seguida que essas técnicas permitem utilizar operações de baixo custo computacional e também reduzir o número de bits necessário para a extração de características com uma limitada perda de acurácia.
Neste último capítulo, apresento as conclusões sobre o estudo dessas técnicas com base na análise dos resultados das experimentações que realizei. Também sumarizo as contribuições desta pesquisa e proponho algumas sugestões de trabalhos futuro relacionados com as minhas descobertas.
De forma geral, as técnicas que propus neste documento podem ser divididas em quatro grupos:
(i) Usar os sinais no mesmo formato em que são amostrados pelos conversores analógicos digitais (ADC), ou seja, representados por inteiros, em vez de reescalonados, como normalmente é feito em processos de normalização. Em hardware, especialmente
em arranjo de portas programáveis por campo (FPGA, do inglês field programmable gate array), operações em inteiros são menos custosas do que operações em ponto flutuante. Eu provo que essa troca não afeta a acurácia de classificação.
(ii) Aproximar os valores da matriz de transformação e do vetor de classificação para suas respectivas potências de 2 mais próximas. Essa aproximação permite que cada multiplicação na classificação em tempo de teste seja substituída por um único deslocamento de bit.
(iii) Quantizar os sinais a serem classificados em tempo de teste de forma a diminuir suas respectivas faixas dinâmicas e com isso diminuir a quantidade de bits necessária para se realizar a classificação.
(iv) Diminuir a faixa dinâmica da matriz de transformação utilizando duas abordagens: primeiramente, adicionando uma penalização à sua norma; em seguida, zerando as entradas dessa matriz que possuem valores abaixo de um limiar, cujo valor é aprendido a partir dos dados de treinamento.
Os resultados apresentados no Capítulo 4.4 mostram a viabilidade de se realizar a classificação de imagens em tempo de teste com operações em inteiros no lugar de operações em ponto flutuante, além de substituir cada operação de multiplicação por um simples deslocamento de bit. Essas substituições possibilitam reduzir o custo computacional da classificação em tempo de teste realizadas em FPGAs, com importância em aplicações embarcadas, cujo consumo de energia é crítico. Além disso, os modelos gerados com essas técnicas reduziram pela metade a quantidade de bits necessária para efetuar a multiplicação matriz-vetor D⊤X, que é a operação de maior custo computacional na classificação em
tempo de teste.
Também é importante notar que desenvolvi essas técnicas somente para a redução do custo computacional da classificação, com uma perda de acurácia de classificação dentro de limites aceitáveis. Entretanto, as acurácias de classificação dos modelos modificados com essas técnicas na base de dados bark versus woodgrain superaram as acurácias de
classificação do modelo original, conforme mostrado na Figura 4.4(a). Após inspecionar esses resultados, percebi que os modelos originais obtiveram acurácia de 100% no conjunto de treinamento, indicando que possivelmente eles se sobreajustaram a esse conjunto (para os casos com mais de 100 átomos). A técnica que aproxima as entradas de D e w para suas respectivas potências de dois mais próximas introduz um erro de quantização, e é possível que esse erro tenha causado um aumentado na variância desses modelos de tal forma a aumentar suas capacidades de generalização para novos sinais [25]. De qualquer forma, esse fato necessita de uma investigação mais profunda, o qual deixo como trabalho futuro. Também como trabalho futuro, é importante investigar com maior profundidade como essa técnica de aproximação para potências de dois afeta a acurácia do modelo.
Referências
[1] Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: a review and new perspectives. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(8):1798–1828, August 2013. 12, 49
[2] Sergio Bernabe, Sebastián Lopez, Antonio Plaza, and Roberto Sarmiento. GPU Implementation of an Automatic Target Detection and Classification Algorithm for Hyperspectral Image Analysis. IEEE Geoscience and Remote Sensing Letters, 10:221–225, March 2013. 3
[3] Stephen P Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, March 2004. 6, 11, 31,32, 33, 34,36, 37, 38, 40
[4] Tom M Bruintjes. Design of a fused multiply-add floating-point and integer datapath. 2011. 27
[5] Ben Cope, Peter YK Cheung, Wayne Luk, and Lee Howes. Performance comparison of graphics processors to reconfigurable logic: a case study. Computers, IEEE Transactions on, 59(4):433–448, 2010. 4
[6] Sanjoy Dasgupta. Experiments with Random Projection. arXiv.org, cs.LG, January 2013. 11
[7] Kevin K Dobbin and Richard M Simon. Optimally splitting cases for training and testing high dimensional classifiers. BMC medical genomics, 4:31, 2011. 48
[8] Pedro Domingos. A few useful things to know about machine learning. Communicati- ons of the ACM, 55(10):78–87, 2012. 4, 9, 10, 11
[9] David L Donoho and Iain M Johnstone. Ideal spatial adaptation by wavelet shrinkage. Biometrika Trust, 81:425–455, 1994. 1, 18
[10] George H Dunteman. Principal components analysis. Sage, 1989. 11
[11] Michael Elad and Michal Aharon. Image denoising via sparse and redundant re- presentations over learned dictionaries. Image Processing, IEEE Transactions on, 15(12):3736–3745, 2006. 12
[12] Alexander Fabisch, Yohannes Kassahun, Hendrik Wöhrle, and Frank Kirchner. Lear- ning in compressed space. Neural networks : the official journal of the International Neural Network Society, 42C:83–93, February 2013. 4
[13] Alhussein Fawzi, Mike Davies, and Pascal Frossard. Dictionary Learning for Fast Classification Based on Soft-thresholding. International Journal of Computer Vision, pages 1–16, November 2014. 4, 6, 13, 17, 19, 20, 22, 23, 31, 33, 35, 40, 44, 45, 46, 47,
51
[14] A Ganesh, S S Sastry, and Y Ma. Robust Face Recognition via Sparse Representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009. 13
[15] X Glorot, A Bordes, and Y Bengio. Deep Sparse Rectifier Neural Networks. In Proce- edings of the 14th International Conference on Artificial Intelligence and Statistics, pages 315–323, 2011. 19
[16] Guang-Bin Huang, Qin-Yu Zhu, and Chee-Kheong Siew. Extreme learning machine: theory and applications. Neurocomputing, 70(1):489–501, 2006. 3
[17] Deepak Khosla, Yang Chen, David J Huber, Darrel J Van Buer, Kyungnam Kim, and Shinko Y Cheng. Real-time, low power neuromorphic hardware for autonomous object recognition. In Proceedings of the SPIE, pages 871313–871313. HRL Labs., LLC. (United States), 2013. 3
[18] Alex Krizhevsky. Learning multiple layers of features from tiny images. Computer Science Department, University of Toronto, 2009. 45, 46
[19] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. ImageNet Classification with Deep Convolutional Neural Networks. Advances in neural information processing systems, pages 1097–1105, 2012. 3
[20] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE. Institute of Electrical and Electronics Engineers, 86(11):2278–2324, 1998. 46
[21] Andrew L Maas, Awni Y Hannun, and Andrew Y Ng. Rectifier nonlinearities improve neural network acoustic models. In Proc. ICML, 2013. 19
[22] J Mairal, F Bach, and J Ponce. Task-Driven Dictionary Learning. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 34(4):791–804, April 2012. 4,12,13
[23] Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pages 807–814, 2010. 19
[24] Jorge Nocedal and Stephen J Wright. Numerical optimization, volume 2. Springer, 2006. 6, 11,32, 36
[25] Bernhard Pfahringer. Compression-Based Discretization of Continuous Attributes. In Proc. 12th International Conference on Machine Learning, pages 456–463. unknown, 1995. 55
[26] J L Raheja, B Ajay, and Ankit Chaudhary. Real Time Fabric Defect Detection System on an Embedded DSP Platform. arXiv.org, cs.CV:–, September 2014. 3
[27] Saiprasad Ravishankar and Yoram Bresler. Learning Sparsifying Transforms. IEEE Transactions on Signal Processing, 61(5):1072–1086, January 2013. 1,4, 17, 31
[28] DAILY MAIL REPORTER. Google uses MORE power than Salt Lake City as vast data farms suck up electricity, September 2011. 2
[29] Jürgen Schmidhuber. Deep learning in neural networks: An overview. Neural networks : the official journal of the International Neural Network Society, 61:85–117, January 2015. 3
[30] Adriana Schulz, Eduardo Antônio Barros Da Silva, and Luiz Velho. Compressive sensing. IMPA, 2009. 13
[31] Sumit Shekhar, Vishal M Patel, and Rama Chellappa. Analysis sparse coding models for image-based classification. In IEEE International Conference on Image Processing. Proceedings, 2014. 4, 17
[32] Mohammed Shoaib, Niraj K Jha, and Naveen Verma. Signal Processing With Direct Computations on Compressively Sensed Data. Schölkopf, B, (99), February 2014. 5,
20
[33] Steven W Smith. The scientist and engineer’s guide to digital signal processing. California Technical Pub. San Diego, December 1997. 4
[34] K Valkealahti and E Oja. Reduced multidimensional co-occurrence histograms in tex- ture classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20(1):90–94, 1998. 22,23, 44, 45
[35] Rosa M Ventura, Pierre Vandergheynst, and Pascal Frossard. Low-rate and flexible image coding with redundant representations. Image Processing, IEEE Transactions on, 15(3):726–739, 2006. 12
[36] Zhen James Xiang, Hao Xu, and Peter J Ramadge. Learning sparse representations of high dimensional data on large scale dictionaries. Advances in neural information processing systems, 24:900–908, 2011. 35
[37] Matthew D Zeiler, M Ranzato, Rajat Monga, M Mao, K Yang, Quoc Viet Le, Patrick Nguyen, A Senior, Vincent Vanhoucke, Jeffrey Dean, and others. On rectified linear units for speech processing. In Acoustics, Speech and Signal Processing (ICASSP), 2013 IEEE International Conference on, pages 3517–3521. IEEE, 2013. 19