Matrix Completion in the Unit Hypercube via Structured Matrix Factorization

1 Introduction

A variety of complex applications that emerge in several organizations can be translated to matrix completion problems. In this study, we address a key challenge faced by our company: predicting the efficiency of artists in rendering visual effects (VFX) in film shots. Effectively solving this problem is of crucial importance as project managers often rely on competency metrics, such as employee's efficiency, to best control and adjust the available assets. Figure 1 illustrates the hierarchical relationship between artists (i.e., employees) and job assignments in a VFX production framework. Here, a job for the organization just consists of a series of contributions from different departments and possibly involves numerous employees. Each department is led by a manager who divides the work in her department into multiple tasks, and each task is assigned to a single employee. Employees work on these tasks and submit partial results called claims. After assessing the quality of a claim, the manager decides whether to approve it or not. Hence, our goal is to exploit the latent attributes of each employee that explain their efficiency across various tasks to ensure products can be delivered on time.

∗Majority of work done while at Technicolor AI Lab.

The key contributions of our work are as follows: (i) transforming industrial setups into a sparse real-valued matrix with entries lying in the [0, 1] interval (e.g., efficiencies of employees in departments), and (ii) proposing two novel structured matrix factorization (MF) models to effectively solve the resulting matrix completion problem. While our methods are inspired by the hierarchical task allocation shown in Figure 1, their formulation is very general and can easily be applied to a variety of scenarios. In this paper, in particular, we consider two additional applications: (a) recommendation of apps to the users of over-the-top (OTT) streaming devices, and (b) recommendation in online advertisement placement to maximize click-through rate (CTR). The details of these applications will be explained in later sections.

Although conventional matrix factorization algorithms have been proved effective to solve the matrix completion problem, recent studies show that constrained MF techniques outperform them on a variety of datasets, including MovieLens, Jester and BookCrossing [Fang et al., 2017; Jawanpuria and Mishra, 2018]. Moreover, MF approaches tend to produce unstable and out-of-range predictions as the sparsity of the matrix increases [Jiang et al., 2018]. While most recommender systems have entries bounded within a range of possible rating values (e.g., one to five in a five-star rating system), our data lies on the unit interval [0, 1]. While we could convert our data to an ordinal space, such as ratings between one and five, as shown in Figure 2, any monotonic transformation mapping the unit interval to a larger one does not simplify the prediction problem. Therefore, we propose two novel approaches for this scenario: expertise matrix factorization (EMF), in which entries are approximated by a weighted correlation between user and item latent factors (i.e., the low-rank features), and survival matrix factorization (SMF), which uses a probabilistic model to capture the latent factors by modeling the procedure resulting in the average efficiency of an employee in a department. Both our approaches are structured matrix factorization methods with constrains derived by modeling the presented setup.

We validate the effectiveness of the proposed models using three datasets: (a) a proprietary dataset of VFX efficiencies, (b) a proprietary dataset of app usage in OTT device, and (c) a public dataset of CTR released by Outbrain. Using a rigorous series of numerical experiments, we show that the proposed models outperform popular MF techniques on scores such as RMSE, MAE, Precision@N and Recall@N.

2 RelatedWork

The allocation of resources is a relevant problem in Business Process Management to improve the performance of an organization [Dumas et al., 2013]. Recently, different approaches in Process Mining [Van Der Aalst, 2011] have been proposed to extract useful knowledge from historical data [Arias et al., 2018]. However, previous studies focused on particular process cases [Huang et al., 2012; Conforti et al., 2015]. In response, we investigate a generic framework that can be mapped to a variety of organizations. Our proposed approaches are inspired by a series of work on low-rank matrix completion, and their applications to recommendation systems [Hu et al., 2008; Cand`es and Recht, 2009; Cand`es and Plan, 2010; Koren et al., 2009; Funk, 2011; Jain et al., 2013]. A class of approaches suitable for our task consists of bounded matrix factorization methods. Non-negative matrix factorization (NMF) is the most popular method in this class, and it only provides a lower bound of 0 for the predicted values. A more general approach is given by bounded matrix factorization (BMF) [Kannan et al., 2014]: a low-rank approximation that leverages the fact that all ratings in a recommender system are bounded within a range [xmin, xmax] Our first approach, expertise matrix factorization, is closely related to these approaches and to matrix completion models with additional structure on the latent factors [Soni et al., 2016; Hoyer, 2004; Aharon et al., 2006; Kannan et al., 2014]. However, our approach departs from them in its unique structure given by the unit interval constraint in our setup. To the best of our knowledge, this structure has not been specifically tackled in the existing literature of MF with explicit data. MF methods for implicit feedback data [Hu et al., 2008; Johnson, 2014] work on the same interval, but with the major difference of relying on just matrix entries that are binary values. Our second approach, survival matrix factorization, is instead related to probabilistic matrix factorization methods [Mnih and Salakhutdinov, 2008; Salakhutdinov and Mnih, 2008]. While they also interpret matrix entries as probabilities, our method specifically models the end-to-end approval process in its formulation.

Notations. In this paper, all vectors are represented by bold lowercase letters and are column vectors (e.g., p, q). All matrices are represented by bold uppercase letters (e.g., P, Q). For a given matrix A, ai denotes its i-th row as a column vector and aij denotes its entry in row i and column j.

3 ProblemFormulation

As described in Section 1, our proposed models are inspired by the framework depicted in Figure 1. This pipeline is motivated by the concrete application scenario of work allocation in movie production at Technicolor, where artists (employees) render visual effects in film shots across various disciplines (departments). Nonetheless, this framework is very general and other production pipelines can easily be mapped into this setting. For instance, if an organization logs employees' performance on pieces of work in a 100-point scale, then each score can be mapped to an approved or rejected claim by defining a threshold value of work quality (e.g., 90/100).

Considering the work allocation scenario, a natural competency metric for employees' efficiencies is given by the ratio of number of claims accepted to the total number of claims submitted by the employee in the department. An accepted claim counts towards the employee's overall performance. In case of rejection, the employee submits a new claim when they believe it will meet the quality required. The latter scenario clearly results in a loss in performance for the entire organization as the employee might need to start over or the manager may decide to designate another employee. Let Ndn be the total number of claims by employee d in department n, and a(i) dn denote whether the i-th claim by employee d in department n was accepted (1) or rejected (0). We then define the efficiency of employee d in department n, xdn, as follows:

It is straightforward to see that xdn ∈ [0, 1].

The goal of our study is to predict the efficiencies of employees in each department. We address this challenge by building an efficiency matrix X ∈ RD×N whose entry xdn ∈ [0, 1] denotes the efficiency of employee d in department n. Only a few entries of this matrix, corresponding to the observation index set Ω ⊂ [D] × [N], are known since most employees only work in a few departments throughout their careers. Hence, our goal of predicting employees' efficiencies now reduces to predicting the missing entries of X.

4 ProposedModels

Our first proposed model, expertise matrix factorization, builds on low-rank models and introduces additional structure on the factors W and Z so that the entries of the resulting matrixW · ZT lie in unit interval. Our second model, survival matrix factorization, instead follows a probabilistic modeling of the claim approval process defining the efficiency matrix.

4.1 Expertise Matrix Factorization

In this first approach, we model the efficiency matrix as a lowrank matrix X ≈ W · ZT . In our setup, we can think of the latent factors as the set of skills or expertise required to work in a given department. In particular, we assume each employee's latent factors (skills) to range from 0 to 1, while each department's latent factors to be non-negative and to sum to 1. On the one hand, employees have a certain level in each skill, where 0 indicates no ability and 1 proficiency. On the other hand, each department is assumed to have a given proportion of skills required to complete tasks in it.

We assume a low-rank model based on the intuitive reasoning that a small number of skills may be required to complete tasks across different departments. With this model, the efficiency of employee d in department n is approximated by a weighted sum of the employee's skills, where the weights are given by the importance of each skill in the department. The structure in the latent vectors ensures that efficiency values under this model lie in [0, 1]. We further extend this model to accommodate user biases, representing the minimum proficiency of each employee in every skill. Note that it would be inconsistent to add a bias term for departments as not every skill is supposed to be useful in each discipline.

The resulting optimization problem is as follows:

where β ∈ RD is the vector of employees' biases, Ω is the set of observed entries and |Ω| is its size, λu and λi control the extent of regularization in the users and items parameters, and || · ||F denotes the Frobenius norm. The first constraint βd + wdk ≤ 1 enforces predictions in [0, 1]. In fact, ˆxdn = βd + wT d · zn = (βd1+wd)T · zn ∈ [0, 1] if βd +wdk ≤ 1. The structure on the factor Z has also been considered in blind de-mixing applications [Lin et al., 2015; Fu et al., 2018], which, however, do not deal with missing entries and do not impose any structure on the factor W. The optimization problem in Equation (2) is jointly non-convex in W, β and Z. However, for fixed values of W and β, the problem is a convex quadratic program in Z, and for fixed value Z the problem is a convex quadratic program in W and β [Boyd and Vandenberghe, 2004]. Hence, we rely on an algorithm based on alternating minimization to solve this problem, first solving for W and β, and then for Z. In particular, the former sub-problem can be solved by any quadratic program solver, while the latter by a projected gradient algorithm that maps each row of Z onto the probability simplex.

4.2 Survival Matrix Factorization

In this approach, we aim to derive a probabilistic model for the underlying process resulting in efficiency values. Recall from Equation (1) that each entry xdn in the efficiency matrix X is defined as the empirical average efficiency of employee d in department n. Each claim submitted by an employee can be viewed as an i.i.d. sample from a Bernoulli random variable Adn, and, by the Weak Law of Large Numbers, the matrix entry xdn tends almost surely to the mean value of Adn, which is equal to P(Adn = 1).

Having introduced this probability framework, in order to define P(Adn = 1), we model the process of claims acceptance. Claims represent pieces of work that employees deliver to managers, who assess the quality of each claim and accept them only if they are good enough. First, we assume employee d to submit claims to department n with a certain quality distribution. That is, each claim i has quality Qdn, a random variable sampled from an underlying probability distribution of quality of work produced by employee d in department n. Second, we model the manager of department n by a single parameter, γn, representing their quality threshold: a claim in department n is only accepted if its quality is higher than the manager's threshold (as depicted in Figure 3).

Hence, each entry xdn is approximated by:

where SQdn (γn) is the survival function, also known as complementary cumulative distribution function, of Qdn at γn, and fQdn is its probability distribution. Note also that each manager is modeled by a single variable and they are then assumed to adhere to equal opportunity laws, accepting claims with no discrimination of race, color, sex, sexual orientation or any other status of the artists.

In this paper, we assume the employees' quality probability distributions to be normal and that the variance of the quality of the claims is the same over all employees and departments:

where µdn is the mean of the distribution of quality of claims of employee d in department n and σ2 is its variance.

Furthermore, we try to explain the means µdn by characterizing both artists and disciplines with vectors of factors inferred from patterns in the data such that employeedepartment interactions are modeled as inner products in that space; i.e., µdn ≈ wTd · zn. That is:

The optimization problem we aim to solve is then given by:

(6)

The objective function in the above problem is smooth in W, Z, γ and σ, and stochastic gradient descent can be used to solve it. We use Leibniz's rule for differentiation under the integral sign to obtain the closed form expressions of the gradients with respect to W, Z and σ, and the fundamental theorem of calculus for the gradient with respect to γ.

5 Experimental Evaluations

In this section, we evaluate the empirical performance of our models on (a) a dataset of VFX rendering, (b) a dataset of OTT streams from Technicolor, and (c) a public dataset of click-through rates (CTR) in online advertising by Outbrain. Experimental results on public data are available on GitHub 1 .

5.1 Methodology

Evaluation Metrics

The quality of a recommendation algorithm can be evaluated using different types of metrics. We use RMSE and MAE as statistical accuracy metrics, while Precision@N and Recall@N as decision support metrics, for N ∈ {2, 3, 5, 10}. In the context of recommender systems, we are usually interested in recommending top-N items to the user. This is clearly the case for our framework too, items being either employees, apps or website categories. As usual, we consider as relevant items those that are already known in the datasets.

Cross-Validation

We use 3 rounds of Monte Carlo cross-validation on the movie production data (due to few non-missing entries) and 3-fold cross-validation on the OTT and CTR data. We use the RMSE scores to find the best model via cross-validation.

Details of Training

We use a maximum number of 100 epochs and a tolerance defined by L(t)-L(t-1) L(t) < 10-6 as stopping criteria for training, where L(t) is the objective cost at epoch t. In all SGDbased algorithms, we use batches of 8 entries on the VFX

1 URL: https://github.com/e-bug/unit-mf.

data, and of 128 entries on the OTT and CTR data. The best number of latent factors K is searched over all possible values in the VFX data, while we use the common values of K ∈ {10, 15, 20} in the larger OTT and CTR data. Each matrix factor is initialized with uniformly random numbers in (0, 1), and biases are initialized as zero vectors.

Learning Algorithms

The following algorithms are evaluated:

• MF. Stochastic gradient descent for MF with biases.
• NMF. Alternating non-negative least squares for NMF. Each block is updated by projected gradient descent.
• BMF. Bounded matrix factorization. To overcome the limitation requiring xmax > 1 in [Kannan et al., 2014], we scale the randomly initialized factors W and Z by √ 1 max(W·ZT ) , ensuring feasible bounds at the first step.
• PMF. Probabilistic matrix factorization.
• LMF. Logistic matrix factorization. Differently from [Johnson, 2014], we use explicit data and model each entry in the data matrix to match our framework:

ˆxdn = P (claims by artist d in discipline n are accepted)

= P (manager of discipline n accepts a claim)

P (artist d submits good claims in discipline n)

• EMF. Expertise matrix factorization. Projections of each row in Z onto the probability simplex are obtained using the O(K logK) efficient algorithm proposed in [Wang and Carreira-Perpin´an, 2013].
• SMF. Survival matrix factorization. σ is initialized to 1.

5.2 Movie Production Data

Our analysis is driven by data collected at Technicolor, where different disciplines (departments) are responsible for generating VFX in movies (jobs) and employees are referred as artists. All data was collected in accordance with appropriate end user agreements and privacy policies.

Our movie production dataset consists of claim records, each with fields: jobId (int), disciplineId (int), taskId (int), userId (int), claimId (int) and approved (bool). To ensure that each average efficiency is sufficiently representative of the true efficiency of an artist in a discipline, we remove all the entries that result from averaging less than 10 claims. This also ensures that, according to Hoeffding's theorem [Hoeffding, 1963], the approximation introduced in Equation (3) holds true with high probability. Moreover, to alleviate the cold-start problem, we remove disciplines that have claims from less than 10 artists and also drop artists with less than 3 non-missing entries. At the end of these preprocessing steps, we are left with a 312 × 25 matrix and 1, 026 non-missing entries. Not only is this matrix very sparse (86.85%) but there are also few ratings per user, with most of the artist having worked on three disciplines only. The distribution of efficiencies increases exponentially (Figure 4).

Number of disciplines per artist

Figure 4: Statistics about movie production data.

0.65 0.70 0.75 0.80 0.85 0.90 0.95 1.00 Efficiency

Table 1 reports prediction errors of each algorithm on this dataset. Precision and recall values are listed in Table 2.

5.3 Over-The-Top Data

Our second application consists of apps usage on over-the-top devices where the goal is to recommend apps to customers. Our OTT dataset consists of number of views of a given app by any user. This data is mapped to users' watching rates ∈ [0, 1] by dividing by the user's maximum number of views. Similarly to what we did for the VFX data, we remove apps that have less than 15 viewers and users who watched less than 10 apps. After preprocessing, we are left with 934 users and 140 apps and a matrix that is extremely sparse (99.91%). The distribution of watching rates is shown in Figure 5.

Tables 3 and 4 show precision and recall values for K equal to 15 and 20, respectively. Due to space constraints, results for K = 10 are omitted but followed similar patterns.

5.4 Click-Through Rate Data

In our third application, we consider the task of placing online advertisements in categories of websites (e.g., Entertainment, Finance, etc.) to maximize their click-through rate.

To simulate this scenario, we use publicly available data from a Kaggle competition 2 run by the advertisement company Outbrain. This dataset contains users' webpage views and clicks on multiple publisher sites in the United States in a two-week period in June 2016. By using additional semantic attributes of the webpages, we can formulate the problem of maximizing the CTR of an advertisement by finding the best categories to display it. After removing advertisements displayed in less than 5 categories and categories with less than 10 advertisements, we are left with 15, 647 advertisements and 85 webpage categories, resulting in a 79.99%-sparse matrix and a distribution of CTR skewed to the right (Figure 6).

Tables 5, 6 and 7 show precision and recall values for number of latent factors K equal to 10, 15 and 20, respectively.

2 URL: https://www.kaggle.com/c/outbrain-click-prediction.

Number of categories per ad

5.5 Discussion

In our VFX data, SMF achieves the lowest prediction errors and EMF outperforms every other method in precision and recall with values three times higher than the second best model. Here, the hypotheses of EMF closely match artists in our VFX framework, while they do not entirely hold for ads in CTR and users in OTT. One of the strongest points of PMF is its ability to generalize considerably well for users with very few ratings. However, here - where the maximum number of entries per user is just 7 - we see that EMF outperforms PMF in both prediction accuracy and quality of recommendations. In Table 1, we also notice an interesting empirical finding: constrained models are capable of better exploiting the underlying structure relying on a higher latent dimensionality.

Results in OTT and CTR datasets instead show how SMF is a very general model and outperforms every other algorithm in terms of precision and recall, regardless of the chosen number of latent factors K. In OTT, the gap is wider for smaller values of K; in CTR, EMF consistently achieves the second highest precision. We believe that SMF underperforms in the VFX data due to the very few available entries rather than its sparsity (OTT is much sparser). Here, SMF's performance is comparable to other bounded models such as BMF and LMF.

6 Conclusion

In this paper, we introduced EMF and SMF: two novel structured MF methods to predict entries in the unit interval. We showed that these models provide better recommendations than popular MF techniques on three real-world datasets. Hence, it is beneficial to explicitly model entries in the unit interval, motivating further research in this domain.

In addition, SMF is more than just one method: it is the simplest in a class of probabilistic models. In this paper, we assumed users' quality of work to be normally distributed and managers to be modeled by a scalar threshold variable. In future work, we plan to extend this model to include more complex assumptions depending on the application domains.