I need to calculate the desired output weights (Wout) which are the linear regression weights of the desired outputs d(n) (a vector) on the input states vector x(n). How can I get binary weights? Is there any mathematical theory to address this problem?
Thanks for your quick reply Peter. By "binary", I mean "taking the values 0 or 1 only". Would you please give me some more explanation for "mixed integer optimization problem"?
:)) Thank you. Although It seems to be vary helpful, I am looking for a concrete mathematical solution like what we have for solving linear regression problem (e.g., Tikhonov regularization).
Dear Peter, Yes exactly! By linear regression, I mean if I have N n-dimensional data vectors x_i assembled row-wise in a data collection matrix M of size n*N, and a target vector, t, of size N, the task to find weights W which minimize the square error:
SE(W)=square(||WM_transpose-t_transpose||)
Now, I would like to have a W matrix which only includes 0 and 1.
On second thought, Yes, as you correctly mentioned, my problem is exactly to minimize |MTw-t| for 0
Hello dear friend!
It's nice to hear from you again.
The problem is similar to perceptron rule of learning with the difference in the constraint; while the latter requires binary outputs.The concept in perceptron is that the undesired outputs are subject to change (ie. 0 to 1 or vise versa). So the weights connecting to them are changed in the (one of two possible) direction(s) to satisfy the desired answer.
However In your case, where the weights are restricted to 0 & 1, the problem transforms into whether a weight should contribute to a specific component (in the output space) or not. As mentioned by Peter, there is no closed formula, but learning algorithms are applied to iteratively reduce a cost function. Hence a cost function with mean squared error in accordance with the constraints in the problem (binary Ws) can be what you want.
If you take a look at the perceptron rule for binary output networks, I think the idea would be insightful.
@Peter Breuer:
Dear Peter,
Regarding your incisive replies, I noticed that my problem is exactly 0-1 integer linear programming and is one of the 21 Karp's NP- Complete problem list.
It helped me a lot in my hardware implementation problem.
I appreciate you again.
@ Peter Breuer:
When computational algorithms come to hardware implementation, low bit precision is always a challenge. In particular, in hardware implementation of either deep or shallow neural network. using just two (binary) or three (ternary) values for weights by projecting them via a quantization function seems to be a potential solution.
Currently, I am working on echo state network in which the read out weights are trained by a simple linear regression. As I realized that binarizing linear regression is an NP- complete problem, I let it alone and am trying to find and alternative solution to cope with low bit precision problem.
In Karp's paper (http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf), there is a list of 21 NP- Complete problems. Among them, 0-1 integer programming is defined as follows:
Input: integer matrix C and integer vector d
Property: there exist a 0-1 vector x such that Cx=d
x is exactly what we need as binary linear regression weights.
As I am not a computer scientist or mathematician, I need time to digest and understand your argument. However, it opened a door for me to search how such problem can be solved in optimization area of research.
- Badges
- Science topic
- Similar topics
- Geoscience
- Atmospheric Sciences
- Climate Science
- Climate Change