Implementing regular ALS

[leodesigner]

Hi Ben,
I am trying to modify your code to work with regular ALS matrix factorization algorithm (for sparce matrices)
This code seems working for now.
However could you please take a look and verify correctness of the proposed changes ?

def least_squares(Cui, X, Y, regularization, num_threads=0):
    users, factors = X.shape
    E = np.eye(factors)
    for u in range(users):
        A = np.zeros(shape=(factors,factors))
        b = np.zeros(factors)

        # confidence = 1, Pu = confidence
        
        for i, confidence in nonzeros(Cui, u):
            factor = Y[i]
            A += np.outer(factor, factor)
            b += 1 * factor * confidence

        A += regularization * E
        X[u] = np.linalg.solve(A, b)

[benfred]

Whats the loss function you're trying to optimize here? If you're going for X[u] = (Pui - XuYi)^2 I think thats correct - but there are substantially faster ways of doing this

Since A = YtY + regI is the same for all users, you break the solving stage up and calculate the cholesky decomposition out of the loop, and then just use that to solve for different 'b' values.

The code for this would look something like

YtY = Y.dot(Y.T) + reg * numpy.eye(Y.shape[0])
U, err = scipy.linalg.lapack.dpotrf(YtY)

for u in range(users):
    b = np.zeros(factors)        
    for i, preference in nonzeros(Pui, u):
        b += Y[i] * preference
    X[u] = scipy.linalg.lapack.dpotrs(U, b)[0]

Note that I haven't tested this out - but I think the basic idea should work

[leodesigner]

Thank you, yes the loss function is X[u] = (Pui - XuYi)^2
I will test your code. Still playing with different loss functions on my dataset.
Seems your implicit ALS code is more stable comparing to Conjugate Gradient Method.
I am getting 'nan' values as the results in X and Y with cg=True.
However, if I will lower number of iterations to 5 (from 15) it seems to produce the same results as implicit ALS.

[benfred]

Would it be possible for you to email me the matrix causing the issue with the CG code? I'm interested in seeing if I can fix

[leodesigner]

Cu matrix is not too big:
Here is the my debug output:

...
C.shape (12, 12), Before Factorization (C.toarray()):
[[ 0.          2.          1.5         1.33333333  1.25        1.2         0.
   0.          0.          0.          0.          0.        ]
 [ 0.          0.          2.          1.5         1.33333333  1.25        0.
   0.          0.          0.          0.          0.        ]
 [ 0.          0.          0.          2.          1.5         1.33333333
   0.          0.          0.          0.          0.          0.        ]
 [ 0.          0.          0.          0.          2.          1.5         0.
   0.          0.          0.          0.          0.        ]
 [ 0.          0.          0.          0.          0.          2.          0.
   0.          0.          0.          0.          0.        ]
 [ 0.          0.          0.          0.          0.          0.          0.
   0.          0.          0.          0.          0.        ]
 [ 0.          0.          0.          0.          0.          0.          0.
   2.          1.5         1.33333333  1.25        1.2       ]
 [ 0.          0.          0.          0.          0.          0.          0.
   0.          2.          1.5         1.33333333  1.25      ]
 [ 0.          0.          0.          0.          0.          0.          0.
   0.          0.          2.          1.5         1.33333333]
 [ 0.          0.          0.          0.          0.          0.          0.
   0.          0.          0.          2.          1.5       ]
 [ 0.          0.          0.          0.          0.          0.          0.
   0.          0.          0.          0.          2.        ]
 [ 0.          0.          0.          0.          0.          0.          0.
   0.          0.          0.          0.          0.        ]]
Running factorization...
X
[[ nan  nan  nan]
 [ nan  nan  nan]
 [ nan  nan  nan]
 [ nan  nan  nan]
 [ nan  nan  nan]
 [ nan  nan  nan]
 [ nan  nan  nan]
....

Here is the configuration for matrix factorization:

dtype = np.float64 
mf_n_factors = 3
regularization = 0.01
iterations = 15 # 5 for cg, 15 for ALS
use_native = True
#cg = False
cg = True

users, items = C.shape

X = np.random.rand(users, mf_n_factors).astype(dtype) * 0.01
Y = np.random.rand(items, mf_n_factors).astype(dtype) * 0.01

X,Y = alternating_least_squares(C,
							X,
							Y,
                                 factors=mf_n_factors,
                                 regularization=regularization,
                                 iterations=iterations,
                                 use_native=use_native,
                                 dtype=dtype,
                                 use_cg=cg,
                                 calculate_training_loss=True)

After changing iterations to 5, or changing mf_n_factors to 5
I am getting the same results as with implicit ALS.

[benfred]

Thanks! will dig in on the weekend and hopefully fix

[benfred]

Turned out to be a simple fix , that last commit should resolve this issue. Thanks for letting me know!

[leodesigner]

Thanks ! I was suspecting division by zero too.

[yangji9181]

Hi Ben,

It feels like the current code is still suffering this issue same: when I tried to run the 'basic usage' on a few small 100*200 random 0-1 matrixes, the output scores are always nan. Could you try to look into that again?

Thanks.