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

Description

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

In recent data analysis, a method called matrix factorization (MF) or tensor factorization (TF) has been widely used (see, for example, Non-Patent Document 1). A tensor is a high-dimensional array with three or more axes.

When the data to be analyzed can be expressed as a matrix or tensor, such as documents, purchasing history, user attribute information, or movie rating history, it is possible to automatically extract patterns in the data or complement missing values in the data by factoring matrix-represented data into the product of multiple matrices using MF, or factoring tensor-represented data into the product of multiple matrices using TF.

Hisashi Kashima. Machine Learning for Relational Data. Journal of the Robotics Society of Japan, Vol.33, No.2, pp.72-76,2015.

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 a pattern of a user's movie rating tendency, in a normal MF, the movie rating history is expressed as a matrix.

Assuming that the matrix is available, patterns are extracted by applying MF to the input. For example, the movie rating history represented in a matrix is a matrix in which row index i corresponds to a user, column index j corresponds to a movie, and the value of the matrix element 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 comprises 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 a factor of the data to be analyzed 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 aspect 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 the factor of the data to be analyzed 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 or estimate values of matrix elements, such as MF or TF, 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 MF (TF) technology 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 MF assumes that the input data is expressed as a matrix, as shown below.

MF is the input matrix

The factor matrices that correspond to the factor matrix with i rows and r columns and the factor matrix with r rows and j columns, respectively, are used to perform 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, a function that indicates that the smaller the value, the more similar the two matrices are, is the following L ₂ divergence:

Or the Bregman Divergence (BD) below:

etc. are used (see, for example, "TamaraG Kolda and BrettW Bader. Tensor decompositions and applications. SIAM review, Vol.51, No.3, pp. 455-500, 2009." (Reference 1), "RussR Salakhutdinov and Andriy Mnih. Probabilistic matrix factorization. In Advances in neural information processing systems, pp. 1257-1264, 2008." (Reference 2), and "AjitP Singh and GeoffreyJ Gordon. Relational learning via collective matrix factorization. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 650-658, 2008." (Reference 4)).

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,

corresponds to logistic loss,

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 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. Various methods can be used to optimize this loss function, such as Stochastic Gradient Descent (SGD) or Newton's method. Reference 4 above describes the derivation of an algorithm that repeatedly updates the factor matrix in an alternating manner based on Newton's method.

When applying TF, we can 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 MF (TF) cannot be applied to data that lacks matrix (tensor) expression, such as the data that is the subject of this analysis. This is because, because the data is not expressed as a matrix (tensor), it is not possible to calculate the value of the loss function, nor is it possible to calculate the above Newton's update formula. Therefore, in this embodiment, the following new method is presented.

As a method for dealing with a problem related to the method of this embodiment, but different from the method of this embodiment, there is a method described in "Z.Shen, L.Du, X.Shen, and Y.Shen. Interval-valued matrix factorization with applications. In ICDM, pp. 1037-1042. IEEE, 2010." (Reference 3) and a 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 6). In the method described in Reference 3, the values of the matrix elements themselves cannot be observed, but when information on a certain interval of values, for example, information that the value of x _ij is 1 to 3, is available, a method is proposed in which MF is performed using the 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. The above-mentioned reference 6 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 6 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 was 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 5). However, the problem addressed by the method described in Reference 5 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 matrix decomposition or tensor decomposition considered in this embodiment.

In this embodiment, a method is described that can perform matrix decomposition or 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 data is insufficient to be expressed as a matrix or tensor. Hereinafter, this method is referred to as uncoupled matrix factorization (UMF) and uncoupled tensor factorization (UTF).

(Formulation)
Next, we will explain the formulation, which is the problem setting of the method described in this embodiment. Below, we will describe the UMF formulation, but the UTF formulation is almost the same if matrices are replaced with tensors based on the UMF formulation. The size of the matrix is described as _nI × _nJ . In the case of the movie rating history data mentioned above, _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, and can be created from prior knowledge, estimated from aggregate data that shows that there is z ₁ movie rated "1" and z ₂ movies rated "2", or the set of values of the elements of each row of the matrix.

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 that shows 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 of the element is greater than the value of

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 the number of times a store has been visited, answering that you visit one store more than another store rather than entering the actual number of visits will hide the fact that you have a favorite store that you visit very frequently, and will allow you to answer with less information about yourself. UMF is an 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 corresponds to the row index is written as I, and the random variable whose realization 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 conditioned on 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 as follows:

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], this approximation is accurate if (w _i1 , w _i2 )=(1/2, 0). 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 (w _i1 , w _i2 )=(b/2, a/2) can be defined. When considering a more general distribution other than a uniform distribution, the generalization loss is

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 follows:

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 θ. Therefore, from now on, the empirical loss

The objective function is expressed by the following equation (8), which is obtained by removing the constant C from

This article explains how to optimize

In equation (8), Ω _A and Ω _B are factor matrices,

represents the regularization term of the L ₁ norm or L ₂ norm, and any value can be used. In the next section, we will

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

(Estimation Algorithm)
Any optimization method can be used to estimate the parameter θ, such as stochastic gradient descent, (quasi-)Newton method, or alternating least squares method (ALS). In the following, we consider the case where the objective function is differentiable, but even if the objective function has points that are not differentiable, such as when the _L1 norm is used as a regularization term, it can be optimized in the same way by using the subgradient method. Objective function

The partial derivative of is given by the following formula:

However, the above

is index data

All data for which i _m =i is extracted from the above

is index data

All data for which j _m =j is extracted from the above

is size comparison data

All data for which i _m =i is extracted from the above.

is size comparison data

from,

All of the data listed above is extracted.

is size comparison data

from,

This is the value obtained by extracting all the data. Using these values, we can derive an update equation for estimation, for example, as follows:

We will now explain the gradient descent method. In this gradient descent method, the parameter θ is updated in the direction of steepest descent. Specifically, the update equations can be written as the following equations (9) and (10).

where ηi and γj are learning rates. By repeatedly updating the parameter θ according to these equations (9) and (10), it is possible to estimate the parameter θ. Note that, unlike the stochastic gradient effect method, the parameters for all rows i and columns j are not updated every time, but the parameters for row i selected stochastically are

and the parameters for column j

You can also just update it.

We will now explain the Newton method. In this Newton method, the update equation is derived using up to two partial derivatives. In general, the length of time required to calculate the Hessian matrix obtained by two partial derivatives is an issue with the Newton method. However, if i ≠ i′, then

and j ≠ j′, then

Efficient calculations are possible by utilizing this and the fact that it has a similar property as a regularization term, namely, that if i ≠ i′ or j ≠ j′, then by using an alternating update approach in which one factor matrix is fixed and the other factor matrix is updated, the parameter θ of the factor matrix to be updated can be updated independently for each row or column, and the Hessian matrix of the parameter θ to be updated can be a matrix of size R × R. This allows the parameter θ to be updated efficiently. The parameter

Hessian matrix of size R×R when is updated

, and

Hessian matrix when is updated

Each element is obtained as follows:

Using this, we can update the parameter θ as shown in equations (11) and (12) below.

where ηi and γj are learning rates. By repeatedly updating the parameter θ according to these equations (11) and (12), a local optimum solution for the objective function can be reached. Also, like the stochastic gradient descent method, when updating the parameter θ, the parameter θ for all rows i or columns j is not updated every time, but the parameter θ for the row i and column j selected stochastically is updated every time.

It is also possible to update only.

As mentioned above, BD is a convex function that

By changing this, various loss functions can be expressed, so by using the update formula for the gradient descent method or Newton method above, it is possible to derive the update formula for the parameter θ when using any loss function that can be expressed in BD, such as the above squared error, logistic loss, I-divergence, or Itakura-Saito pseudo distance.

(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 (13).

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 (14) below, and can be estimated using any optimization method.

Since equation (14) is defined as the sum of absolute values, it is possible to use methods that can handle the presence of 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 , wi2) of

Using any vector g belonging to , the following equation (15) 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 (16):

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 (16), any optimization method can be used, as in the case of optimizing the above formula (14), and the subgradient method can be used.

This embodiment makes it possible to perform matrix decomposition or 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 which lacks a matrix or tensor representation. This makes it possible to extract latent patterns from data in which the representation as a matrix or tensor is lacking, and to estimate the values of matrix elements.

(Explanation of operation)
The configuration of the data analysis device 1 according to this embodiment and the operation of each unit 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

, and 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

is estimated (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 (14) 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 (15). At this time, the hyper-parameter estimation unit 20 calculates 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 (8) 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. Fig. 4 is a flowchart showing an example of the operation of the parameter estimation unit. Fig. 4 shows an example of updating the parameter θ when using the Newton method.

(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 calculation iterations, here the maximum number of calculation iterations 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 (11). 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 (12). 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 2 via the input/output unit 60.
In the above embodiment, an algorithm based on Newton's method is used to estimate the parameter θ that minimizes the objective function of the above equation (8), but any other method, such as the 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

or aggregated data. In this case, hyperparameters can be estimated by minimizing (optimizing) the above formula (16) instead of the objective function of the above formula (14). Any method can be used for this optimization. In addition, while the above shows an example of applying UMF, which performs matrix decomposition on data that lacks a matrix representation, it is also possible to apply UTF, which performs tensor decomposition on data that lacks a tensor representation, in a similar framework.

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 transmitting it 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. Note that 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 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 analysis target data, 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, thereby estimating the factor of the analysis target data;
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 based on the input index data, the magnitude comparison data, and the estimated parameter;
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 analysis target data, a value based on the input index data, and a value based on the input magnitude comparison data and the estimated parameter, thereby estimating the factor of the analysis target data.
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