JP7635855B2 - Data analysis device, method and program - Google Patents

Description

Embodiments of the present invention relate to data analysis devices, methods and programs.

In recent years, a method called Nonnegative Matrix Factorization (NMF) or Nonnegative Tensor Factorization (NTF) has been widely used in data analysis (see, for example, Non-Patent Documents 1 and 2). A tensor is a high-dimensional array with three or more axes.

When the values of elements of the analysis target, such as documents, purchasing history, user attribute information, movie rating history, etc., can be expressed as non-negative matrices or tensors, it is possible to automatically extract patterns in the data or complement missing values in the data by factoring matrix-represented data into products of non-negative matrices using NMF, or factoring tensor-represented data into products of non-negative matrices using NTF.

Masahiro KOHJIMA, Tatsushi MATSUBAYASHI, Hiroshi SAWADA, Multiple Data Analysis and Non-negative Matrix/Tensor Factorization [I]:Multiple Data Analysis and Its Advances, The journal of the Institute of Electronics, Information and Communication Engineers, Vol.99, No.6, pp.543-550, jun 2016. Tatsushi MATSUBAYASHI, Masahiro KOHJIMA, Hiroshi SAWADA, Multiple Data Analysis and Non-negative Matrix/Tensor Factorization [II・Finish] : Tensor Data Analysis and Applications, The journal of the Institute of Electronics, Information and Communication Engineers, Vol.99, No.7, pp. 691-698, jul 2016.

However, in recent data analysis, it is sometimes necessary to analyze data in which the index of a matrix or tensor element does not correspond to the value of that element, which is created as a result of the data collection method and processing for privacy protection.
For example, in the case of extracting patterns of users' movie rating trends, normal NMF uses a matrix representation of movie rating history.

Assuming that the matrix is available, NMF is applied to extract patterns using the matrix as input. For example, the row index i corresponds to a user, the column index j corresponds to a movie, and the matrix element value x _ij indicates the rating value of movie j by user i.

However, such a matrix representation of movie rating history is not necessarily usable. For example, the fact that user i rated or watched movie j may be recorded and used, but the rating value is not recorded or made public in a form linked to movie j from the viewpoint of privacy protection, and the distribution of ratings of movie j by user i, for example, there is _one movie with a rating value of "1", there are z _two movies with a rating value of "2", etc., may be available.
In this case, the rating value of movie j by user i cannot be observed, so there is no correspondence between the matrix element index (i, j) and the value of that element. In other words, it is not known what the value of x _ij is, so the data is represented as data that cannot be expressed in a matrix.

Similarly, when dealing with user attribute information where row index i corresponds to each attribute item such as weight and annual income, and column index j corresponds to a user, from the perspective of privacy protection, the rating value is not recorded or published in a form linked to user j, and may be available in the form of a distribution of the value of item i, for example, there is _one user z whose weight is 60 kg, there are _two users z whose weight is 61 kg, etc. In this case, as in the case of movie rating history, the information of user j regarding item i cannot be observed, and therefore it is not possible to establish a correspondence between the index of a matrix element and the value of that element, resulting in data that cannot be expressed in a matrix.

This invention has been made in light of the above-mentioned circumstances, and its purpose is to provide a data analysis device, method, and program that are capable of appropriately analyzing the data to be analyzed regardless of whether there is a correspondence between the index and elements of the data to be analyzed.

A data analysis device according to one embodiment of the present invention includes an input unit that accepts input of index data, which is a set of indexes of data to be analyzed, a set of elements of the data to be analyzed, and size comparison data indicating the size relationship of the elements of the data to be analyzed; a first estimation unit that estimates parameters that minimize an upper bound of the error between a loss function used to estimate a factor of the data to be analyzed and an approximation of the loss function, based on the set of elements input by the input unit; and a second estimation unit that estimates parameters of the data to be analyzed under conditions that satisfy non-negative constraints, based on the index data, the size comparison data, and the parameters estimated by the first estimation unit input by the input unit.

A data analysis method according to one embodiment of the present invention is a method performed by a data analysis device, and includes accepting input of index data, which is a set of indexes of data to be analyzed, a set of elements of the data to be analyzed, and size comparison data indicating the size relationship of the elements of the data to be analyzed; estimating parameters that minimize an upper bound of the error between a loss function used to estimate a factor of the data to be analyzed and an approximation of the loss function based on the input set of elements; and estimating factors of the data to be analyzed under conditions that satisfy non-negative constraints based on the input index data, the size comparison data, and the estimated parameters.

According to the present invention, the data to be analyzed can be appropriately analyzed regardless of whether there is a correspondence between the index and elements of the data to be analyzed.

FIG. 1 is a diagram showing an application example of a data analysis device according to an embodiment of the present invention. FIG. 2 is a flow chart showing an example of an outline of the operation of the data analysis device according to one embodiment of the present invention. FIG. 3 is a flowchart showing an example of an operation of the hyper-parameter estimation unit. FIG. 4 is a flowchart showing an example of the operation of the parameter estimation unit. FIG. 5 is a block diagram showing an example of a hardware configuration of a data analysis apparatus according to an embodiment of the present invention.

Hereinafter, an embodiment of the present invention will be described with reference to the drawings.
In this embodiment, we will explain a method that can automatically extract patterns in data and estimate the values of matrix elements, such as NMF or NTF, even if the data is given in a format in which the index of a matrix or tensor element cannot correspond to the value of that element.

Conventional NMF (NTF) cannot analyze data in which the indices of matrix (tensor) elements do not correspond to the values of those elements, as described above. This is because NMF assumes that the input data is expressed in matrices, as shown below.

NMF is an input matrix

A factor matrix with non-negative elements that corresponds to the factor matrix with i rows and r columns and the factor matrix with r rows and j columns, respectively, and that performs a low rank approximation of

and

Patterns are extracted by estimating as the result of factorization.

The estimation of the factor matrix is done by the matrix

and the product of the factor matrices

and are similar values.

The (i, j) element of

The loss function used as a measure of similarity above, that is, the smaller the value, the more similar the two matrices are, is the following L ₂ divergence function.

Or Bregman Divergence (BD)

etc. are used (see, for example, "InderjitS Dhillon and Suvrit Sra. Generalized nonnegative matrix approximations with bregman divergences. In Proceedings of the 18th International Conference on Neural Information Processing Systems, pp. 283-290, 2005." (hereinafter, Reference 1) and the above-mentioned non-patent document 1).

In addition,

is a convex function,

is its derivative. The function

By changing , BD can express various functions. For example,

corresponds to the squared error,

When

When this is the case, it corresponds to I-divergence (also called generalized KL (Kullback-Leibler) divergence),

When , it corresponds to the Itakura-Saito pseudo-distance. Determining the loss function to use is equivalent to making an assumption on the probability distribution that generates the matrix elements. Specifically, using the above squared error, I-divergence, or Itakura-Saito pseudo-distance corresponds one-to-one to the assumption that the matrix elements are generated according to normal distribution, poisson distribution, or exponential distribution, respectively.

The factor matrix is estimated by minimizing the loss function shown above, subject to the constraint that each element of the factor matrix must be a non-negative value. Various methods can be used for this optimization, including stochastic gradient descent (SGD), projected gradient method, and majorization minimization. For example, the majorization minimization method, which minimizes BD, performs optimization by repeatedly updating the factor matrix below (see Reference 1 above).

however,

is the element-wise product (Hadamard product),

Matrix

Represents the (i, r) component of.

When applying NTF, we need to consider low-rank approximations of tensors rather than matrices. For example, a third-order tensor

is approximated by CP decomposition (Canonical Polyadic decomposition), that is, decomposed into a basis number R of factors, the elements x _ijk of the tensor and its factor matrix

and

Approximation by

It is sufficient to estimate that and are similar values.

The above NMF (NTF) cannot be applied to data that lacks a matrix (tensor) representation, such as the data that is the subject of this analysis. Because the data is not represented as a matrix (tensor), it is not possible to calculate the value of the loss function, nor is it possible to calculate the update equation for the above auxiliary function. Therefore, in this embodiment, the following new method is presented.

A method for dealing with a related problem, different from the method in this embodiment, is "Masahiro Kohjima, Tatsushi Matsubayashi, and Hiroyuki Toda. Generalized interval valued nonnegative matrix factorization. In IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 3412-3416, 2019.
(Reference 2) and the method described in "Yuto Yamaguchi and Kohei Hayashi. Tensor decomposition with missing indices. In International Joint Conference on Artificial Intelligence, pp.3217-3223, 2017." (Reference 4). In the method described in Reference 2, the values of the matrix elements themselves cannot be observed, but when information on a certain range of values is available, for example, the value of x _ij is between 1 and 3, a method is proposed to perform NMF using that information.

The problem considered in this embodiment is different from the problem where information on a certain interval of values is given, so this method cannot be applied. Reference 4 above proposes a method that can perform tensor decomposition even if the tensor index is missing. In this method, even if some of the indexes, for example j, of the tensor index and element pair (i, j, k, x _ijk ) are missing, tensor decomposition is applied by estimating the value of the missing index.

The method considered in this embodiment differs from the method described in Reference 4 above in that it is a method that can analyze data without the need to estimate missing values and establish correspondence between indices and matrix elements.

In this embodiment, the objective function used for parameter estimation is derived using the same approximation as that used to derive the objective function in the regression method described in "Liyuan Xu, Gang Niu, Junya Honda, and Masashi Sugiyama. Uncoupled regression from pairwise comparison data. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 3992-4002, 2019." (Reference 3). However, the problem addressed by the method described in Reference 3 here is a regression problem of estimating a function f that determines the relationship y=f(x) between an input x and an output y, which is a different problem from the nonnegative matrix decomposition or nonnegative tensor decomposition considered in this embodiment.

In this embodiment, a method is described that can perform nonnegative matrix factorization or nonnegative tensor factorization even for data in which the index of a matrix or tensor element cannot be associated with the value of that element, and the data is insufficient to be expressed as a matrix or tensor. Hereinafter, this method is referred to as Uncoupled Nonnegative Matrix Factorization (UNMF) and Uncoupled Nonnegative Tensor Factorization (UNTF).

(Formulation)
Next, the formulation, which is the problem setting of the method described in this embodiment, will be described. Below, the formulation of UNMF will be described, but the formulation of UNTF is almost the same if matrices are replaced with tensors based on the formulation of UNMF. The size of the matrix is described as _nI × _nJ . In the case of the above-mentioned movie rating history data, _nI represents the number of users and _nJ represents the number of movies. The set of matrix indices is

Hereinafter, this will be referred to as index data. n _U represents the number of indexes in this data. In the case of the movie rating history data mentioned above,

corresponds to the set of data that records that user i _m has rated or watched movie j _m .

Furthermore, the set of distributions for the elements of each row of the matrix, i.e., the set of probability distributions, is

The distribution of elements in each row above is the Probability Density Function (PDF) of the matrix elements conditioned (or fixed) on row i and marginalized with respect to column j.

In the case of the movie rating history data mentioned above, f _X|I=i (x) represents the probability density function of movie rating value x by a certain user i. It can be created from prior knowledge, estimated from aggregate data that there are z ₁ movies rated "1" and z ₂ movies rated "2", or the set of values of the elements of each row of the matrix.

can be used. n _V represents the number of elements in the data. i _m represents the row index, and x _m represents the value of an element in a column in the i _m- th row, although the column is unknown. As will be described later, when using aggregated data or a set of element values in each row, the method can be applied without explicitly estimating this probability density function.

In addition to the above, the data showing the magnitude relationship of the matrix elements is

Hereafter, we will call it the size comparison data. _{i m} is the row index,

and,

and are both column indexes and the element value

value is,

It means that the value is greater than the value of the element.

The data itself is not observed. n _R represents the number of sets of matrix elements compared. For example, when a user evaluates a movie j, they can be asked to judge whether it is better than another movie j' and record the result of this judgment, and this kind of data can be obtained. Compared to giving a score such as 1 or 2, it is easy for users to answer and it is often easy to collect the data.

Also, when the elements of a matrix are not movie ratings but rather represent the number of visits to a store, answering simply that you visit one store more than another store, rather than entering the actual number of visits, allows you to hide the fact that you have a favorite store that you visit very frequently and allows you to answer with less information about yourself.

UNMF is index data

, a set of probability distributions

, and size comparison data

The three data are input, and the factor matrix

is a method to estimate the factor matrix.

and the estimates for each element using the factor matrix are

It is written.

(Loss Function) Next, we will explain how to derive the loss function for the above estimation. In defining the loss function, the random variable whose realization value corresponds to the row index is written as I, and the random variable whose realization value corresponds to the column index is written as J.
Furthermore, the random variables whose realizations correspond to the values of the matrix elements are denoted as X. The probability distributions that these random variables follow are denoted as P _I,J,X .
Furthermore, the conditional probability distribution when I = i and the probability density function of this probability distribution are written as P _J,X|I = i and f _J,X|I = i, respectively.
The distributions obtained by further marginalizing this conditional distribution with respect to J or X above are written as P _X|I=i and P _J|I=i , respectively. The probability density function of the probability distribution P _X|I=i is written as f _X|I=i , and the cumulative density function is written as F _X|I=i . By definition,

is.

The loss function used to estimate the parameter θ using the above random variables is defined as the following equation (1) using the above Bregman divergence.

However, in equation (1),

is the expected value operation based on the probability distribution P _I,J,X ,

is defined by the following equation (2).

However, in equation (2),

represent the expected value operations based on the probability distributions P _J,X|I=i and P _J|I=i , respectively. The difficulty in this loss function is caused by the last term on the right-hand side of equation (2)

This is because this term is defined by the joint distribution of column index J and element X, but in the problem setting considered in this embodiment, the index and the element are not associated and cannot be observed simultaneously, so it cannot be calculated even if, for example, a sample approximation is performed. Therefore, hereafter, we consider approximately evaluating this term.

We introduce a new set of random variables (J ⁺ , J ^- ) whose realizations correspond to the index of the columns. This set indicates that for a fixed i, the value of element (i, J ⁺ ) is greater than the value of (i, J ^- ), and is defined as follows:

Here, (J, X) and (J′, X′) are both independent random variables with probability P _J,X|I=i . From this definition, the above-mentioned size comparison data

We will later use the fact that we can consider J+ and J- to be the realization of this random variable. Hereafter, the probability density functions that J ⁺ and ^J- follow under the condition that i is fixed are respectively

and

The expected value operation for the appearance of J ⁺ and J ^- is

Using this random variable, it can be shown that the following equations (3) and (4) hold.

where F _X|I=i is the cumulative density function for the element values with row i fixed.

is.

The proof of formula (3) will be explained. According to the definition of J ⁺ , fJ _+|I=i can be expanded as follows.

where Z is a normalization constant defined as follows:

By integration by parts, we can derive that Z = 1/2. Using this result, we can derive equation (3) as follows:

The derivation of equation (4) is similar. This completes the proof.

Using equations (3) and (4), when the conditional marginal distribution of the random variable X is a uniform distribution on [0, 1] (i.e., F _X|I=i (x)=x), the last term on the right-hand side of equation (2) is

Taking this fact into consideration, a certain hyperparameter

It seems promising to use the approximation form shown in the following equation (5).

However, in equation (5), the value on the right side indicates that the value on the left side is an approximation. In the above uniform distribution on [0, 1], if we define (w _i1 , w _i2 )=(1/2, 0), this approximation is accurate. This can also be generalized to the case where the conditional marginal distribution of the random variable X is a uniform distribution on [a, b] (F _X|I=i (x)=(xa)/(ba) for all x∈[a, b]), where we define (wi1, wi2)=(b/2, a/2). When considering a more general distribution other than a uniform distribution, the generalization loss

We can determine the hyperparameters (w _i1 , w _i2 ) so as to minimize the upper bound of . This determination will be described later.

By adding up equations (3) and (4), we obtain the following equation.

Using this formula, the above formula (5) can be transformed into the following formula (6) using a certain constant λ _i .

There is a degree of freedom in setting λ _i , and it can be set arbitrarily, such as λ _i =0 or λ _i =(w _i1 +w _i2 )/2. However, it is basically desirable for the value of λ _i to be zero or greater, and in the following explanation, it is assumed that λ _i ≧0. Using the above formula (6), the generalization loss of formula (1) can be calculated as

Approximation of

is obtained as follows:

however,

The above C _i is a constant that does not depend on the parameter θ. Therefore, by replacing the expected values for the random variables I, J, J ⁺ , and J ^- with the sample average, the empirical risk is expressed as the following equation (7).

is obtained.

where C is a constant that does not depend on the parameter θ. Since these quantities, except for the constant C, can be calculated from data, they can be used as the objective function for estimating the parameter θ. In the next section, we will discuss the empirical loss

We describe a parameter estimation method, i.e., an estimation algorithm, that minimizes .

(Estimation Algorithm)
To estimate the parameter θ, any optimization method can be used, such as stochastic projected gradient descent, multiplicative update, projected quasi-Newton method, alternating least squares method (ALS), auxiliary function method, etc.

The partial derivative of can be calculated from the data as follows:

however,

is index data

All data for which i _m =i is extracted from

is index data

All data for which j _m =j is extracted from

is size comparison data

All data for which i _m =i is extracted from

is size comparison data

from,

This is an extract of all the data,

is size comparison data

from,

This is the extraction of all the data that is Using these values, we can derive an update equation for estimation, for example, as follows:

We will now explain the above projected gradient descent method. In this projected gradient descent method, parameter updates are performed in the following format, which combines updating the parameters in the steepest descent direction with a projection operation to satisfy the non-negativity constraint. Specifically, the update formulas can be written as the following formulas (8) and (9).

where ηir, γrj are learning rates, and [·] ₊ represents, for example, any projection operation to satisfy the non-negativity constraint. An example of projection is [y] ₊ =max(ε, y) using a sufficiently small positive integer ε. The parameter θ can be estimated by repeatedly updating the parameter θ according to equations (8) and (9).

The above multiplicative update method will now be explained. In this multiplicative update method, the update formula is derived by setting the learning rate in the above projected gradient descent method so that the partial differential, in this case the positive component in the steepest descent direction, is the denominator, and the negative component is the numerator. Following this, the following update formulas (10) and (11) can be derived.

When applying the multiplicative update method, as shown above, all values on the right side of the update equation are positive, so by setting the initial value to a non-negative value, the non-negativity constraint is naturally satisfied. By repeatedly updating the parameter θ according to the above equations (10) and (11), the function

However, under the assumption that certain conditions are satisfied, a local optimum for the objective function can be reached.

As mentioned above, BD is a convex function that

By changing , we can express various loss functions, so we can derive various estimation formulas from the above update formula. For example,

, that is, if we use a function equivalent to squared error,

is a constant, so the factor matrix when using the multiplicative update method is

The update equation for is derived as follows:

Similarly, we can derive the update formula when using any loss function that can be expressed in BD, such as the logistic loss, I-divergence, or Itakura-Saito pseudodistance mentioned above.

(Hyperparameter estimation)
Finally, we will describe the estimation of the hyper-parameters {w _i1 , w _i2 }. These hyper-parameters can be determined by minimizing the function _Erri as shown in the following equation (12).

This function is the function

of

is an upper bound on the error of the approximation by

and for component (i, j)

under the condition that

Therefore, the approximation error can be reduced by minimizing the above function _Erri . The function _Erri includes integral calculations, but since the distribution f _X|I=i (x) is known by assumption, it can be calculated as a discrete approximation. Specifically, for example, all possible values of x can be calculated discretely.

and divide it into, for example, the 0.01 quantile of x

and the 0.99th quantile is

As

This can be approximated by setting and minimizing the right-hand side of equation (13) below, and can be estimated using any optimization method.

Since this equation (13) is defined as the sum of absolute values, it is possible to use a method that can handle even if there are non-differentiable points in the objective function, such as the subgradient method, or linear programming.
When using the subgradient method, the function

The set of subgradients at w _i =(w _i1 , w _i2 ) of

Using any vector g belonging to , the following equation (14) is

Then we repeatedly update the parameter θ according to the following, where γ′ is the learning rate.

In the above, we have shown how to estimate hyperparameters when the probability distribution f _X|I=i (x) is known.

It is also possible to estimate hyperparameters using

The value where i _m =i is extracted from

Then, the function _Erri can be approximated as in the following equation (15):

however,

is the empirical approximation of the cumulative density function F _X|I=i

is.

teeth

represents the number of data points. When aggregated data is used, the function _Erri can be similarly approximated. For optimizing the above formula (15), any optimization method can be used, as in the case of optimizing the above formula (13), and the subgradient method can be used.

This embodiment makes it possible to perform nonnegative matrix decomposition or nonnegative tensor decomposition even for data in which the index of a matrix or tensor element does not correspond to the value of that element and the representation as a matrix or tensor is insufficient. This makes it possible to extract latent patterns from data in which the representation as a matrix or tensor is insufficient and to estimate the values of matrix elements.

(Explanation of operation)
The operation of each unit of the data analysis device 1 according to this embodiment will be described below.
FIG. 1 is a diagram showing an application example of a data analysis device according to an embodiment of the present invention.
1, a data analysis device 1 according to an embodiment of the present invention includes an input data processing unit 10, a hyperparameter estimating unit 20, a parameter estimating unit 30, a parameter processing unit 40, a recording unit 50, and an input/output unit 60. The input/output unit 60 is capable of inputting and outputting data to and from an external device 2.
The recording unit 50 includes an input data recording unit 51 , a hyper-parameter recording unit 52 , and a parameter recording unit 53 .

Next, an overview of the operation of the data analysis device 1 will be described below. Fig. 2 is a flowchart showing an example of the overview of the operation of the data analysis device according to an embodiment of the present invention.
First, the input data processing unit 10 of the data analysis device 1 receives index data

, a set of probability distributions

, size comparison data

is input from the external device 2 via the input/output unit 60 (step S1).

Next, the hyper-parameter estimation unit 20 estimates the hyper-parameter

Estimate (step S2).

Next, the parameter estimation unit 30 estimates the parameter θ (step S3).
Next, the parameter processing unit 40 outputs the estimated parameter θ to the external device 2 via the input/output unit 60 (step S4).

The specific operations of S1 to S4 above will be described below.
First, a specific example of S1 will be described. The input data processing unit 10 receives index data

, a set of probability distributions

, and size comparison data

and store it in the input data recording section 51 of the recording unit 50.

Next, a specific example of S2 will be described. The hyperparameter estimation unit 20 estimates the set of probability distributions stored in the input data recording unit 51.

and estimates the hyper-parameter w by minimizing the objective function of the above formula (13) using the following methods (a) to (d). The hyper-parameter estimation unit 20 stores the estimated hyper-parameter w in the hyper-parameter recording unit 52 of the recording unit 50. FIG. 3 is a flowchart showing an example of the operation of the hyper-parameter estimation unit. FIG. 3 shows an example of updating the hyper-parameter w _i when the subgradient method is used. By performing this update for each i=1,...,n _I, the hyper-parameter w to be estimated is obtained.

(a) The hyper-parameter estimation unit 20 initializes the parameter w _i (step S21). As a variable used as a termination condition for the process in step S2, the hyper-parameter estimation unit 20 similarly initializes a variable δ indicating the maximum change range of the update amount of the hyper-parameter w _i , and sets a threshold ε and a maximum number of calculation iterations for the termination condition, here the maximum value of the number of calculation iterations for updating the variable δ (step S22).

(b) The hyper-parameter estimation unit 20 updates the parameter w in accordance with the above formula (14). At this time, the hyper-parameter estimation unit 20 estimates the maximum absolute value of the difference between the hyper-parameter w _i before the update and the hyper-parameter w _i after the update.

is recorded in the variable δ (step S23). Here, the elements of the hyper-parameter w _i before the update are

The elements of the updated hyperparameter w _i are

It is described as follows.

(c) In response to step S23, the hyper-parameter estimation unit 20 updates the count value of the number of times the calculation is repeated (step S24).
(d) When the count value of the number of calculation iterations exceeds the predetermined maximum number of iterations or the variable δ indicating the maximum change width of the update amount is smaller than the predetermined threshold ε (Yes in step S25), the hyper-parameter estimation unit 20 ends the process related to step S2. Otherwise (No in step S25), the hyper-parameter estimation unit 20 sets the variable δ to δ←0 and returns to step S22.

Next, a specific example of S3 will be described. The parameter estimation unit 30 uses the index data stored in the input data recording unit 51

, size comparison data

and the hyper-parameter w stored in the hyper-parameter recording unit 52, and estimates the parameter θ by minimizing the objective function of the above equation (7) using the following methods (a) to (e). The parameter estimation unit 30 stores the estimated parameter θ in the parameter recording unit 53 of the recording unit 50. Figure 4 is a flowchart showing an example of the operation of the parameter estimation unit. Figure 4 shows an example of updating the parameter θ when the multiplicative update method is used.

(a) The parameter estimation unit 30 initializes the parameter θ (step S31). As a variable used as the termination condition for the process related to step S3, the parameter estimation unit 30 similarly initializes a variable δ indicating the maximum change range of the update amount of the parameter θ, and sets the threshold ε of the termination condition and the maximum number of iterations of the calculation, here the maximum number of iterations of the calculation related to the update of the variable δ (step S32).

(b) The parameter estimation unit 30 estimates the factor matrix

is updated according to the above formula (10). At this time, the parameter estimation unit 30 updates the factor matrix before and after the update

Maximum absolute value of the difference

If is greater than the current variable δ, the parameter estimation unit 30 sets this variable δ to

(step S33). However, the factor matrix before the update

The elements of

and the above elements after the update are

It is described as follows.

(c) The parameter estimation unit 30 estimates the factor matrix

is updated according to the above formula (11). At this time, the parameter estimation unit 30 calculates the factor matrix before and after the update

Maximum absolute value of the difference

If is greater than the current variable δ, set this variable δ to

(step S34). However, the factor matrix before the update

The elements of

and the above elements after the update are

It is described as follows.

(d) In response to step S34, the parameter estimation unit 30 updates the count value of the number of calculation iterations (step S35).

(e) If the count value of the number of calculation iterations exceeds the maximum number of iterations determined above, or if the variable δ indicating the maximum change in the update amount is smaller than the predetermined threshold value ε (Yes in step S36), the parameter estimation unit 30 terminates the processing related to step S3; otherwise (No in step S36), the parameter estimation unit 30 sets the variable δ to δ←0 and returns to step S32.

Next, a specific example of S4 will be described. The parameter processing unit 40 outputs the parameter θ stored in the parameter recording unit 53 to the external device 3 via the input/output unit 60.
In the above embodiment, the algorithm based on the multiplicative update method is used to estimate the parameter θ that minimizes the objective function of the above equation (7), but any other method, such as the above projected gradient descent method, may be used. Also, in the above embodiment, a set of probability distributions is used to estimate the hyperparameters.

is used, but instead, a set of element values for each row of the matrix

Alternatively, aggregated data may be used. In this case, the hyperparameters can be estimated by minimizing (optimizing) the above formula (15) instead of the above formula (13). Any method can be used to optimize K. In addition, the above shows an example of applying UNMF, which performs nonnegative matrix decomposition on data that lacks a matrix representation, but in a similar framework, it is also possible to apply UNTF, which performs nonnegative tensor decomposition on data that lacks a tensor representation.

FIG. 5 is a block diagram showing an example of a hardware configuration of a data analysis device according to an embodiment of the present invention.
5, the data analysis device 1 according to the embodiment is configured, for example, by a server computer or a personal computer, and has a hardware processor 111A such as a CPU (Central Processing Unit). A program memory 111B, a data memory 112, an input/output interface 113, and a communication interface 114 are connected to the hardware processor 111A via a bus 115.

The communication interface 114 includes, for example, one or more wireless communication interface units, and enables transmission and reception of information to and from a communication network NW. As a wireless interface, for example, an interface that adopts a low-power wireless data communication standard such as a wireless LAN (Local Area Network) is used.

An input device 200 and an output device 300 used by a user or the like, which are attached to the data analysis apparatus 1, are connected to the input/output interface 113. The input device 200 and the output device 300 correspond to the external device 2 shown in FIG.
The input/output interface 113 takes in operation data input by a user or the like through an input device 200 such as a keyboard, a touch panel, a touchpad, a mouse, or the like, and outputs output data to an output device 300 including a display device using liquid crystal or organic EL (Electro Luminescence), etc., for display. The input device 200 and the output device 300 may be devices built into the data analysis device 1, or may be input devices and output devices of other information terminals that can communicate with the data analysis device 1 via the network NW.

The program memory 111B is a non-transient tangible storage medium that is a combination of a non-volatile memory that can be written to and read from at any time, such as a hard disk drive (HDD) or solid state drive (SSD), and a non-volatile memory such as a read only memory (ROM), and stores the programs necessary to execute various control processes, etc. according to one embodiment.

Data memory 112 is a tangible storage medium that is, for example, a combination of the above-mentioned non-volatile memory and a volatile memory such as RAM (Random Access Memory), and is used to store various data acquired and created during various processing steps.

A data analysis device 1 according to one embodiment of the present invention can be configured as a data processing device having an input data processing unit 10, a hyperparameter estimation unit 20, a parameter estimation unit 30, a parameter processing unit 40, and an input/output unit 60 as software-based processing function units, as shown in FIG. 1.

Each information storage unit and recording unit 50 used as a working memory by each unit of the data analysis device 1 can be configured by using the data memory 112 shown in Fig. 5. However, these configured storage areas are not essential components within the data analysis device 1, and may be areas provided in a storage device such as an external storage medium such as a Universal Serial Bus (USB) memory, or a database server located in the cloud.

The processing function units in the input data processing unit 10, the hyper parameter estimation unit 20, the parameter estimation unit 30, the parameter processing unit 40, and the input/output unit 60 can all be realized by reading and executing a program stored in the program memory 111B by the hardware processor 111A. Note that some or all of these processing function units may be realized in various other forms, including integrated circuits such as application specific integrated circuits (ASICs) or field-programmable gate arrays (FPGAs).

The methods described in each embodiment can be stored as a program (software means) that can be executed by a computer on a recording medium such as a magnetic disk (floppy disk, hard disk, etc.), optical disk (CD-ROM, DVD, MO, etc.), semiconductor memory (ROM, RAM, flash memory, etc.), and can be distributed by transmission via a communication medium. The programs stored on the medium also include a setting program that configures the software means (including not only execution programs but also tables and data structures) that the computer executes. The computer that realizes this device reads the program recorded on the recording medium, and in some cases, constructs the software means using the setting program, and executes the above-mentioned processing by controlling the operation of the software means. The recording medium referred to in this specification is not limited to a recording medium for distribution, but also includes a storage medium such as a magnetic disk or semiconductor memory provided inside the computer or in a device connected via a network.

Note that the present invention is not limited to the above-described embodiments, and can be modified in various ways in the implementation stage without departing from the gist of the invention. The embodiments may also be implemented in appropriate combination, in which case the combined effects can be obtained. Furthermore, the above-described embodiments include various inventions, and various inventions can be extracted by combinations selected from the multiple constituent elements disclosed. For example, if the problem can be solved and an effect can be obtained even if some constituent elements are deleted from all the constituent elements shown in the embodiments, the configuration from which these constituent elements are deleted can be extracted as an invention.

REFERENCE SIGNS LIST 1 data analysis device 2 external device 10 input data processing unit 20 hyperparameter estimation unit 30 parameter estimation unit 40 parameter processing unit 50 recording unit 51 input data recording unit 52 hyperparameter recording unit 53 parameter recording unit 60 input/output unit

Claims (8)

an input unit that receives input of index data, which is a set of indexes of analysis target data, a set of elements of the analysis target data, and size comparison data indicating the size relationship of the elements of the analysis target data;
a first estimation unit that estimates a parameter that minimizes an upper bound of an error between a loss function used to estimate a factor of the analysis target data and an approximation of the loss function, based on the set of elements input by the input unit;
a second estimation unit that estimates a factor of the analysis target data under a condition that satisfies a non-negative constraint, based on the index data input by the input unit, the magnitude comparison data, and the parameter estimated by the first estimation unit;
A data analysis device comprising: The index data is
is a set of matrix or tensor indices,
The elements of the analysis target data are:
are the elements of each row of said matrix or tensor,
The magnitude comparison data is
The data indicates the magnitude relationship of the elements of the matrix or tensor.
The data analysis device according to claim 1 . The second estimation unit is
optimizing a function based on a regularization term related to a factor of the data to be analyzed, a value based on the index data input by the input unit, and a value based on the magnitude comparison data input by the input unit and the estimated parameter under a condition that satisfies a non-negative constraint, thereby estimating the factor of the data to be analyzed;
The data analysis device according to claim 1 . The first estimation unit
estimating the parameters that minimize a function based on a probability density function of elements of the analysis target data;
The data analysis device according to claim 1 . A method performed by a data analysis device, comprising:
receiving input of index data which is a set of indexes of analysis target data, a set of elements of the analysis target data, and size comparison data which indicates the size relationship of the elements of the analysis target data;
estimating a parameter that minimizes an upper bound of an error between a loss function used to estimate a factor of the analysis target data and an approximation of the loss function based on the input set of elements;
estimating a factor of the analysis target data under a condition that satisfies a non-negative constraint based on the input index data, the magnitude comparison data, and the estimated parameters;
A data analysis method comprising: The index data is
is a set of matrix or tensor indices,
The elements of the analysis target data are:
are the elements of each row of said matrix or tensor,
The magnitude comparison data is
The data indicates the magnitude relationship of the elements of the matrix or tensor.
The data analysis method according to claim 5 . Estimating the factors includes:
and optimizing a function based on a regularization term related to a factor of the data to be analyzed, a value based on the input index data, and a value based on the input magnitude comparison data and the estimated parameter under a condition that satisfies a non-negative constraint, thereby estimating the factor of the data to be analyzed.
The data analysis method according to claim 5 . A data analysis processing program that causes a processor to function as each of the components of the data analysis device described in any one of claims 1 to 4.

Images