# How to add extra constraints to a linear system for probabilities？

Background：

I have an equation which looks like as follows:

$$W \times P = R$$

$$\left[\begin{array} &{1}&{0}&{0}&-\frac{w_{1}}{w_{o1}} &\dots &{0} &-\frac{w_{1}}{w_{0} } \\{0}&{-\frac{w_{2}}{w_{o2}}}&{1}&{0}&\dots &{0} &-\frac{w_{2}}{w_{o2}} \\ &&&& {\vdots} \\ {1} & {c-1} & {0} & {0} &{\cdots} & {0} & {0} \\ {0} & {0} & {1} & {c-1} & {\cdots} & {0} &{0} \\ &&&&{\vdots}\end{array}\right] \left[ \begin{array}{c}{p_{11}} \\ {p_{1o}} \\ {p_{22}} \\ {p_{2o}} \\ {\vdots} \\ {p_{c c}} \\ {p_{co}}\end{array}\right] = \left[ \begin{array}{l}{0} \\ {0} \\ {\vdots} \\ {0} \\ {1} \\ {\vdots} \\ {1} \end{array}\right]$$

$$c$$ denotes the number of classes and here, $$c = 5$$.
The elements of $$P$$ denote the probability of belonging to each class.

For example, $$p_{11}$$ denotes the probability the 1st sample belongs to the first class. $$p_{1o}$$ denotes the probability the 1st sample belongs to the classes except for the first class.

W = array([[  1.        ,   0.        ,   0.        ,  -1.76690464,
0.        ,  -1.76690464,   0.        ,  -1.76690464,
0.        ,  -1.76690464],
[  0.        , -38.43501272,   1.        ,   0.        ,
0.        , -38.43501272,   0.        , -38.43501272,
0.        , -38.43501272],
[  0.        , -41.64051053,   0.        , -41.64051053,
1.        ,   0.        ,   0.        , -41.64051053,
0.        , -41.64051053],
[  0.        ,  -1.06855322,   0.        ,  -1.06855322,
0.        ,  -1.06855322,   1.        ,   0.        ,
0.        ,  -1.06855322],
[  0.        ,  -2.86308364,   0.        ,  -2.86308364,
0.        ,  -2.86308364,   0.        ,  -2.86308364,
1.        ,   0.        ],
[  1.        ,   4.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ],
[  0.        ,   0.        ,   1.        ,   4.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ],
[  0.        ,   0.        ,   0.        ,   0.        ,
1.        ,   4.        ,   0.        ,   0.        ,
0.        ,   0.        ],
[  0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   1.        ,   4.        ,
0.        ,   0.        ],
[  0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
1.        ,   4.        ]])

R = array([0., 0., 0., 0., 0., 1., 1., 1., 1., 1.])


I try to solve this equation by using the following method:

import numpy as np
P = np.linalg.solve(W, R)


The result looks like:

P = array([ 1.29096548, -0.07274137, -1.82110745,  0.70527686, -1.80496726,
0.70124182,  0.59473423,  0.10131644,  4.10879343, -0.77719836])


Problem:

However, the result P is not I expected.

As you see, here the elements of P denote the probability belonging to each class and they should vary from 0 to 1. I don't know how to add these constraints to my equation.

I find that the condition number of W is 537. Does it cause the problem?

You could use a least-square solver with bounds.

import numpy as np
from scipy.optimize import lsq_linear

W = np.array([
[1., 0., 0., -1.76690464, 0., -1.76690464, 0., -1.76690464, 0.,
-1.76690464],
[0., -38.43501272, 1., 0., 0., -38.43501272, 0., -38.43501272, 0.,
-38.43501272],
[0., -41.64051053, 0., -41.64051053, 1., 0., 0., -41.64051053, 0.,
-41.64051053],
[0., -1.06855322, 0., -1.06855322, 0., -1.06855322, 1., 0., 0.,
-1.06855322],
[0., -2.86308364, 0., -2.86308364, 0., -2.86308364, 0., -2.86308364,
1., 0.],
[1., 4., 0., 0., 0., 0., 0., 0., 0., 0.],
[0., 0., 1., 4., 0., 0., 0., 0., 0., 0.],
[0., 0., 0., 0., 1., 4., 0., 0., 0., 0.],
[0., 0., 0., 0., 0., 0., 1., 4., 0., 0.],
[0., 0., 0., 0., 0., 0., 0., 0., 1., 4.]])
R = np.array([0., 0., 0., 0., 0., 1., 1., 1., 1., 1.])
sol = lsq_linear(W, R, bounds=(0, 1))


with solution

np.array([0.5448, 0., 0.9638, 0.0241, 0.9485, 0.0266, 0.5271, 0., 0.5726, 0.])

• i'm not sure this solution is correct. e.g. $p_{11}$ and $p_{1o}$ should add up to one (assuming the 5 classes cover all the probability space). in your solution, they don't. – GoHokies May 14 '19 at 18:49
• @GoHokies, I see. I misinterpreted the question. I think that in that case there should be an extra constraint that guarantees that the probability add up to one. – nicoguaro May 14 '19 at 18:51
• e.g. the last equation reads $p_{55} + 4 p_{5o} = 1$ - that does not seem to make much sense given the OPs interpretation of the unknowns as class probabilities... unless (1) $p_{55} =1$ or (2) there are other classes that we don't know about. – GoHokies May 14 '19 at 18:58
• @GoHokies, so I suppose that the sum of the vector $P$ adds up to $c$. But, also, each pair adds up to 1. – nicoguaro May 14 '19 at 19:04
• @GoHokies You can understand $4p_{5o}$ as the sum of $p_{51} + p_{52} + p_{53} + p_{54}$ , and here we assume that $p_{51} = p_{52} = p_{53} = p_{54}$. – rosefun May 15 '19 at 2:24