# Dirichlet Matrix Factorization: A Reliable Classification-Based Recommender System
## 2 Proposed Model
### Computational Complexity  
From the information of Algorithm 1, it is possible to analyze the complexity of the DirMF model in terms of time and space consumption.  
Let us first focus on the spent time. From lines 3-4 and 21-22, we observe that, for each training epoch, the training algorithm must iterate over the set of known votes, let us denote it by \(\Delta\). Now, the entry corresponding to each of the matrix factorizations must be updated, and there are \(|\mathcal{S}|\) of them (lines 6, 9, 24 and 27). Finally, each updating operation requires to modify each of the entries of the hidden vectors for users and items, and there are \(K\) of them (lines 14 and 32). Notice that the updates only require standard arithmetic operations, which are performed in constant time. Hence, taking the total number of training steps, we obtain an exact time consumption of \(O(|\Delta||\mathcal{S}|Km)\).  
To analyze how this quantity scales with the size of the dataset, we can estimate it further. Typically in real world datasets, the number of known values is a constant proportion (around 1-5%) of the total numbers of pairs (user, item), and there are \(NM\) of these pairs. On the other hand, \(\mathcal{S}\) uses to be a small set (of the order of 10 possible ratings) and \(m\) is a hyperparameter that is fixed independently of the number of entries of the dataset. Hence, the time complexity can be estimated by \(O(NMK)\), that is, the time complexity increases linearly with the number of users and items in the dataset, as well as with the number of hidden factors.  
```
input :\(R,K,\gamma,\eta,m,\mathcal{S}\) output :\(P,Q\)
1 Initialize \(P\leftarrow\text{Uniform}(0,1),Q\leftarrow\text{Uniform}(0,1)\) repeat
2 for each user \(u\)do
3 for each item \(i\) rated by user \(u\): \(R_{u,i}\)do
4\(\tau\gets 0\)
5 for each score \(s\in\mathcal{S}\)do
6\(\tau\leftarrow\tau+\omega(P_{u}^{s}\cdot Q_{i}^{s})\)
7 end for
8 for each score \(s\in\mathcal{S}\)do
9\(\hat{R}_{u,i}^{s}\gets 1/(\#S-1-exp(R_{u,i}))\)
10 if\(s=R_{u,i}\)then
11\(\hat{R}_{u,i}^{s}\leftarrow\hat{R}_{u,i}^{s}\cdot exp(R_{u,i})\)
12\(\delta\leftarrow\omega(P_{u}^{s}\cdot Q_{i}^{s})(1-\omega(P_{u}^{s}\cdot Q_{i} ^{s}))\)
13 for each \(k\in\{1,\ldots,K\}\)do
14\(\Delta\leftarrow\delta\mathcal{Q}_{i,k}^{s}(\psi(\omega(P_{u}^{s}\cdot Q_{i} ^{s}))-\psi(\tau)-\log(\hat{R}_{u,i}^{s}))\)
15\(P_{u,k}^{s}\gets P_{u,k}^{s}-\eta\Big{(}\Delta+\gamma P_{u,k}^{s}\Big{)}\)
16
17 end for
18
19 end for
20
21 end for
22
23 end for
24 for each item \(i\)do
25 for each user \(u\) that rated item \(i\): \(R_{u,i}\)do
26\(\tau\gets 0\)
27 for each score \(s\in\mathcal{S}\)do
28\(\hat{R}_{u,i}^{s}\gets 1/(\#S-1-exp(R_{u,i}))\)
29 if\(s=R_{u,i}\)then
30\(\hat{R}_{u,i}^{s}\leftarrow\hat{R}_{u,i}^{s}\cdot exp(R_{u,i})\)
31\(\delta\leftarrow\omega(P_{u}^{s}\cdot Q_{i}^{s})(1-\omega(P_{u}^{s}\cdot Q_{i} ^{s}))\)
32 for each \(k\in\{1,\ldots,K\}\)do
33\(\Delta\leftarrow\delta P_{u,k}^{s}(\psi(\omega(P_{u}^{s}\cdot Q_{i}^{s}))- \psi(\tau)-\log(\hat{R}_{u,i}^{s}))\)
34\(Q_{i,k}^{s}\leftarrow Q_{i,k}^{s}-\eta\Big{(}\Delta+\gamma Q_{i,k}^{s}\Big{)}\)
35
36 end for
37
38 end for
39
40 end for
410
42
43 until\(m\) iterations
```  
**Algorithm 1**DirMF model fitting algorithm fixing \(\omega\) for the logistic function and shape parameters \(\hat{\psi}_{u,i}=R_{u,i}\).  
With respect to space consumption, notice that all the operations can be conducted inplace, so no extra space is needed apart from the computed values. These values correspond to the \(|\mathcal{S}|\) pairs of matrices \((P^{s},Q^{s})\) of the corresponding matrix factorization for the binary matrix \(R^{s}\). Since each of these pairs has shape \(N\times K\) and \(M\times K\), we get a space complexity of \(O(|\mathcal{S}|NMK^{2})\). Again, since \(|\mathcal{S}|\) is a fixed value independent of the size of the dataset, this complexity scales as \(O(NMK^{2})\), that is, linearly in the number of users and items and quadratically in the number of hidden factors.