JP7017528B2 - Learning equipment, learning methods and learning programs - Google Patents

Description

The present invention relates to learning devices, learning methods and learning programs that are resistant to data poisoning.

One of the threats to supervised learning is a data poisoning attack that mixes malicious data into training data. As a countermeasure against this attack, there is a learning algorithm called TRIM (see, for example, Non-Patent Document 1).
In general supervised learning, when learning a model that represents the correspondence between inputs and outputs from training data, the parameters of the model that minimizes the loss function are determined by solving the optimization problem. On the other hand, in TRIM, in order to minimize the influence of data poisoning, the number of normal training data out of N training data mixed with malignant data is set to n (<N) and the optimization problem is solved. Determine the parameters of the model. Specifically, in TRIM, by alternately optimizing the training data and the parameters of the model by the alternate minimization method, n training data that minimize the loss function are extracted from the N training data. At the same time, determine the parameters of the model that minimizes the loss function.

M. Jagielski et al. , "Manipulating Machine Learning: Poisoning Attacks and Countermeasures for Regression Learning," IEEE S & P 2018.

In matrix factorization-based collaborative filtering, the evaluation matrix for items by multiple users is used as training data, and the user factor matrix and item factor matrix that minimize the loss function are derived as latent models. In a data poisoning attack against collaborative filtering, an attacker improperly evaluates an item while pretending to be a legitimate user, thereby mixing malicious data into the evaluation data. Therefore, as a countermeasure against data poisoning attacks, it is desirable to eliminate malicious data on a user-by-user basis rather than on a data-by-data basis.

When the above-mentioned TRIM is applied to matrix factorization-based collaborative filtering, first, n users are selected, and a user factor matrix and an item factor matrix are selected using the corresponding evaluation matrix. Then, using the selected user factor matrix and item factor matrix, n users who minimize the loss function are selected.
However, when learning is performed using the evaluation matrix of some users, the user factor matrix does not include the information of other users. Further, the loss function of matrix factorization is expressed by the Frobenius norm of the difference between the evaluation matrix and the product of the user factor matrix and the item factor matrix. Therefore, the degree of loss for user evaluation data not included in the user factor matrix is not calculated. Therefore, in TRIM, it was not possible to efficiently obtain n users who minimize the loss function.

An object of the present invention is to provide a learning device, a learning method, and a learning program that can minimize the influence of data poisoning during matrix factorization.

The learning device according to the present invention is a learning device based on a matrix decomposition that decomposes an evaluation matrix into a product of a user factor matrix and an item factor matrix, and when the evaluation matrix and the item factor matrix are fixed, the evaluation matrix, The first matrix derivation unit for deriving the user factor matrix, the user factor matrix, and the item factor matrix are fixed so as to minimize the first loss function having the user factor matrix and the item factor matrix as parameters. When, a partial evaluation matrix obtained by removing a predetermined number of rows from the evaluation matrix, a partial user factor matrix obtained by removing the predetermined number of rows from the user factor matrix, and a second loss function having the item factor matrix as parameters are used. When the second matrix derivation unit for deriving the partial evaluation matrix and the partial user factor matrix and the partial evaluation matrix and the partial user factor matrix are fixed so as to be minimized, the second loss function is minimized. As described above, the second loss function is provided with a third matrix derivation unit for deriving the item factor matrix, and the processing by the first matrix derivation unit, the second matrix derivation unit, and the third matrix derivation unit is performed. Repeat until it converges.

The second loss function may be one in which the evaluation matrix is replaced with the partial evaluation matrix and the user factor matrix is replaced with the partial user factor matrix among the parameters of the first loss function.

The first loss function may be a quadratic Frobenius norm of the difference between the evaluation matrix and the product of the user factor matrix and the item factor matrix.

The learning method according to the present invention is a learning method based on a matrix decomposition that decomposes an evaluation matrix into a product of a user factor matrix and an item factor matrix, and when the evaluation matrix and the item factor matrix are fixed, the evaluation matrix, The first matrix derivation step for deriving the user factor matrix and the user factor matrix and the item factor matrix are fixed so as to minimize the first loss function with the user factor matrix and the item factor matrix as parameters. When, a partial evaluation matrix obtained by removing a predetermined number of rows from the evaluation matrix, a partial user factor matrix obtained by removing the predetermined number of rows from the user factor matrix, and a second loss function having the item factor matrix as parameters are used. When the second matrix derivation step for deriving the partial evaluation matrix and the partial user factor matrix and the partial evaluation matrix and the partial user factor matrix are fixed so as to be minimized, the second loss function is minimized. As described above, the computer repeatedly executes the third matrix derivation step for deriving the item factor matrix until the second loss function converges.

The learning program according to the present invention is a learning program based on a matrix decomposition that decomposes an evaluation matrix into a product of a user factor matrix and an item factor matrix, and when the evaluation matrix and the item factor matrix are fixed, the evaluation matrix, The first matrix derivation step for deriving the user factor matrix and the user factor matrix and the item factor matrix are fixed so as to minimize the first loss function with the user factor matrix and the item factor matrix as parameters. When, a partial evaluation matrix obtained by removing a predetermined number of rows from the evaluation matrix, a partial user factor matrix obtained by removing the predetermined number of rows from the user factor matrix, and a second loss function having the item factor matrix as parameters are used. When the second matrix derivation step for deriving the partial evaluation matrix and the partial user factor matrix and the partial evaluation matrix and the partial user factor matrix are fixed so as to be minimized, the second loss function is minimized. As described above, the third matrix derivation step for deriving the item factor matrix is repeatedly executed by the computer until the second loss function converges.

According to the present invention, the influence of data poisoning can be minimized during matrix factorization.

It is a block diagram which shows the functional structure of the learning apparatus which concerns on embodiment. It is a flowchart which shows the process of the learning apparatus which concerns on embodiment.

Hereinafter, an example of the embodiment of the present invention will be described.
In the learning method according to the present embodiment, the influence of the malignant data is suppressed in the collaborative filtering by matrix factorizing the evaluation matrix mixed with the malignant data into the product of the user factor matrix and the item factor matrix.
It should be noted that the malignant data is assumed to be mixed by a predetermined ratio of malignant users, for example, 20% of the total number of users, and the evaluation data by the predetermined ratio of malignant users is removed from the whole.

Here, M is an evaluation matrix for n items by m regular users. M _{i and j} indicate the evaluation of the j-th column (item) of the i-th row (user) of the evaluation matrix M. However, M is a sparse matrix and includes elements whose evaluation has not been observed. Let Ω be the index set of the elements whose evaluations are observed in the evaluation matrix M. R _Ω (A) is a function that returns A _{i, j} if (i, j) ∈ Ω, and 0 otherwise, given the matrix A.

In matrix factorization-based co-filtering, a user factor matrix U with m rows and k columns that minimizes the quadratic adjugate norm by solving an optimization problem as shown in the following equation (1) or equation (2), for example. , And the item factor matrix V with n rows and k columns is derived. However, _∥A∥F indicates the Frobenius norm of the matrix A.
min _{(U, V)} ∥R _Ω (M-UV ^T ) ∥ _F ² ... (1)
min _{(U, V)} ∥R _Ω (M-UV ^T ) ∥ _F ²
＋ λ {∥U∥ _F2 ^＋ ∥V∥ _F2 } ・ ・ ・ ( ² )

In a data poisoning attack against collaborative filtering, the attacker becomes a legitimate user, fraudulently evaluates items according to the purpose of the attack, and adds malicious evaluation data to the learning system. Let M'be the evaluation matrix for n items by m'malignant users. Let M ⁺ be an evaluation matrix obtained by adding the evaluation matrix M'of a malicious user to the evaluation matrix M of a regular user.

Let M ^* be an evaluation matrix obtained by extracting evaluation data of m users, which is an estimated number of regular users, from the evaluation matrix M ⁺ . Further, U ^* is a user factor matrix for m users included in M ^* .
In the learning method of this embodiment, parameters U ^* and V that minimize the influence of data poisoning are derived by solving the optimization problem shown in the following equation (3), for example.
min _{(M *, U *, V)} R _Ω ( ^{M *} -U ^* VT) ∥ _F ² ... (3)

FIG. 1 is a block diagram showing a functional configuration of the learning device 1 according to the present embodiment.
The learning device 1 is an information processing device (computer) such as a server device or a personal computer, and includes a control unit 10 and a storage unit 20, as well as various data input / output devices and communication devices.

The control unit 10 is a part that controls the entire learning device 1, and realizes each function in the present embodiment by appropriately reading and executing various programs stored in the storage unit 20. The control unit 10 may be a CPU.

The storage unit 20 is a storage area for various programs and various data for making the hardware group function as the learning device 1, and may be a ROM, RAM, flash memory, hard disk (HDD), or the like. Specifically, the storage unit 20 stores a program (learning program) for causing the control unit 10 to execute each function of the present embodiment, an evaluation matrix to be input, various parameter (matrix) values during processing, and the like. do.

The control unit 10 includes a first matrix derivation unit 11, a second matrix derivation unit 12, and a third matrix derivation unit 13. By repeatedly operating these functional units, the control unit 10 derives the partial evaluation matrix M ^* excluding the malignant user, the partial user factor matrix U ^* , and the item factor matrix V with respect to the evaluation matrix M ⁺ . do.

When the evaluation matrix M ⁺ and the item factor matrix V are fixed, the first matrix derivation unit 11 uses the evaluation matrix M ⁺ , the user factor matrix U ⁺ , and the item factor matrix V as parameters as the first loss function (for example, described above). The user factor matrix U ⁺ is derived so as to minimize the equation (1)).
The initial value of the item factor matrix V may be randomly determined.

When the user factor matrix U ⁺ and the item factor matrix V are fixed, the second matrix derivation unit 12 has a partial evaluation matrix M ^* obtained by removing a predetermined number (m') of rows from the evaluation matrix M ⁺ , and a user factor matrix U. To minimize the second loss function (for example, the above equation (3)) with the partial user factor matrix U ^* excluding the predetermined number (m') rows from ⁺ and the item factor matrix V as parameters. A partial evaluation matrix M ^* and a partial user factor matrix U ^* are derived.
The second loss function may be one in which the evaluation matrix M ⁺ is replaced with the partial evaluation matrix M ^* and the user factor matrix U ⁺ is replaced with the partial user factor matrix U ^* among the parameters of the first loss function.

The third matrix derivation unit 13 derives the item factor matrix V so as to minimize the second loss function when the partial evaluation matrix M ^* and the partial user factor matrix U ^* are fixed.

The control unit 10 repeatedly executes the processing by the first matrix derivation unit 11, the second matrix derivation unit 12, and the third matrix derivation unit 13 until the second loss function converges.

FIG. 2 is a flowchart showing the processing of the learning device 1 according to the present embodiment.
The learning device 1 alternately optimizes U ^* and V by solving the above-mentioned optimization problem by using the alternate minimization method. Further, the learning device 1 simultaneously optimizes the U ^* and the evaluation matrix M ^* by using the alternate minimization method when optimizing the U ^* .

In step S1, the control unit 10 randomly determines the initial value of the item factor matrix V.

In step S2, the control unit 10 (first matrix derivation unit 11) fixes the evaluation matrix M ⁺ and the item factor matrix V, and the first loss function ∥ R _Ω ( ^{M +} −U ⁺ VT) ∥ _F ² Select U ⁺ to minimize. However, U ⁺ is a user factor matrix of (m + m') rows and k columns.

In step S3, the control unit 10 (second matrix derivation unit 12) fixes the user factor matrix U ⁺ and the item factor matrix V, and the second loss function ∥ R _Ω ( ^{M *} −U ^* VT) ∥ _F. Select the partial evaluation matrix M ^* and the partial user factor matrix U ^* that minimize ² .

In step S4, the control unit 10 (third matrix derivation unit 13) fixes the partial evaluation matrix M ^* and the partial user factor matrix U ^* , and the second loss function ∥ R _Ω ( ^{M *} −U ^* VT). Select the item factor matrix V that minimizes _F ² .

In step S5, the control unit 10 determines whether or not the value of the ^second loss function R _Ω ( ^{M *} −U ^* VT) ∥ _F2 has converged. If this determination is YES, the process ends. On the other hand, when the determination is NO, the processing returns to step S2, and the control unit 10 performs the processing from step S2 to step S4 with the value of the ^second loss function R _Ω ( ^{M *} -U ^* VT) ∥ _F2 . Repeat until does not change.

When the second loss function R _Ω ( ^{M *} -U ^* VT) ∥ _F ² converges by this processing, the partial evaluation matrix M ^* and the partial user factor matrix U ^* are optimized, and the original evaluation matrix M ⁺ is used. A partial evaluation matrix M ^* from which records considered to be malignant have been removed and a partial user factor matrix U ^* corresponding to this partial evaluation matrix M ^* are obtained.

As described above, according to the present embodiment, the learning device 1 first optimizes the user factor matrix U ⁺ for all users when the evaluation matrix is matrix factorized. Next, the learning device 1 selects m users whose loss function is minimized by using the user factor matrix U ⁺ for all the optimized users, and derives the partial user factor matrix U ^* . Subsequently, the learning device 1 optimizes the item factor matrix V using the partial evaluation matrix M ^* and the partial user factor matrix U ^* .
The learning device 1 optimizes the user factor matrix and the item factor matrix by repeating these series of processes based on the alternating minimization method, and simultaneously optimizes the selected user.
As a result, the learning device 1 can minimize the influence of data poisoning during matrix factorization. The result is matrix factorization-based collaborative filtering that is resistant to data poisoning.

Further, the learning device 1 can improve the processing efficiency by sharing the first loss function and the second loss function. Further, as a common loss function, a learning device is used by using a quadratic Frobenius norm of the difference between the evaluation matrix (or partial evaluation matrix) and the product of the user factor matrix (or partial user factor matrix) and the item factor matrix. 1 can use the existing matrix factorization and co-filtering algorithms.

Although the embodiments of the present invention have been described above, the present invention is not limited to the above-described embodiments. Moreover, the effects described in the above-described embodiments are merely a list of the most suitable effects resulting from the present invention, and the effects according to the present invention are not limited to those described in the embodiments.

The learning method by the learning device 1 is realized by software. When realized by software, the programs that make up this software are installed in the information processing device (computer). Further, these programs may be recorded on a removable medium such as a CD-ROM and distributed to the user, or may be distributed by being downloaded to the user's computer via a network. Further, these programs may be provided to the user's computer as a Web service via a network without being downloaded.

1 Learning device 10 Control unit 11 1st matrix derivation unit 12 2nd matrix derivation unit 13 3rd matrix derivation unit 20 Storage unit

Claims (5)

A learning device based on matrix factorization that decomposes an evaluation matrix into a product of a user factor matrix and an item factor matrix.
When the evaluation matrix and the item factor matrix are fixed, the first user factor matrix is derived so as to minimize the first loss function having the evaluation matrix, the user factor matrix, and the item factor matrix as parameters. Matrix derivation part and
When the user factor matrix and the item factor matrix are fixed, a partial evaluation matrix obtained by removing a predetermined number of rows from the evaluation matrix, a partial user factor matrix obtained by removing the predetermined number of rows from the user factor matrix, and the above. A second matrix derivation unit for deriving the partial evaluation matrix and the partial user factor matrix so as to minimize the second loss function with the item factor matrix as a parameter.
When the partial evaluation matrix and the partial user factor matrix are fixed, a third matrix derivation unit for deriving the item factor matrix is provided so as to minimize the second loss function.
A learning device that repeatedly executes processing by the first matrix derivation unit, the second matrix derivation unit, and the third matrix derivation unit until the second loss function converges. The learning according to claim 1, wherein the second loss function is a parameter of the first loss function in which the evaluation matrix is replaced with the partial evaluation matrix and the user factor matrix is replaced with the partial user factor matrix. Device. The learning device according to claim 2, wherein the first loss function is a quadratic Frobenius norm of the difference between the evaluation matrix and the product of the user factor matrix and the item factor matrix. It is a learning method based on matrix factorization that decomposes the evaluation matrix into the product of the user factor matrix and the item factor matrix.
When the evaluation matrix and the item factor matrix are fixed, the first user factor matrix is derived so as to minimize the first loss function having the evaluation matrix, the user factor matrix, and the item factor matrix as parameters. Matrix derivation step and
When the user factor matrix and the item factor matrix are fixed, a partial evaluation matrix obtained by removing a predetermined number of rows from the evaluation matrix, a partial user factor matrix obtained by removing the predetermined number of rows from the user factor matrix, and the above. A second matrix derivation step for deriving the partial evaluation matrix and the partial user factor matrix so as to minimize the second loss function with the item factor matrix as a parameter.
A third matrix derivation step for deriving the item factor matrix so as to minimize the second loss function when the partial evaluation matrix and the partial user factor matrix are fixed.
Is a learning method in which the computer repeatedly executes the above until the second loss function converges. A learning program based on matrix factorization that decomposes an evaluation matrix into a product of a user factor matrix and an item factor matrix.
When the evaluation matrix and the item factor matrix are fixed, the first user factor matrix is derived so as to minimize the first loss function having the evaluation matrix, the user factor matrix, and the item factor matrix as parameters. Matrix derivation step and
When the user factor matrix and the item factor matrix are fixed, a partial evaluation matrix obtained by removing a predetermined number of rows from the evaluation matrix, a partial user factor matrix obtained by removing the predetermined number of rows from the user factor matrix, and the above. A second matrix derivation step for deriving the partial evaluation matrix and the partial user factor matrix so as to minimize the second loss function with the item factor matrix as a parameter.
A third matrix derivation step for deriving the item factor matrix so as to minimize the second loss function when the partial evaluation matrix and the partial user factor matrix are fixed.
Is a learning program for causing a computer to repeatedly execute the process until the second loss function converges.

Images