Re: [Neurostat-develop] first ideas...

[Joseph]

> I also would like to consider our library to be usable without R, for instance
> as an add-on component to GSL. That's why I think we should focus on very low
> level primitives: calculation of the output and of the differentials of an
> MLP. I don't think it's a good idea to provide more, because everything else
> needed, especially optimization algorithms, should be provided by the
> environement (for instance R or GSL). It would be better for us to contribute
> missing bits to GSL and to R rather than to integrate them in our library.
> 

Y agree, we can do a general "C" library and adapt one version  to match
with the "R" packages style.
Moreover even for the "R" library it would be a good idea to use GSL
code like random generator, or differential optimization.


> 
> We have a problem here, for several reasons:


 I don't think so.

> 1) With dense matrices, we can use efficient BLAS implementations (ATLAS seems
> to give quite good results compared to vendor optimized BLAS). There is a
> sparseblas on netlib (in fortran), but I don't think it is close to the
> optimization level of ATLAS (authors of ATLAS plan to work on sparse matrices,
> but it is not the case right now, I think).


generally, the size of the matrices is not really huge (100x100 is the
maximum), so the use of optimized library is not so critic. In my
experience with my C++ program interfaced with BLAS, if an optimization
task takes 5 minutes with the Intel optimized BLAS routine, it takes
about 8 minutes with the netlib BLAS and 6 minutes with ATLAS. So, the
gain of speed is just between 30% to 40%, it's not a big deal.
MLP are not used for real time task and it doesn't really matter to wait
8 minutes instead of 5 minutes. 

I don't think that we need to use the very general sparse netlib
library, we can implement only three or four BLAS-operations one a
particular sparse-architecture (see bellow). 




> 
> 2) When the number of holes is small, the simplest way to store and to
> calculate with corresponding matrices is to use a dense representation. The
> main problem is that we have to force the learning algorithm to keep missing
> weights to zero. It is easy to replace real partial differential of the error
> with respect to a constant weight by zero. Conjugate gradient like algorithms
> are linear (ie the descent direction is a linear function of the previous
> direction and of the gradient) and therefore they should work with this scheme
> quite easily. But other algorithms will need a specific support.
> 
> 3) In general, if we want to use optimization algorithms, we need to rely on a
> flat representation of the numerical parameters of the MLP (a "vector"). I
> don't know many things about sparse matrices and so I wonder how this
> requierement can be achieved.
> 

In fact the problem evocated is the main reason to use sparse matrices,
because the representation of the coefficients in a sparse matrix is
flat!! 

Indeed, we have essentially the choice between the compressed column
storage or compressed row storage (see  SparseLib++ v.1.5. Sparse Matrix
Class Library, Reference Guide, / R. Pozo, K.A. Remington  April 1996,
http://math.nist.gov/sparselib++/).

With these representations,  the parameters are inevitably stored in a
"flat" vector but are also  "compressed" (without zero).

By the way you can represent the weights of the MLP in a flat vector,
without zeros, and construct the sparse matrices and vectors
representing the architecture of the MLP using  (double *) pointers on
the (good) coordinates of this vector. 


> That's right, but the design must be compatible with future optimization.

This design is compatible with further optimization in the same way that
we can use NETLIB BLAS then  switch to INTEL BLAS, because you can
optimize the 3 or 4 operations needed  later (essentially
matrices*vectors multiplications).



> 
> I propose to start working on a prototype C API as a discussion support. I
> will try to post something before Xmas.



I will try to post a example of this (reduced) sparse-library before
Xmas too. 


Joseph