JP6465440B2 - Analysis apparatus, method, and program - Google Patents

Description

  The present invention relates to an analysis apparatus, method, and program, and more particularly, to an analysis apparatus, method, and program for analyzing data using a regularization technique.

  Supervised learning is a technique for estimating parameters for predicting supervised data from observed data when given training data consisting of pairs of observed data and supervised data. Parameter estimation is formulated as a problem that minimizes errors when predicting teacher data from observed data. The performance of the estimated parameters is evaluated by the error (generalization error) when predicting the teacher data from unknown observation data not included in the training data called test data. The smaller the generalization error, the better the performance It is said.

  In recent years, in the supervised learning research field, the accuracy of estimation deteriorates as the generalization error of the estimated parameters increases when the training data is less than the dimensions of the unknown observation data as the observation data increases in dimension. The problem is getting attention. This phenomenon is based on the phenomenon of overlearning. Therefore, regularization techniques that introduce prior knowledge obtained in advance as data as regularization terms, restrict the possible values of parameters, and avoid overlearning have been studied. Among regularization techniques, the one using the structure of parameters is called structural regularization, and has been actively studied in recent years.

  Non-Patent Document 1 proposes a structural regularization technique called combined regularization (Fused Lasso). The combined regularization technique introduces prior knowledge that a certain parameter and another parameter have the same true value because they have an adjacent relationship as a regularization term. Non-Patent Document 1 proposes a method for minimizing the joint regularization term, and it is reported from experiments that the performance is higher than that of the regularization technique that does not use the structure in the data having parameters adjacent to each other.

  Non-Patent Document 2 proposes a technique called generalized combined regularization (Generalized Fused Lasso) in which the adjacency relationship of connection regularization is expanded to an arbitrary adjacency relationship. Non-Patent Document 2 shows that generalized joint regularization is consistent with the Robache extension of the submodular function in discrete optimization (see Non-Patent Document 3), and further using its properties, Non-Patent Document 4 and Non-Patent Document 7 proposed a method for minimizing generalized coupled regularization terms.

  In unsupervised learning, observation data is included in training data and test data, but when teacher data is not included, a technique for analyzing data, such as matrix decomposition, has been proposed. Even in unsupervised learning, the problem of over-learning has occurred with higher data dimensions, and research to apply regularization technology to avoid this problem has been conducted, and improvement in analysis accuracy has been reported. .

Tibshirani, R., Saunders, M., Rosset, S., Zhu, J., Knight, K .: Sparsity and smoothness via the fused lasso.Journal of the Royal Statistical Society: Series B (Statistical Methodology) 67 (1) , 91-108 (2005) Xin, B., Kawahara, Y., Wang, Y., Gao, W.: Efficient generalized fused lasso with its application to the diagnosis of Alzheimer ’s disease.In: Proc. Of AAAI. Pp. 2163-2169 (2014) Fujishige, S .: Submodular function sandoptimization, vol. 58. Elsevier (2005) Gallo, G., Grigoriadis, M.D., Tarjan, R.E .: A fast parametric maximum flow algorithm and applications.SIAM Journal on Computing 18 (1), 30-55 (1989) Kohli, P., Ladicky, L., Torr, P.H.S .: Robust higher order potentials for enforcing label consistency.International Journal of Computer Vision 82 (3), 302-324 (2009) Combettes, P.L., Wajs, V.R .: Signal recovery by proximal forward-backward splitting.Multiscale Modeling & Simulation 4 (4), 1168-1200 (2005) Nagano, K., Kawahara, Y., Aihara, K .: Size-constrained submodular minimization through minimum norm base. In: Proc. Of ICML. Pp. 977-984 (2011) Liu, J., Ji, S., Ye, J .: SLEP: Sparse Learning with Efficient Projections.Arizona State University (2009),

  As prior knowledge regarding parameters, a case is assumed in which information such as a higher-order structure, that is, a set of parameters belonging to the same group, is used for regularization. However, prior knowledge that can be used for generalized joint regularization is limited only to the adjacency relationship, so a higher-order structure cannot be used. For this reason, sufficient performance may not be obtained for data having parameters having a group structure.

  The present invention has been made to solve the above-described problems, and an object of the present invention is to provide an analysis apparatus, method, and program capable of accurately analyzing data having a group structure.

In order to achieve the above object, an analysis apparatus according to a first invention is an analysis apparatus for predicting a real scalar value y with respect to observation data x, and is a data point comprising a combination of observation data x and real scalar value y. The degree of affiliation of each dimension of each parameter of the parameter β, which is a d-dimensional vector for predicting the real scalar value y for the observation data x, the training data that is a set of the training data, the observation data x, and Representing the parameter structure data representing, the slope ∇l of the error term l for each of the data points of the training data in the loss function for estimating the parameter β, and the R regularization terms Ω _{r in} the loss function A data input unit that accepts a function ∇Ω _r that minimizes each, the training data, the gradient ∇l of the error term l, and each of the R regularization terms Ω _r On the basis of a function ∇Ω _r that minimizes each of the training data, the error term l for each of the data points of the training data, the R regularization terms Ω _r, and for each group, the parameter β A parameter estimation unit that estimates the parameter β so as to minimize the loss function including a higher-order coupled regularization term expressed using a difference in element values between dimensions belonging to the group in A prediction unit that predicts a real scalar value y for the test data based on the parameter β estimated by the parameter estimation unit.

In the analysis apparatus according to the first invention, the parameter structure data further includes a dimension pair similarity of the parameter β, and the parameter estimation unit includes the training data and the gradient ∇l of the error term l. And the error term l for each of the data points of the training data, and the R regularization terms, based on and the function ∇Ω _r that minimizes each of the R regularization terms Ω _r Minimize the loss function including Ω _r and the generalized higher order regularization term including the higher order joint regularization term and the generalized joint regularization term expressed using the similarity of the dimension pairs of the parameter β. Alternatively, the parameter β may be estimated.

In the analysis apparatus according to the first invention, the parameter estimation unit includes an error term parameter estimation unit that estimates the parameter β based on the gradient ∇l of the error term l, and the error term parameter estimation unit. A regularization term parameter estimator for estimating the parameter β based on the estimated parameter β and a function ∇Ω _r that minimizes each of the R regularization terms Ω _r , and the regularization term A higher-order coupled regularization term parameter estimation unit that estimates the parameter β based on the parameter β estimated by the parameter estimation unit and the higher-order coupling regularization term, and the estimation by the error term parameter estimation unit, The estimation by the regularization term parameter estimation unit and the estimation by the higher-order coupled regularization term parameter estimation unit may be performed at least once. .

In the analysis apparatus according to the first invention, the parameter estimation unit includes an error term parameter estimation unit that estimates the parameter β based on the gradient ∇l of the error term l, and the error term parameter estimation unit. A regularization term parameter estimator for estimating the parameter β based on the estimated parameter β and a function ∇Ω _r that minimizes each of the R regularization terms Ω _r , and the regularization term A generalized higher-order coupled regularization term parameter estimation unit that estimates the parameter β based on the parameter β estimated by the parameter estimation unit and the generalized higher-order coupling regularization term, and the error term parameter estimation Estimation by the regular part, estimation by the regularization term parameter estimation unit, and estimation by the generalized higher order coupled regularization term parameter estimation unit at least once. You may make it.

  In the analysis apparatus according to the first invention, the higher-order coupled parameter estimation unit is predetermined corresponding to the parameter β estimated by the regularization term parameter estimation unit and the higher-order coupled regularization term. The parameter β may be estimated according to the parametric maximum flow algorithm based on the s / t graph.

  In the analysis apparatus according to the first aspect of the present invention, the generalized higher order coupled regularization term parameter estimation unit includes the parameter β estimated by the regularization term parameter estimation unit and the generalized higher order coupled regularization term. Correspondingly, the parameter β may be estimated according to a parametric maximum flow algorithm based on a predetermined s / t graph.

The analysis apparatus according to the second aspect of the present invention provides each group of training data that is a set of data points composed of observation data x and each dimension of parameter β that is a d-dimensional vector for analyzing observation data x. Parameter structure data representing the degree of membership in the data, the slope ∇l of the error term l for each of the data points of the training data in the loss function for estimating the parameter β, and R regulars in the loss function A data input that accepts a function ∇Ω _r that minimizes each of the term Ω _r, the training data, the slope ∇ l of the error term l, and each of the R regularization terms Ω _r based on the function ∇Omega _r of reduction, and the error term l for each of the data points of the training data, wherein the R-number of regularization term Omega _r, for each group, in the parameter beta, the Guru A parameter estimator for estimating the parameter β so as to minimize the loss function including a higher-order coupled regularization term expressed using a difference in element values between dimensions belonging to It is configured.

In the analysis apparatus according to the second invention, the parameter structure data further includes a dimension pair similarity of the parameter β, and the parameter estimation unit includes the training data and the gradient ∇l of the error term l. And the error term l for each of the data points of the training data, and the R regularization terms, based on and the function ∇Ω _r that minimizes each of the R regularization terms Ω _r Minimize the loss function including Ω _r and the generalized higher order regularization term including the higher order joint regularization term and the generalized joint regularization term expressed using the similarity of the dimension pairs of the parameter β. Alternatively, the parameter β may be estimated.

An analysis method according to a third invention is an analysis method in an analyzer for predicting a real scalar value y with respect to observation data x, wherein the data input unit is a data point comprising a combination of the observation data x and the real scalar value y. The degree of affiliation of each dimension of each parameter of the parameter β, which is a d-dimensional vector for predicting the real scalar value y for the observation data x, the training data that is a set of the training data, the observation data x, and Representing the parameter structure data representing, the slope ∇l of the error term l for each of the data points of the training data in the loss function for estimating the parameter β, and the R regularization terms Ω _{r in} the loss function Receiving a function ∇Ω _r that minimizes each, and a parameter estimator, wherein the training data, the slope ∇l of the error term l, Based each of the R regularization term Omega _r in the function ∇Omega _r that minimizes, and the error term l for each of the data points of the training data, and wherein the R regularization term Omega _r For each group, the parameter β so as to minimize the loss function including a higher-order coupled regularization term represented using a difference in element values between dimensions belonging to the group in the parameter β. a step of estimating β, and a step of predicting a real scalar value y for the test data based on the parameter β estimated by the parameter estimation unit. .

In the analysis method according to the third aspect of the invention, the parameter structure data further includes the similarity of the dimension pair of the parameter β, and the step of the parameter estimation unit estimating includes the training data and the error term l. , And the error term l for each of the data points of the training data, and the R pieces, based on the slope ∇l of and the function ∇Ω _r that minimizes each of the R regularization terms Ω _r A regularized term Ω _r of the above, a higher-order coupled regularization term, and a generalized higher-order coupled regularization term including a generalized coupled regularization term expressed using the similarity of the dimension pairs of the parameter β The parameter β may be estimated so as to minimize the loss function.

Further, in the analysis method according to the third aspect of the invention, the step of estimating the parameter estimation unit includes the step of the error term parameter estimation unit estimating the parameter β based on the gradient ∇l of the error term l; regularization term parameter estimation unit, and the parameter β estimated by the error term parameter estimator, based on the function ∇Omega _r that minimizes each of the R number of regularization term Omega _r, the parameter β And a step in which a higher-order coupled regularization term parameter estimation unit estimates the parameter β based on the parameter β estimated by the regularization-term parameter estimation unit and the higher-order coupling regularization term. And the estimation by the error term parameter estimation unit, the estimation by the regularization term parameter estimation unit, and the higher-order coupled regularization term parameter estimation The estimation by the fixed unit may be performed at least once.

  In the analysis method according to the third aspect of the present invention, the step of estimating by the higher order coupled parameter estimation unit corresponds to the parameter β estimated by the regularization term parameter estimation unit and the higher order coupled regularization term. The parameter β may be estimated according to a parametric maximum flow algorithm based on a predetermined s / t graph.

  A program according to a fourth invention is a program for causing a computer to function as each part of the analysis device according to the first or second invention.

According to the analysis apparatus, method and program of the present invention, based on the training data, the slope ∇l of the error term l, and the function ∇Ω _r that minimizes each of the R regularization terms Ω _r , Expressed using the error term l for each of the data points of the training data, R regularization terms Ω _r, and for each group, the difference in element values between the dimensions belonging to the group in the parameter β. By estimating the parameter β so as to minimize a loss function including a higher-order coupled regularization term, data having a group structure can be analyzed with high accuracy.

It is a block diagram which shows the structure of the analyzer which concerns on the 1st Embodiment of this invention. It is a figure which shows an example at the time of constructing an s / t graph. It is a flowchart which shows the analysis process routine in the analyzer which concerns on the 1st Embodiment of this invention. It is a block diagram which shows the structure of the analyzer which concerns on the 2nd Embodiment of this invention. It is a figure which shows an example at the time of constructing an s / t graph. It is a block diagram which shows the structure of the analyzer which concerns on the 3rd Embodiment of this invention. It is a block diagram which shows the structure of the analyzer which concerns on the 4th Embodiment of this invention. It is a figure which shows an example of the result of the non-overlapping conditions in an experiment example. It is a figure which shows an example of the result of the overlapping conditions in an experiment example. It is a figure which shows an example of the true value in an example of an experiment, an observed value, and an estimated value.

  Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.

<Principle according to the embodiment of the present invention>

  First, the principle in the embodiment of the present invention will be described.

In the embodiment of the present invention, a proposal for a higher-order coupled regularization term and an analysis apparatus to which the minimization method is applied are proposed. The higher-order coupled regularization term is proposed as a Robust extension of the robust ^Pn model described in Non-Patent Document 5. Furthermore, an efficient minimization method for higher-order coupled regularization terms is shown using the fact that the robust ^Pn model is a submodular function.

The observation data is assumed to be an M-dimensional real vector x and a teacher data real scalar value y. The training data is a set of N data points {(x _n , y _n )} _{n = 1} ^N , and the test data is a set of N ′ data points {(x _{n ′} )} _{n ′ = 1} ^{N ′} To do. The loss function of supervised learning with regularization is formulated as the following equation (1) using the d-dimensional real vector β as a parameter.

At this time, l (x _n , y _n ) is an error term for each data point, and Ω (β) is a regularization term. Also, the regularization term Ω (β) is

It is expressed. Here, Ω _r is R regularization terms, λ _r is a hyperparameter to the regularization term Ω _r , Ω _ho (β) is a higher-order coupled regularization term described later, and λ _ho is , A hyperparameter for the higher-order coupled regularization term Ω _ho .

Loss function regularization with unsupervised learning is formulated into the following equation (2) so without a y _n.

Regularized supervised learning and regularized unsupervised learning are problems for obtaining a parameter β ^* that minimizes the loss function shown in the following equation (3).

The parameter β ^* is estimated by alternately minimizing the error term and the regularization term (see Non-Patent Document 6 above). In supervised learning, the predicted value {(y _{n ′} )} _{n ′ = 1} ^{N ′} of the test data is calculated by the prediction function f (β ^* ; x _{n ′} ).

In the embodiment of the present invention, as a new structural regularization term, one of Ω (β) is proposed as a higher order coupled regularization term Ω _ho (β) and a parameter for minimizing the higher order coupled regularization term Propose estimation and adapt to machine learning problems.

<Configuration of analysis apparatus according to first embodiment of the present invention>

  Next, the configuration of the analysis apparatus according to the first embodiment of the present invention will be described. As shown in FIG. 1, the analysis device 100 according to the first embodiment of the present invention includes a CPU, a RAM, and a ROM that stores a program and various data for executing an analysis processing routine described later. It can be configured with a computer including. Functionally, the analysis apparatus 100 includes an input unit 10, a calculation unit 20, and an output unit 50 as shown in FIG.

The input unit 10 includes training data, test data, parameter structure data, an error term l, a slope ｌl of the error term l for each of the data points of the training data in the loss function for estimating the parameter β, and Lipsitz of the error term. Constant L, R regularization terms Ω _r (r = 1,..., R), and a function ∇Ω _r (r = 1,..., R) that minimizes each of the R regularization terms Ω _r in the loss function. ), The prediction function f, the number of repeated operations P, the hyper parameter α, and the hyper parameter γ are read.

The training data is a set of N data points {(x _n , y _n )} _{n = 1} ^N consisting of a combination of the observation data x and the real scalar value y. The test data is a set {(x _n )} _{n = 1} ^{N ′} of ^{N ′} observation data x.

The parameter structure data is c indicating the degree of affiliation of each dimension of the parameter β, which is a d-dimensional vector for predicting the real scalar value y with respect to the observation data x, shown in the following equation (4), to each group k. ₀ ^k and c ₁ ^k .

Parameter structure data is K _c ^{0 k} in group k in number, and _c ^{1 k,} _c ^{0 k,} and _c ^{1 k} at k, the value of each dimension element of the parameter β in the group k is the , The degree of being the same as the true value in the group k. G _k is a set of dimensions of the parameter β belonging to the k-th group. The parameter structure data further includes parameters θ ₀ ^k , θ ₁ ^k , and θ _max ^k for controlling the number of elements having the same value as the true value in group k.

  The calculation unit 20 includes a parameter estimation unit 30 and a prediction unit 40.

The parameter estimation unit 30 includes training data, a slope ∇l of the error term l, a function ∇Ω _r that minimizes each of the R regularization terms Ω _r , a Lipschitz constant L of the error term, and a hyperparameter α. , Γ, the error term l for each of the data points of the training data, the R regularization terms Ω _r, and the elements between the dimensions belonging to group k in parameter β for each group k The parameter β is estimated so as to minimize the loss function including the higher-order coupled regularization term expressed using the difference between the values of.

Specifically, the parameter estimation unit 30 includes an initialization unit 32, an error term parameter estimation unit 34, a regularization term parameter estimation unit 36, and a higher-order coupled regularization term parameter estimation unit 38 described below. It is configured to include. The parameter estimation unit 30 performs estimation of the error term parameter estimation unit 34, the regularization term parameter estimation unit 36, and the higher-order coupled regularization term parameter estimation unit 38 at least once. In the present embodiment, the parameter β ^* obtained by repeatedly estimating the number of repetition operations P received by the input unit 10 is output to the prediction unit 40.

Initialization unit 32 generates the uniform random initial value beta ₀ parameter beta.

The error term parameter estimation unit 34 is the p−1th time estimated by the gradient ∇l of the error term l, the Lipschitz constant L of the error term, the initial value β ₀ of the parameter β or the higher-order coupled regularization term parameter estimation unit 38. The parameter β _p ^{^} is estimated based on the parameter estimated value β _p−1 of Here, according to the method described in Non-Patent Document 6, the error term is estimated using the initial value β ₀ or the (p−1) th parameter estimated value β _p−1 as shown in the following equation (5). Obtain the value β _p ^{^} .

The regularization term parameter estimation unit 36 determines the parameter β based on the parameter β _p ^ estimated by the error term parameter estimation unit 34 and the function ∇Ω _r that minimizes each of the R regularization terms Ω _r. to estimate the _p ^~. Here, by using β _p ^{^} obtained by the error term parameter estimation unit 34 and a function ∇Ω _r that minimizes each of the first regularization terms Ω _r , an estimated value β _p (1 ) to give ^~, estimate beta _{p (1} parameter) ^- and, second each regularization term Omega _r by using the function ∇Omega _r that minimizes the estimated value of the parameter beta _{p (2} ) Get ^~ . Similarly, using the parameter estimate β _p (r−1) ^˜ and the function ∇Ω _r that minimizes each of the second regularization terms Ω _r , the parameter estimate β _p (2) ^˜ Get. Here, β _p ^˜ (0) = β _p ^{^,} and the operation shown in the following equation (6) is repeated R times.

The regularization term parameter estimation unit 36, the result of repeated R times, β _p ^~ = β _p ^~ a (R).

Higher-order bond regularization term parameter estimation unit 38, the parameter beta _p and ^~ estimated by the regularization term parameter estimation unit 36, based on the higher-order bond regularization term Omega _{ho (beta),} to estimate the parameters beta _p.

Specifically, first, the higher-order coupled regularization term is formulated as in the following equation (7). Below, β = β _p and ^- for the sake of simplicity.

At this time, j _s ^k and j _t ^k are

It is.

Here, the higher-order coupled regularization term corresponds to the Robust extension of the robust ^Pn model of Non-Patent Document 5, which is a submodular function. Therefore, the estimation of the parameter β related to the higher-order coupled regularization term is performed by the methods described in Non-Patent Document 4 and Non-Patent Document 7, similarly to Non-Patent Document 2.

Next, in order to estimate the parameter β related to the higher-order coupled regularization term, an s / t graph determined corresponding to the higher-order coupled regularization term Ω _ho (β) is constructed as shown in FIG. In s / t graph, s is the start node, t is the end point _{node, {v 1, ..., v} d} are nodes corresponding to each dimension of parameter ^{_{β, U s = {u s}} 1, ..., u s K} , U _t = {u _t ¹ ,..., U _t ^K } are hypernodes corresponding to group k.

The higher-order coupled regularization term parameter estimation unit 38 uses the parametric maximum flow algorithm described in Non-Patent Document 4 based on the parameters β _p ^˜ estimated by the regularization term parameter estimation unit 36 and the s / t graph. Then, while changing the value of the hyper parameter α, the parameter β _p is estimated by searching for a path that maximizes the flow from the start node to the end node.

The parameter estimation unit 30 calculates the estimated value β _p of the parameter obtained by repeating the estimation by the error term parameter estimation unit 34, the regularization term parameter estimation unit 36, and the higher-order coupled regularization term parameter estimation unit 38 P times. The parameter β ^* formulated by the equation (3) is output to the prediction unit 40.

The prediction unit 40 predicts a real scalar value y for the test data based on the parameter β ^* estimated by the parameter estimation unit 30 and the prediction function f. Here, as shown in the following equation (8), using the parameter β ^* estimated by the parameter estimation unit 30 and the prediction function f, the test data {(x _n )} _{n = 1} ^{N ′ is a} predicted value { (Y _{n ^} )} _{n = 1} ^{N ′} is calculated, and the calculation result is output to the output unit 50.

<Operation of the analyzing apparatus according to the first embodiment of the present invention>

Next, the operation of the analysis apparatus 100 according to the first embodiment of the present invention will be described. In the input unit 10, training data, test data, parameter structure data, error term l, error term l slope ∇l, error term Lipschitz constant L, R regularization terms Ω _r , R regularization in loss function When the function ∇Ω _r that minimizes each of the terms Ω _r , the prediction function f, the number of iterations P, the hyper parameter α, and the hyper parameter γ are read, the analysis apparatus 100 executes the analysis processing routine shown in FIG. .

First, in step S100, as p = 1, the initial value beta ₀ parameter beta for p = 0 generated by uniform random numbers.

Next, in step S102, the gradient ∇l error term l, and Lipschitz constant L of the error term, the parameter parameter estimates p-1 th estimated by the step S106 to the initial value beta ₀ or below described beta beta _p Based on ₋₁ , the parameter β _p ^{^} is estimated according to the above equation (5).

In step S104, based on the parameter β _p ^ estimated in step S102 and the function ∇Ω _r that minimizes each of the R regularization terms Ω _r , the parameters β _p ^~ Is estimated.

In step S106, based on the parameter β _p ^~ estimated in step S104 and the s / t graph defined corresponding to the higher-order coupled regularization term Ω _ho (β) formulated in the above equation (7). Then, the parameter β _p is estimated by searching for a path that maximizes the flow from the start node to the end node while changing the value of the hyperparameter α by the parametric maximum flow algorithm described in Non-Patent Document 4 above. To do.

  In step S108, it is determined whether the processes in steps S102 to S106 have been repeated P times. If the process has been repeated P times, the process proceeds to step S112. If the process has not been repeated P times, the process proceeds to step S110.

  In step S110, it sets p = p + 1, returns to step S102, and repeats the process of steps S102-S106.

In step S112, the estimated value β _p of the parameter obtained as a result of steps S102 to S108 is output to the prediction unit 40 as the parameter β ^* formulated by the above equation (3).

In step S114, the real scalar value y for the test data is predicted based on the parameter β ^* obtained in step S110 and the prediction function f, the prediction result is output to the output unit 50, and the analysis processing routine is terminated. .

As described above, according to the analysis apparatus according to the first embodiment, the training data, the gradient ∇l of the error term l, and the function ∇Ω that minimizes each of the R regularization terms Ω _r. based on _r , the error term l for each of the data points of the training data, R regularization terms Ω _r, and for each group, the value of the element between the dimensions belonging to the group in the parameter β By estimating the parameter β so as to minimize a loss function including a higher-order coupled regularization term expressed using the difference, and predicting a real scalar value y for the test data based on the parameter β, the group It is possible to predict the real scalar value y for the test data by accurately analyzing the data having a structure.

<Configuration of analysis apparatus according to second embodiment of the present invention>

  Next, the configuration of the analysis apparatus according to the second embodiment of the present invention will be described. The second embodiment is different from the first embodiment in that a loss function including a generalized higher-order coupled regularization term is used. In addition, the same code | symbol is attached | subjected about the location similar to 1st Embodiment, and description is abbreviate | omitted.

  As shown in FIG. 4, the analysis device 200 according to the second embodiment of the present invention includes an input unit 210, a calculation unit 220, and an output unit 50.

The input unit 210 includes training data, parameter structure data, an error term l, a slope ∇l of the error term l for each of the data points of the training data in the loss function for estimating the parameter β, a Lipschitz constant L of the error term, R regularization terms Ω _r (r = 1,..., R), a function ∇Ω _r (r = 1,..., R) that minimizes each of the R regularization terms Ω _r in the loss function, and repetition The operation number P, the hyper parameter α, and the hyper parameter γ are read. In the following, each data will be described with respect to differences from the first embodiment.

The parameter structure data includes c ₀ ^k and c ₁ representing the degree of affiliation of each dimension of the parameter β, which is a d-dimensional vector for analyzing the observation data x shown in the above equation (4), to each group k. ^k . The parameter structure data further includes a graph matrix W having a dimension of the parameter β as a node and a similarity with respect to a dimension pair as an edge.

  The calculation unit 220 includes a parameter estimation unit 230 and a prediction unit 40.

The parameter estimation unit 230 includes training data, a slope ∇l of the error term l, a function ∇Ω _r that minimizes each of the R regularization terms Ω _r , a Lipschitz constant L of the error term, and a hyper parameter α. , Γ and is expressed using the error term l for each of the data points of the training data, the R regularization terms Ω _r , the higher order joint regularization term and the similarity of the dimension pairs of the parameter β. The parameter β is estimated so as to minimize the loss function including the generalized higher order combined regularization term including the generalized combined regularization term. The parameter estimation unit 30 includes an initialization unit 32, an error term parameter estimation unit 34, a regularization term parameter estimation unit 36, and a generalized higher-order coupled regularization term parameter estimation unit 238. Yes. In the present embodiment, the parameter estimation unit 30 estimates the parameter β for analyzing the observation data x included in the training data, and outputs it to the output unit 50.

Generalized higher order binding regularization term parameter estimating unit 238, based on the parameter beta _p and ^~ estimated by the regularization term parameter estimation unit 36, a generalized higher order binding regularization term Omega _GFL (beta), the parameter beta _p Is estimated.

Specifically, first, the generalized coupled regularization term is Ω _GFL , the higher order coupled regularization term is Ω _HO , and the generalized higher order coupled regularization term is formulated as follows. Below, β = β _p and ^- for the sake of simplicity.

From Non-Patent Document 2, the generalized combined regularization corresponds to the Robust extension of the cut function, which is a submodular function. As in the first embodiment, the higher-order coupled regularization term corresponds to Robust extension of the robust ^Pn model of Non-Patent Document 4 that is a submodular function. Therefore, the generalized higher order regularization is consistent with the Robust extension of the submodular function consisting of the sum of the cut function and the robust ^Pn model.

  From the above, the estimated values of the parameters related to the generalized higher-order coupled regularization term are performed by Non-Patent Document 4 and Non-Patent Document 7, similarly to Non-Patent Document 2.

At this time, the s / t graph is constructed as shown in FIG. In the graph, s is a start node, t is an end node, {v ₁ ,..., V _d } is a node corresponding to each dimension of the parameter, U _s = {u _s ¹ ,..., U _s ^K }, U _t = {U _t ¹ ,..., U _t ^K } are hypernodes corresponding to groups.

The generalized higher-order coupled regularization term parameter estimation unit 238 is based on the parameter β _p ^~ estimated by the regularization term parameter estimation unit 36 and the s / t graph, and the parametric maximum flow described in Non-Patent Document 4 above. the algorithm, while changing the value of the hyper-parameter alpha, flows from a source node to a destination node is by searching the path with the maximum, to estimate parameters beta _p.

The parameter estimation unit 230 obtains an estimated value β _p of the parameter obtained by repeating the estimation by the error term parameter estimation unit 34, the regularization term parameter estimation unit 36, and the generalized higher-order coupled regularization term parameter estimation unit 238 P times. The parameter β ^* formulated by the above equation (3) is output to the prediction unit 40.

  In addition, since it is the same as that of 1st Embodiment about the other structure and effect | action of the analyzer which concerns on 2nd Embodiment, description is abbreviate | omitted.

As described above, according to the analysis apparatus according to the second embodiment, the training data, the gradient ∇l of the error term l, and the function ∇Ω that minimizes each of the R regularization terms Ω _{r. is expressed using} the error term l for each of the data points of the training data, the R regularization terms Ω _r , the higher-order coupled regularization term, and the similarity of the dimension pairs of the parameter β. Estimate the parameter β to minimize a loss function including a generalized higher order regularization term including a generalized combined regularization term, and predict a real scalar value y for the test data based on the parameter β. Thus, it is possible to accurately analyze data having a group structure and predict a real scalar value y for test data.

  In addition, by using prior information on adjacent and higher orders regarding parameters as generalized higher order combined regularization terms, it is possible to improve the quantitative performance of supervised learning.

  In addition, as prior knowledge about parameters, if you want to use two types of prior information of adjacent structure and higher-order structure for regularization, the loss function including generalized higher-order coupled regularization term to use these prior knowledge is minimized. The parameter β is estimated so that the real scalar value y for the test data can be predicted based on the parameter β.

  Further, the parameter β can be estimated by an efficient minimization method using the fact that the generalized higher-order joint regularization is a Robust extension of the submodular function.

<Configuration of analysis apparatus according to third embodiment of the present invention>

  Next, the configuration of an analysis apparatus according to the third embodiment of the present invention will be described. The third embodiment is different from the first embodiment in that unsupervised learning without using teacher data is performed. In addition, the same code | symbol is attached | subjected about the location similar to 1st Embodiment, and description is abbreviate | omitted.

  As shown in FIG. 6, an analysis apparatus 300 according to the third embodiment of the present invention includes a CPU, a RAM, and a ROM that stores a program and various data for executing an analysis processing routine described later. It can be configured with a computer including. Functionally, the analysis apparatus 300 includes an input unit 310, a calculation unit 320, and an output unit 50 as shown in FIG.

The input unit 310 includes training data, parameter structure data, an error term l, a slope ∇l of the error term l for each of the data points of the training data in the loss function for estimating the parameter β, a Lipschitz constant L of the error term, R regularization terms Ω _r (r = 1,..., R), a function ∇Ω _r (r = 1,..., R) that minimizes each of the R regularization terms Ω _r in the loss function, and repetition The operation number P, the hyper parameter α, and the hyper parameter γ are read. In the following, each data will be described with respect to differences from the first embodiment.

The training data is a set of N data points consisting of observation data x {(x _n )} _{n = 1} ^N. Since this embodiment is unsupervised learning, a real scalar value {(y _n )} _{n = 1} ^N is not read.

The parameter structure data includes c ₀ ^k and c ₁ representing the degree of affiliation of each dimension of the parameter β, which is a d-dimensional vector for analyzing the observation data x shown in the above equation (4), to each group k. ^k .

  In the present embodiment, as shown in the above equation (2), the error term l in the loss function is different from that in the first embodiment.

  The calculation unit 320 includes the parameter estimation unit 30.

Parameter estimation unit 30, like the first embodiment, the training data, and slope ∇l error term l, and functions ∇Omega _r that minimizes each of the R regularization term Omega _r, the error Based on the Lipschitz constant L of the term and the hyperparameters α, γ, the error term l for each of the data points of the training data, the R regularization terms Ω _r, and for each group k in the parameter β The parameter β is estimated so as to minimize a loss function including a higher-order coupled regularization term expressed using a difference in element values between dimensions belonging to the group k. In addition, the parameter estimation unit 30 includes an initialization unit 32, an error term parameter estimation unit 34, a regularization term parameter estimation unit 36, and a higher-order coupled regularization term parameter estimation unit 38, as in the first embodiment. And. In the present embodiment, the parameter estimation unit 30 estimates the parameter β for analyzing the observation data x included in the training data, and outputs it to the output unit 50.

  In addition, since the other structure and effect | action of 3rd Embodiment are the same as that of 1st Embodiment, description is abbreviate | omitted.

<Configuration of Analysis Device According to Fourth Embodiment of the Present Invention>

  Next, the configuration of an analysis apparatus according to the fourth embodiment of the present invention will be described. The fourth embodiment is different from the second embodiment in that unsupervised learning without using teacher data is performed. In addition, about the location similar to 2nd Embodiment, the same code | symbol is attached | subjected and description is abbreviate | omitted.

  As shown in FIG. 7, an analysis apparatus 400 according to the fourth embodiment of the present invention includes a CPU, a RAM, and a ROM that stores a program and various data for executing an analysis processing routine to be described later. It can be configured with a computer including. Functionally, the analysis apparatus 400 includes an input unit 410, a calculation unit 420, and an output unit 50 as shown in FIG.

The input unit 410 includes training data, parameter structure data, an error term l, a slope ∇l of the error term l for each of the data points of the training data in the loss function for estimating the parameter β, a Lipschitz constant L of the error term, R regularization terms Ω _r (r = 1,..., R), a function ∇Ω _r (r = 1,..., R) that minimizes each of the R regularization terms Ω _r in the loss function, and repetition The operation number P, the hyper parameter α, and the hyper parameter γ are read. Hereinafter, each data will be described with respect to differences from the second embodiment.

The training data is a set of N data points consisting of observation data x {(x _n )} _{n = 1} ^N. Since this embodiment is unsupervised learning, a real scalar value {(y _n )} _{n = 1} ^N is not read.

The parameter structure data includes c ₀ ^k and c ₁ representing the degree of affiliation of each dimension of the parameter β, which is a d-dimensional vector for analyzing the observation data x shown in the above equation (4), to each group k. ^k . The parameter structure data further includes a graph matrix W having a dimension of the parameter β as a node and a similarity with respect to a dimension pair as an edge.

  In the present embodiment, as shown in the above equation (2), the error term l in the loss function is different from that in the second embodiment.

  The calculation unit 420 includes a parameter estimation unit 230.

Parameter estimation unit 230, similarly to the second embodiment, the training data, and slope ∇l error term l, and functions ∇Omega _r that minimizes each of the R regularization term Omega _r, the error Based on the Lipsitz constant L of the term and the hyperparameters α, γ, an error term l for each of the data points of the training data, R regularization terms Ω _r, and a generalized higher order coupled regularization term The parameter β is estimated so as to minimize the loss function including it. Also, the parameter estimation unit 230 is similar to the second embodiment in that the initialization unit 32, the error term parameter estimation unit 34, the regularization term parameter estimation unit 36, and the generalized higher-order coupled regularization term parameter estimation. Part 238. In the present embodiment, the parameter estimation unit 30 estimates the parameter β for analyzing the observation data x included in the training data, and outputs it to the output unit 50.

  In addition, since the other structure and effect | action of 4th Embodiment are the same as that of 2nd Embodiment, description is abbreviate | omitted.

  In this way, quantitative performance improvement of unsupervised learning can be performed by using adjacent information and higher-order prior information regarding parameters as generalized higher-order coupled regularization terms.

<Experimental example>

  In order to show the effect of the technique according to the first embodiment of the present invention, a linear that is one of supervised learning for an artificially generated data set and a data set published on the Internet. Regression analysis is performed, and quantitative performance evaluation is performed using an index called mean square error shown in the following equation (9).

In the artificially generated data, the dimension of the data and parameters was M = d = 100, and the data was generated under the conditions of 30, 50, 70, 100, and 150 points. Take the linear sum of pre-designed parameters x _n generated by a random number, generated artificially a for y _n thereto was added Gaussian noise. The mean square error for the test data was measured by 10 cross-validations. SGL (Non-Patent Document 8), GFL (Non-Patent Document 2), Lasso (Non-Patent Document 1), and OLS (Non-Patent Document 1) were used as the comparison method.

Two conditions were used for designing the parameters. The first condition is called non-overlapping. Under this condition, the parameters have a total of five group structures, and certain parameters belong to only one group, so that the groups do not overlap. Parameters belonging to the same group were set to have the same true value. The second condition is called overlapping. In this condition, unlike the first setting, parameters belonging to two groups exist so that the groups have overlap. The values of the parameters belonging to the two groups were made to have the same true value as either of the two groups. The other settings were the same as the condition non-overlapping. Note that the values of c _{0, i} ^k , c _{1, i} ^k were 1.0 or 0.0, θ ₀ ^k , θ ₁ ^k were 0.0, and θ _max ^k was 1.0.

  An experiment was conducted under the condition of N from 30 to 150, and the mean square error for the obtained test data is shown in Table 1 below. (a) is the result under non-overlapping, and (b) is the result under overlapping conditions. Bold indicates that there is a statistically significant difference from the mean square error of other methods.

  Under non-overlapping conditions, the present invention and GFL show good performance. Under the overlapping condition, the improvement of the mean square error for the test data was confirmed by the present invention. The present invention showed good performance even when N was smaller than d and overlearning occurred (N = 70, 50, 30). This is because overlearning was avoided by higher order regularization terms.

  Next, parameters (N = 30) estimated from the experiment are shown in FIGS. The line in the figure is the true value of the parameter, and the white circle is the estimated value of the parameter by each method. In the non-overlapping condition of FIG. 8, the present invention and GFL were able to estimate a parameter close to the true value of the parameter. Under the overlapping conditions in FIG. 9, only the method according to the embodiment of the present invention can estimate a parameter close to the true value of the parameter.

  From the above results, the performance of the technique according to the first embodiment of the present invention is effective both when the parameter belongs to a single group and when the parameter belongs to a plurality of groups. It has been shown.

  Next, the result of an experiment is shown using a data set published on the Internet. In this experiment, MovieLens100k, EachMovie, and Book-Crossing (http://grouplens.org) data sets are used to give movies and books from the history data of movies and books viewed by users in the data set. An experiment was conducted to predict the evaluation value. A summary of the data set is shown in Table 2 below.

  Table 3 shows the results of measuring the mean square error for the test data by 10 cross-validations. The technique according to the first embodiment of the present invention shows almost the same or better performance than the existing technique in all settings.

  It was also shown that the performance of the technique according to the first embodiment of the present invention is effective for data recorded in the real world.

  Next, in order to show the effect of the technique according to the second embodiment of the present invention, one of supervised learning is performed on an artificially generated data set and a data set released on the Internet. A linear regression analysis is performed, and quantitative performance evaluation is performed using an index called a mean square error shown in the above equation (9).

  With the artificially generated data, matrix data having 50 rows and columns as shown in FIG. 10A is generated. Divide the matrix into 12 regions (8 rectangles and 3 shapes, stars, circles, and diamonds), and every element in each region takes an integer value between 1 and 12. This integer value is used as test data. Next, noise sampled from a Gaussian distribution with mean 0 and variance 1 is added to this integer value, and element values are lost by random selection to obtain training data. Matrix interpolation is a problem of estimating the true value of missing elements from observed data.

In the experiment, the matrix is vectorized. That is, the parameter dimension is d = 50 ² = 2500. The percentage of missing values was generated under the conditions of p = 0.9, 0.5, 0.7, 0.9. The mean square error for the test data was measured by 10 cross-validations. As a comparison method, GFL (Non-patent Document 2), HOFL (first embodiment), and average value were used.

Note that the values of w _{i, j} , c _{0, i} ^k , c _{1, i} ^k are 1.0 or 0.0, θ ₀ ^k and θ ₁ ^k are 0.0, and θ _max ^k is 1.0. Adjacent structure was given information of adjacent parameters by matrix data, and 8 rectangles and star shape were given to higher order structure. In other words, the circle and rhombus were treated as unknown structures. The mean square error between the estimated value obtained from the experiment and the actual observed value is shown in the following table. Bold type indicates the lowest mean square error.

  Under the condition of p = 0.1, the technique (prop.) and GFL according to the second embodiment of the present invention show good performance. The technique according to the second embodiment of the present invention has good performance even when there are many other missing values and overlearning occurs (p = 0.5, 0.7, 0.9). This is because over-learning was avoided by the generalized higher-order coupled regularization term.

  Next, parameters estimated from the experiment are shown in FIG. FIG. 10 (a) is a true matrix, FIG. 10 (b) is an observed value added with noise due to random loss, and FIG. 10 (c) is a method according to the second embodiment of the present invention. FIG. 10D shows an estimated value, FIG. 10D shows an estimated value for generalized joint regularization, and FIG. 10E shows an estimated value for higher-order joint regularization. It can be confirmed that the method according to the second embodiment of the present invention was able to estimate a parameter closer to the true value than other methods.

  From the above, the effectiveness of the technique according to the second embodiment of the present invention was shown.

  The present invention is not limited to the above-described embodiment, and various modifications and applications can be made without departing from the gist of the present invention.

10, 210, 310, 410 Input unit 20, 220, 320, 420 Operation unit 30, 230 Parameter estimation unit 32 Initialization unit 34 Error term parameter estimation unit 36 Regularization term parameter estimation unit 38 Higher order regularization term parameter estimation unit 238 Generalized higher-order coupled regularization term parameter estimation unit 40 prediction unit 50 output unit 100, 200, 300, 400 analysis device

Claims (11)

An analysis device for predicting a real scalar value y for observation data x,
A training data that is a set of data points consisting of a combination of observation data x and real scalar value y, test data consisting of observation data x, and a d-dimensional vector for predicting real scalar value y for observation data x. The parameter structure data representing the degree of affiliation of each dimension of a certain parameter β to each group, and the slope ∇l of the error term l for each of the data points of the training data in the loss function for estimating the parameter β And a data input unit for receiving a function ∇Ω _r that minimizes each of the R regularization terms Ω _{r in} the loss function;
Based on the training data, the slope ∇l of the error term l, and a function ∇Ω _r that minimizes each of the R regularization terms Ω _r , for each of the data points of the training data. Higher-order joint regularization expressed using the error term l, the R regularization terms Ω _r, and the difference in element values between dimensions belonging to the group in the parameter β for each group A parameter estimator for estimating the parameter β so as to minimize the loss function including a term;
A prediction unit that predicts a real scalar value y for the test data based on the parameter β estimated by the parameter estimation unit;
Analysis device including The parameter structure data further includes a similarity of a dimension pair of the parameter β,
The parameter estimation unit includes:
Based on the training data, the slope ∇l of the error term l, and a function ∇Ω _r that minimizes each of the R regularization terms Ω _r , for each of the data points of the training data. Generalization including the error term l, the R regularization terms Ω _r , the higher-order joint regularization term, and a generalized joint regularization term expressed using the similarity of the dimension pairs of the parameter β The analysis apparatus according to claim 1, wherein the parameter β is estimated so as to minimize the loss function including a higher-order coupled regularization term. The parameter estimation unit includes:
An error term parameter estimator for estimating the parameter β based on the gradient ∇l of the error term l;
Regularization term parameter estimation for estimating the parameter β based on the parameter β estimated by the error term parameter estimation unit and a function ∇Ω _r that minimizes each of the R regularization terms Ω _r And
A higher-order coupled regularization term parameter estimation unit that estimates the parameter β based on the parameter β estimated by the regularization term parameter estimation unit and the higher-order coupled regularization term;
The analysis apparatus according to claim 1, wherein the estimation by the error term parameter estimation unit, the estimation by the regularization term parameter estimation unit, and the estimation by the higher-order coupled regularization term parameter estimation unit are performed at least once. The parameter estimation unit includes:
An error term parameter estimator for estimating the parameter β based on the gradient ∇l of the error term l;
Regularization term parameter estimation for estimating the parameter β based on the parameter β estimated by the error term parameter estimation unit and a function ∇Ω _r that minimizes each of the R regularization terms Ω _r And
A generalized higher order coupled regularization term parameter estimation unit that estimates the parameter β based on the parameter β estimated by the regularization term parameter estimation unit and the generalized higher order combination regularization term;
The analysis apparatus according to claim 2, wherein the estimation by the error term parameter estimation unit, the estimation by the regularization term parameter estimation unit, and the estimation by the generalized higher-order coupled regularization term parameter estimation unit are performed at least once.   The higher order coupled regularization term parameter estimation unit is based on the parameter β estimated by the regularization term parameter estimation unit and an s / t graph predetermined corresponding to the higher order coupled regularization term, The analysis apparatus according to claim 3, wherein the parameter β is estimated according to a parametric maximum flow algorithm.   The generalized higher-order coupled regularization term parameter estimation unit includes the parameter β estimated by the regularization term parameter estimation unit, and an s / t graph determined in advance corresponding to the generalized higher-order coupled regularization term. 5. The analysis apparatus according to claim 4, wherein the parameter β is estimated according to the parametric maximum flow algorithm. Training data that is a set of data points composed of observation data x; parameter structure data that represents the degree of affiliation of each dimension of parameter β, which is a d-dimensional vector for analyzing observation data x, to each group; The slope ∇l of the error term l for each of the data points of the training data in the loss function to estimate the parameter β, and the function ∇ that minimizes each of the R regularization terms Ω _{r in} the loss function. A data input unit for receiving Ω _r ;
Based on the training data, the slope ∇l of the error term l, and a function ∇Ω _r that minimizes each of the R regularization terms Ω _r , for each of the data points of the training data. Higher-order joint regularization expressed using the error term l, the R regularization terms Ω _r, and the difference in element values between dimensions belonging to the group in the parameter β for each group A parameter estimator for estimating the parameter β so as to minimize the loss function including a term;
Analysis device including The parameter structure data further includes a similarity of a dimension pair of the parameter β,
The parameter estimation unit includes:
Based on the training data, the slope ∇l of the error term l, and a function ∇Ω _r that minimizes each of the R regularization terms Ω _r , for each of the data points of the training data. Generalization including the error term l, the R regularization terms Ω _r , the higher-order joint regularization term, and a generalized joint regularization term expressed using the similarity of the dimension pairs of the parameter β The analysis apparatus according to claim 7, wherein the parameter β is estimated so as to minimize the loss function including a higher-order coupled regularization term. An analysis method in an analyzer for predicting a real scalar value y with respect to observation data x,
A data input unit for training data that is a set of data points composed of a combination of observation data x and real scalar value y, test data composed of observation data x, and real scalar value y for observation data x An error term for each of the data points of the training data in the loss function for estimating the parameter β and parameter structure data representing the degree of affiliation of each dimension of the parameter β, which is a d-dimensional vector, to each group receiving a slope ∇l of l and a function ∇Ω _r that minimizes each of the R regularization terms Ω _{r in} the loss function;
A parameter estimator based on the training data, the gradient ∇l of the error term l, and the function ∇Ω _r that minimizes each of the R regularization terms Ω _r ; Expressed using the error term l for each of the points, the R regularization terms Ω _r, and for each group, the difference in element values between the dimensions belonging to the group in the parameter β. Estimating the parameter β so as to minimize the loss function including a higher order coupled regularization term,
A predicting unit predicting a real scalar value y for the test data based on the parameter β estimated by the parameter estimating unit;
Analysis method including The parameter structure data further includes a similarity of a dimension pair of the parameter β,
The step of the parameter estimation unit estimating includes:
Based on the training data, the slope ∇l of the error term l, and a function ∇Ω _r that minimizes each of the R regularization terms Ω _r , for each of the data points of the training data. Generalization including the error term l, the R regularization terms Ω _r , the higher-order joint regularization term, and a generalized joint regularization term expressed using the similarity of the dimension pairs of the parameter β The analysis method according to claim 9, wherein the parameter β is estimated so as to minimize the loss function including a higher-order coupled regularization term.   The program for functioning a computer as each part of the analyzer of any one of Claims 1-8.