Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Time complexity of neural network

Asked by David on 29 Dec 2012

Matlab use many training algos, like LM, CG, SD etc for ANN training. I am searching for the time complexity for LM & CG based ANN implementation in Matlab. specificly, What is the time complexity of LM & CG method implementd in Matlab. Are they faster than O(n3).

Thanks in advance for your help.

0 Comments

David

Products

No products are associated with this question.

2 Answers

Answer by Matt J on 30 Dec 2012
Edited by Matt J on 30 Dec 2012

As a disclaimer, I have no background in neural networks. I do have some background in function optimization, though, and I think I can confidently say,

  1. The time complexity will depend on the structure of your network, i.e., how densely things are interconnected. If connections are sparse, then sparse math can be used for the gradient computations, etc... leading to reduced complexity.
  2. In general, the worst case complexity won't be better than O(N^3). LM requires the solution of an NxN system of equations in every iteration, which can be O(N^3). CG can require O(N^2) for each gradient computation per iteration and N iterations to converge for a total of O(N^3). These are worst case bounds, of course, and might not reflect what you see in practice.

5 Comments

David on 5 Jan 2013

Thanks for answers.

I know that NN solutions depend on network architecture. Also research papers are availlable, where NN with back progagation has implemented in O(N) with more storage (IJNS). I am intrested in knowing how Matlab programmer coded these algos and with what complexity.

Matt J on 5 Jan 2013

Since this information isn't given in the documentation, it stands to reason that TMW doesn't want the internal details of the code exposed.

However, you could test the complexity yourself just by running examples with increasing N and plotting the trend in the computation time as a function of N.

Greg Heath on 5 Jan 2013

The current version of the source code is hard to decipher

type trainlm

Although obsolete versions of the code may be easier to understand, they may not be relevant re what the new code does.

Matt J
Answer by Greg Heath on 5 Jan 2013
Edited by Greg Heath on 5 Jan 2013

It depends on the network efficiency settings that control the speed/storage tradeoff

For example, the current algorithms for regression and classification are FITNET and PATTERNNET, respectively. BOTH call FEEDFORWARDNET.

The default settings are 1 but can be overwritten.

net = feedforwardnet;

% To verify unity defaults

efficiency = net.efficiency

cacheDelayedInputs = net.efficiency.cacheDelayedInputs

flattentime = net.efficiency.flattenTime

memoryReduction = net.efficiency.memoryReduction

% To overide defaults

net.efficiency.cacheDelayedInputs = cacheDelayedInputs0;

net.efficiency.flattenTime = flattentime0;

net.efficiency.memoryReduction = memoryReduction0;

Search the newsgroup and answers using

neural speed memory

http://www.mathworks.com/matlabcentral/answers/57414-problem-in-using-neural-network-toolbox

http://www.mathworks.com/matlabcentral/answers/137-how-do-i-improve-my-neural-network-performance

http://www.mathworks.com/matlabcentral/answers/11964-why-better-hardware-performance-doesn-t-speed-up-matlab-programs

Hope this helps.

Thank you for formally accepting my answer.

Greg

0 Comments

Greg Heath

Contact us