Neural Network Learning by the Levenberg-Marquardt Algorithm with Bayesian Regularization (part 2)

lm-apprx-1_thumb-5B2-5D

A complete explanation for the totally lost, part 2 of 2. Click here to return to part 1.

Downloads

The code has been incorporated in Accord.NET Framework, which includes the latest version of this code plus many other statistics and machine learning tools.

Contents

  1. Overview
    1. Neural Networks
    2. AForge Framework
    3. Network training as a function optimization problem
  2. Levenberg-Marquardt
    1. Computing the Jacobian
    2. Approximating the Hessian
    3. Solving the Levenberg-Marquardt equation
    4. General Algorithm
    5. Limitations
  3. Bayesian Regularization
    1. Expanded Levenberg-Marquardt Algorithm
  4. Source Code
    1. Using the Code
    2. Sample Applications
  5. Additional Notes
  6. References

Bayesian Regularization

To overcome the problem in interpolating noisy data, MacKay (1992) has proposed a Bayesian framework which can be directly applied to the neural network learning problem. It also allows to estimate the effective number of parameters actually used by the model – in this case, the number of network weights actually needed to solve a particular problem.
Bayesian regularization expands the cost function to search not only for the minimal error, but for the minimal error using the minimal weights. It works by introducing two Bayesian hyperparameters, alpha and beta, to tell which direction (minimal error or minimal weights) the learning process must seek.
The cost function will then become:

C(k) = β*Ed+α*Ew, where:

  1. Ed is the sum of squared errors, and
  2. Ew is the sum of squared weights

By using Bayesian regularization, one can avoid costly cross validation. It is particularly useful to problems that can not, or would suffer, if a portion of the available data were reserved to a validation set. Regularization also reduces (or eliminates) the need for testing different number of hidden neurons for a problem. A third variable, gamma, indicates the number of effective weights being used by the network, thus giving an indication on how complex the network should be.
Many practical realizations of Bayesian Regularization perform an update of the hyperparameters alpha and beta after each training cycle. However, according to Poland (2001) the most popular update algorithm fails to produce robust iterates if there is not much training data. The following algorithm shows how to update the hyperparameters according to both rules. Both methods base their calculations in the inverse Hessian matrix.

Expanded Levenberg-Marquardt Algorithm

Adding bayesian regularization to the Levenberg-Marquardt adds little overhead to the process because we already have an Hessian approximation. So, the algorithm for a learning epoch then becomes:

  1. Compute the Jacobian (by finite differences or using the chain rule)
  2. Compute the error gradient
    • g = JtE
  3. Approximate the Hessian using the cross product Jacobian
    1. H = JtJ
  4. Calculate the cost function
    1. C = β*Ed+α*Ew, where:
      1. Ed is the sum of squared errors, and
      2. Ew is the sum of squared weights
  5. Solve (H + λI)δ = g to find δ
  6. Update the network weights w using δ
  7. Recalculate the cost function using the updated weights
  8. If the cost has not decreased,
    1. Discard the new weights, increase λ using v and go to step 5.
  9. Else decrease λ using v
  10. Update the Bayesian hyperparameters using MacKay’s or Poland’s formulae:
    1. gamma = W – (alpha * tr(H-1))
    2. beta = (N – gamma) / 2.0 * Ed
    3. alpha = W / (2.0 * Ew + tr(H-1)) [modified Poland’s update], or
    4. alpha = gamma / (2.0 * Ew) [original MacKay’s update], where:
      1. W is the number of network parameters (number of weights and biases)
      2. N is the number of entries in the training set
      3. tr(H-1) is the trace of the inverse Hessian matrix

Source Code

Here is the code for running a learning epoch of the Levenberg-Marquardt algorithm.

Using the Code

Code usage is very simple. It follows the common AForge.NET learning algorithm usage, instantiating a LevenbergMarquardtLearning class instead of the more traditional BackpropagationLearning. Optionally, we may opt for using the Jacobian approximated by finite differences instead of computing it directly (although it would not be very practical unless for debugging purposes). We may also enable bayesian regularization by passing a boolean parameter to the constructor.

Sample applications

The original sample applications from AForge.NET have been modified to use Levenberg-Marquardt learning. However, it is quite tricky to get them to converge adequately.

lm-apprx-1 lm-apprx-2
Function approximation using regular Levenberg-Marquardt

lm-apprx-3-br lm-apprx-3-nw lm-apprx-4-br lm-apprx-5-br lm-apprx-6-br
Function approximation using the Levenberg-Marquardt with Bayesian regularization. Note that some of them does not converge to a best fit solution; instead, a possibly more general solution is preferred. The top-right image uses the Nguyen-Widrow method for initializing weights.

lm-xor-1
Solving the XOR problem using Levenberg-Marquardt

Additional Notes

Some versions of the Levenberg-Marquardt algorithm solve the equation (JtJ + λ diag(JtJ) I)δ = JtE instead of  (JtJ + λI)δ = JtE, effectively replacing the identity matrix with the diagonal of the approximated Hessian for the weight update rule. According to Wikipedia, this was suggested by Marquardt to incorporate some local curvature estimation. However, for some reason, more recent implementations that use the Levenberg-Marquardt tag do not include Marquardt’s suggestion. Other implementations suggest using an initial λ related to the size of the elements of the approximated Hessian by making λ0 = t max(diag(JtJ)), where t is a value chosen by the user.
It is also important to note that the Levenberg-Marquardt is extremely dependent on the initial guess for the network parameters. Depending on the initial weights of the network, the algorithm may converge to a local minima or not converge at all.
Besides that, it is an extremely fast method for neural network learning when compared to the standard backpropagation algorithm.

Finally, if you have any comments about the article or about the code, please let me know it! All suggestions are welcome.

References

Análise de Componente Principal em C#

input_thumb-5B2-5D

For the english version, Principal Component Analysis in C#, click this link.

A Análise de Componente Principal (PCA) é uma ferramenta exploratória criada por Karl Pearson em 1901 para identificar tendencias desconhecidas em um conjunto de dados multidimensional. A análise envolve um procedimento matemático que transforma um conjunto de variaveis possivelmente correlatas em um grupo menor de variaveis incorrelatas de denominadas componentes principais. Os primeiros componentes principais correspondem a maior variabilidade possivel contida nos dados, enquanto os componentes posteriores correspondem ao restante da informacao, em ordem decrescente de variabilidade.

Visão Geral

A técnica PCA essencialmente rotaciona o conjunto de pontos ao redor de sua média objetivando seu alinhamento com os primeiros componentes principais. Isto move a maior parte da variancia possivel (usando uma transformação linear) para as primeiras dimensões. Os valores nas dimensoes restantes, portanto, tendem a ser altamente correlacionados e podem ser ignorados com perda mínima de informação.

Para uma explicação mais detalhada sobre PCA, leia o excelente texto Tutorial On Principal Component Analysis, por Lindsay Smith (2002).

 

AForge.NET Framework

Minha idéia inicial era implementar a PCA internamente no AForge.NET Framework. O AForge.NET é um excelente framework de Inteligência Artificial e Visão Computacional de código aberto escrito para .NET e desenvolvido principalmente por Andrew Kirillov.

No entanto, como isto envolveria muitas mudanças e adições ao framework, acredito que seria muito difícil rever todas mudanças requeridas para adicionar esta funcionalidade diretamente em seu código fonte.

Devido a isso, este novo, e mais limpo, código, foi implementado usando somente os binários do AForge como ponto de partida. Espero que este código ajude outros precisando realizar a Análise de Componente Principal em seus próprios projetos em C#.

 

Esta nova biblioteca, a que chamei de Accord.NET, extende o AForge.NET adicionando novas features como a Principal Component Analysis, decomposições numéricas e algumas outras poucas transformações matemáticas e ferramentas. Na verdade, esta extensão é muito mais como um campo de teste para novas features que eu gostaria de ver em versões futuras do AForge. Mas para maior simplicidade, omiti as partes não relacionadas com PCA e criei esta versão compacta apenas para suportar a análise.

 

Decisões de Implementação

Como pessoas que querem utilizar PCA em seus projetos geralmente já tem suas próprias classes de matrizes, decidi evitar usar implementações específicas para tornar o código mais flexível. Também tentei evitar dependencias em outros métodos sempre que possível, para tornar o código bastante independente. Acredito que isto também tenha tornado o código mais simples de se entender.

O código está dividido entre estes dois projetos:

  • Accord.Math, que fornece as ferramentas matemáticas, como decomposições e transfomações; e
  • Accord.Statistics, que fornece análises e ferramentas estatísticas.

Ambos dependem do núcleo do AForge.NET. Adicionalmente, sua estrutura e organização interna também tenta similar ao máximo a empregada no AForge sempre que possível.

 

O código fonte fornecido não inclui o código fonte na íntegra do Accord Framework, que permanece como um framework de testes do que seria interessante ver no AForge, mas inclui somente porções limitadas do código necessárias para suportar PCA.

 

Visão Geral do Código

Below is the main code behind the PCA.

 

Usando o Código

Para realizar uma análise simples, você pode simplesmente instanciar um novo objeto PrincipalComponentAnalysis passando seu conjunto de dados e chamar seu método Compute para computar o modelo. Então você pode simplesmente chamar o método Transform para projetar os dados no espaço dos componentes principais.

Abaixo está um exemplo de código demonstrando seu uso.

 

Demonstração

Para demonstrar o uso da Análise de Componente Principal, criei uma simples aplicação Windows Forms que efetua uma análise de dados simples e as transformações PCA em planilhas Excel.

input
The application can open Excel workbooks. Here we are loading some random Gaussian data, some random Poisson data, and a linear multiplication of the first variable (thus also being Gaussian).
 
univariate
Simple descriptive analysis of the source data, with a histogram plot of the first variable. We can see it fits a Gaussian distribution with 1.0 mean and 1.0 standard deviation.
 
principal
Here we perform PCA by using the Correlation method (actually the transformation uses SVD on the standardized data, not the correlation matrix, but the effect is the same). Because the third variable is a linear multiplication of the first, the analysis detected it was totally irrelevant, thus having zero importance level.
 
projection
Now we can make a projection of the source data using only the first two components.
 

 

Nota: Os componentes principais não são únicos porque a decomposição em valor singular não é única. Além do mais, os sinais na matriz de rotação são arbitrários, e portanto podem difererir entre diferentes programas para PCA.

junto com a aplicação de demonstração vem uma planilha Excel contendo vários exemplos de dados. O primeiro exemplo é o mesmo utilizado por Lindsay em seu Tutorial on Principal Component Analysis. Outros exemplos incluem dados Gaussianos, dados não correlacionados e combinações lineares de dados Gaussianos para exemplificar melhor a análise.

 

Bem, novamente, espero que alguém ache este código útil! 😛

Principal Component Analysis in C#

Principal Component Analysis (PCA) is an exploratory tool designed by Karl Pearson in 1901 to identify unknown trends in a multidimensional data set. It involves a mathematical procedure that transforms a number of possibly correlated variables into a smaller number of uncorrelated variables called principal components.

Foreword

Before you read this article, please keep in mind that it was written before the Accord.NET Framework was created and became popular. As such, if you would like to do Principal Component Analysis in your projects, download the accord-net framework from NuGet and either follow the starting guide or download the PCA sample application from the sample gallery in order to get up and running quickly with the framework.

Introduction

PCA essentially rotates the set of points around their mean in order to align with the first few principal components. This moves as much of the variance as possible (using a linear transformation) into the first few dimensions. The values in the remaining dimensions, therefore, tend to be highly correlated and may be dropped with minimal loss of information. Please note that the signs of the columns of the rotation matrix are arbitrary, and so may differ between different programs for PCA.

For a more complete explanation for PCA, please visit Lindsay Smith excellent Tutorial On Principal Component Analysis (2002).

Accord.NET Framework

This new library, which I called Accord.NET, was initially intended to extend the AForge.NET Framework through the addition of new features such as Principal Component Analysis, numerical decompositions, and a few other mathematical transformations and tools. However, the library I created grew larger than the original framework I was trying to extend. In a few months, both libraries will merge under Accord.NET. (Update April 2015)

Design decisions

As people who want to use PCA in their projects usually already have their own Matrix classes definitions, I decided to avoid using custom Matrix and Vector classes in order to make the code more flexible. I also tried to avoid dependencies on other methods whenever possible, to make the code very independent. I think this also made the code simpler to understand.

The code is divided into two projects:

  • Accord.Math, which provides mathematical tools, decompositions and transformations, and
  • Accord.Statistics, which provides the statistical analysis, statistical tools and visualizations.

Both of them depends on the AForge.NET core. Also, their internal structure and organization tries to mimic AForge’s wherever possible.

The given source code doesn’t include the full source of the Accord Framework, which remains as a test bed for new features I’d like to see in AForge.NET. Rather, it includes only limited portions of the code to support PCA. It also contains code for Kernel Principal Component Analysis, as both share the same framework. Please be sure to look for the correct project when testing.

Code overview

Below is the main code behind PCA.

Using the code

To perform a simple analysis, you can simple instantiate a new PrincipalComponentAnalysis object passing your data and call its Compute method to compute the model. Then you can simply call the Transform method to project the data into the principal component space.

A sample sample code demonstrating its usage is presented below.

Example application

To demonstrate the use of PCA, I created a simple Windows Forms Application which performs simple statistical analysis and PCA transformations.

input_thumb-5B2-5D

The application can open Excel workbooks. Here we are loading some random Gaussian data, some random Poisson data, and a linear multiplication of the first variable (thus also being Gaussian).
 
univariate_thumb-5B4-5D
Simple descriptive analysis of the source data, with a histogram plot of the first variable. We can see it fits a Gaussian distribution with 1.0 mean and 1.0 standard deviation.
 
principal_thumb-5B9-5D
Here we perform PCA by using the Correlation method. Actually, the transformation uses SVD on the standardized data rather than on the correlation matrix, the effect being the same. As the third variable is a linear multiplication of the first, the analysis detected it as irrelevant, thus having a zero importance level.
 
projection_thumb-5B4-5D
Now we can make a projection of the source data using only the first two components.
 

 

Note: The principal components are not unique because the Singular Value Decomposition is not unique. Also the signs of the columns of the rotation matrix are arbitrary, and so may differ between different programs for PCA.

Together with the demo application comes an Excel spreadsheet containing several data examples. The first example is the same used by Lindsay on his Tutorial on Principal Component Analysis. The others include Gaussian data, uncorrelated data and linear combinations of Gaussian data to further exemplify the analysis.

I hope this code and example can be useful! If you have any comments about the code or the article, please let me know.

See also

A Tutorial On Principal Component Analysis with the Accord.NET Framework

This is a tutorial for those who are interested in learning how PCA works and how each step of Lindsay’s tutorial can be computed in the Accord.NET Framework, in C#.

Kernel Principal Component Analysis in C#

This is the non-linear extension of Principal Component Analysis. While linear PCA is restricted to rotating or scaling the data, kernel PCA can do arbitrary transformations (such as folding and twisting the data and the space that contains the data).

IX Congresso Brasileiro de Redes Neurais e Inteligência Computacional

Hoje foi o terceiro dia (propriamente dito) do IX Congresso Brasileiro de Redes Neurais e Inteligência Computacional (CBRN 2009), sendo realizado aqui em Ouro Preto.

Neste mesmo dia, apresentei o meu singelo trabalho de graduação entre tantos outros trabalhos de mestrado e doutorado. E graças a Deus, tudo deu certo!

E além disto, o melhor de tudo foi ter a oportunidade de assistir a trabalhos muito interessantes apresentados nessa conferência. A começar pelo trabalho da primeira sessão plenária, muito bem elaborado e muito, muito bem apresentado.

Os trabalhos que assisti e que mais me chamaram a atenção foram:

Redes Neurais sob Criterios de Entropia: Previsão de Potência Eólica e Outras Aplicações

Ao invés de minimizar os erros, o autor minimiza a entropia dos erros das redes neurais. Muito genial, pois evita que erros de medição contaminem o aprendizado. Professor Vladimiro Miranda, INESC Porto.

Analise de Desempenho de Cursos de Pós-Graduação Utilizando Mapas Auto-Organizáveis Parciais

Mostra o como podemos analisar o conceito CAPES de diversas maneiras para ter uma visão melhor sobre a pós-graduação no país. Muito interessante observar os resultados graficamente! Flavius da L. Gorgônio, José A. F. Costa

Uma Interface Humano-Máquina Inteligente Baseada no Rastreamento Ocular para comunicação Escrita de Pacientes com Síndrome Locked-In

A construção de um sistema de comunicação pra pessoas com paralisia total em que a única forma de comunicação seja o movimento e piscar de olhos. Graduação. Amanda L. Nascimento, Fernando B. L. Neto, Sérgio C. Oliveira, Hugo S. B. Filho

E também o meu, é claro 😛

Avaliação Prognóstica de Complicações Pós-Operatórias em Pacientes Submetidos à Cirurgia de Revascularização do Miocárdio

Uma investigação de aplicabilidade de redes neurais no problema específico do prognóstico de complicações pós-operatórias desta cirurgia cardíaca, utilizando análise de componente principal, regularização bayesiana e curvas ROC. Graduação. César Roberto de Souza, Ednaldo B. Pizzolato, Renata Mendes, Audrey B. Silva, Maurício Machado, Paulo Correa

Recebi algumas sugestões de como melhorar a pesquisa. Afinal, a apresentação foi produtiva!

MATLAB ANN’s: Disabling Validation Checks

Just in case you are trying to train your MATLAB neural network for a indefinite amount of time, and your training keeps stopping when “validation checks” reaches 6, just set your validation set division function to be an empty string. Example:

ann = newff(inputs,outputs,100,{},’trainbr’);
ann.divideFcn = ”;
ann = train(ann,inputs,outputs);

That should do the trick.

getToken(); Compilador de Portugol em JavaScript

logo-big

Durante a disciplina de Construção de Compiladores II, temos a oportunidade de trabalhar em um compilador para uma linguagem de programação hipotética a ser implementado em (praticamente) qualquer linguagem que se queira – só não valendo Shakespeare e afins.

Como tínhamos muito pouca experiência com Javascript, decidimos encarar o desafio e comecar a desenvolver nosso compilador para rodar em um ambiente totalmente web.

 

Pois bem; aqui está a primeira versão do getToken(), nosso compilador de pseudo-linguagem que mais lembra uma mistura de pascal com portugol!

 

[ getToken(); – JavaScript-Based Hypothetical Programming Language Compiler ]

 

Bom, é verdade que por enquanto estamos ainda na fase de análise léxica e a única coisa que o programa pode fazer é separar o código em tokens, mas mesmo assim, acho que o negócio está ficando bonitinho ;P

Convertendo profundidade em audio em C#

Este post é uma tradução do post original anterior, Converting Audio Bit Depths in C#, em inglês

Sinais de áudio digitais podem ser armazenados em muitos tipos de formatos diferentes. Por exemplo, um sinal de áudio poderia ser armazenado como um sinal PCM de 16-bits dentro de um arquivo WAVE ou codificado em um formato com perdas como o MP3. Mas em todos os casos, todos sinais digitais são representados como uma sequência de valores, denominadas amostras, as quais são resultado da mensuração de uma determinada característica do som em função do tempo, para que possam ser manipuladas digitalmente.

Amostras (ou samples) formam um sinal discreto (digital) tipicamente originado de um sinal contínuo (analógico, como as ondas sonoras), obtido através de algum tipo de procedimento ou algorítmo de conversão (de amostragem). Assim existem, portanto, muitas maneiras de se representar uma amostra, como com bytes de 8-bits, inteiros de 32-bits ou números de ponto flutuante (floats) de 32-bits. E, por vezes, a conversão entre estes vários tipos de representações são um requerimento inicial em diversas aplicações.

Convertendo entre diferentes representações de amostras de áudio em C#

Para converter entre diferentes representações de amostras, além de modificar o tipo de dado (sua profundidade em bits) ainda é preciso adequar nossas amostras em uma nova escala. Por exemplo, para converter de um float de 32-bits para um unsigned byte de 8-bits, nós temos que transportar a amostra original de seu intervalo de [-1;1] para seu novo intervalo de [0;255].

Para realizar este processo, a classe a seguir contém um único (exaustivamente sobrecarregado) método que permite converter, por exemplo, amostras de 16-bit para 8-bit, 16-bit para float, float para 16-bit, entre outros. De fato, são possíveis conversões entre quaisquer um dos seguintes tipos: unsigned 8-bit bytes, signed 16-bit integers, signed 32-bit integers e 32-bit floating point single precision numbers. Espero que o código seguinte seja útil a alguem que esteja interessado!

Considerações

Note, porém, que conversões raramente são perfeitas. Isto é verdade para quase tudo, especialmente para sinais digitais. Converter de uma codifiação para outra pode introduzir erros de conversão nos dados. Para ajudar nesta questão, foi inventada a técnica conhecida como dithering. Dithering é o mesmo que propositalmente adicionar ruído num sinal.

Ruído? Sim, ruído. Ruído não é sempre uma coisa ruim. Basta dar uma olhada nos exemplos de imagens na Wikipedia e você logo entenderá isto. Infelizmente, esta classe ainda não suporta dithering, poderá suportar no futuro caso surja necessidade.

Até mais!

Voce se considera um bom programador?

bug

Você se considera um bom programador? Se respondeu sim a esta pergunta, então aposto que não vai deixar este bug passar despercebido:

E ai, vê alguma coisa?

 

Óbvio não?

 

 

Dica: olhe atentamente para a linha 6:

Ainda não percebeu? Então digamos, o que acontece, se, por acaso, low valer 10 e high valer 2.147.483.647 (ou seja, 2^31-1, o valor máximo que um inteiro de 32 bits pode possuir)?

Overflow!

Sim, de fato, a maioria das implementações de busca binária possui este erro. Não apenas livros, apostilas e materiais didáticos, mas sistemas críticos de produção também. Mas ai você fala: Ahh mas eu nunca vou empregar este tipo de busca em algo tão grande! – Bom, talvez não, mas não se esqueça que este é o mecanismo chave de muitos outros algoritmos de divisão-e-conquista, como, por exemplo, o mergesort.

 

Mais do que isto, esta observação serve para elucidar o quão é difícil garantir a corretude de um software. Demoraram 16 anos para detectar um erro no algoritmo que é, provavelmente, o mais popular de toda computação, presente em virtualmente todos os livros da área. Pois é: Planejamento cuidadoso é uma bênção, testar é uma maravilha. Utilizar métodos formais, melhor ainda. Revisão de código e análise estatística? Impossível ainda restar algum bug! Errado! Nenhuma destas coisas são suficientes para eliminarmos todos os bugs de um software. A verdade é: Eles sempre vão estar presentes e nos acompanhar por toda nossa vida :~

 

Ah, a correção? Simplesmente mude a linha 6 para:

Mágica.

 

[Fonte: Official Google Research Blog]

Converting audio bit depths in C#

Para a versão em português deste post, clique aqui.

Digital audio signals can be stored in a myriad of different formats. For example, digital audio could be stored as a raw 16-bit PCM signal buried inside a WAVE file or as an encoded lossy format such as MP3. But invariably most digital signals are represented by a sequence of values, called samples, which are the measurement of a choosen sound characteristic over time, so they can be manipulated digitally.

Samples are a discrete-time (digital) signal tipically originated from a continous (analog, such as sound waves) signal through some kind of conversion procedure or algorithm. There is, however, many ways to represent a sample, such as a 8-bit byte, a 32-bit integer or a 32-bit float. And sometimes converting between those different representations (performing some kind of resampling) is an requirement in many applications.

Converting between different sample bit depths in C#

To convert between different sample representations, besides changing the data type we also have to rescale our samples. To convert from 32-bit float to 8-bit unsigned byte, for example, we have to rescale the original sample from its [-1;1] interval to a unsigned, [0;255] interval. The class below has a single (heavily overloaded) method suitable to convert, for example, 16-bit to 8-bit, 16-bit to float, float to 16-bit, and so on. In fact, it can convert in between unsigned 8-bit bytes, signed 16-bit integers, signed 32-bit integers and 32-bit floating point single precision numbers. I hope someone finds it useful!