[go: up one dir, main page]

WO2019198815A1 - 機械学習システム、機械学習方法、プログラム - Google Patents

機械学習システム、機械学習方法、プログラム Download PDF

Info

Publication number
WO2019198815A1
WO2019198815A1 PCT/JP2019/015973 JP2019015973W WO2019198815A1 WO 2019198815 A1 WO2019198815 A1 WO 2019198815A1 JP 2019015973 W JP2019015973 W JP 2019015973W WO 2019198815 A1 WO2019198815 A1 WO 2019198815A1
Authority
WO
WIPO (PCT)
Prior art keywords
variable
dual
node
unit
machine learning
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2019/015973
Other languages
English (en)
French (fr)
Inventor
健太 丹羽
ウィリム バスティアン クライン
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Nippon Telegraph and Telephone Corp
Victoria University of Wellington
Original Assignee
Nippon Telegraph and Telephone Corp
Victoria University of Wellington
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Nippon Telegraph and Telephone Corp, Victoria University of Wellington filed Critical Nippon Telegraph and Telephone Corp
Priority to US17/047,028 priority Critical patent/US12450524B2/en
Priority to JP2020513461A priority patent/JP7091446B2/ja
Publication of WO2019198815A1 publication Critical patent/WO2019198815A1/ja
Anticipated expiration legal-status Critical
Priority to JP2022037711A priority patent/JP7309004B2/ja
Ceased legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N20/00—Machine learning
    • G06N20/20—Ensemble learning
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G06F17/11—Complex mathematical operations for solving equations, e.g. nonlinear equations, general mathematical optimization problems
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G06F17/18—Complex mathematical operations for evaluating statistical data, e.g. average values, frequency distributions, probability functions, regression analysis
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N20/00—Machine learning

Definitions

  • the present invention relates to a machine learning technique.
  • Fig. 1 illustrates a network system to which this consensus building algorithm is applied.
  • a large number of sensors A-101 eg, microphones, cameras, thermometers
  • the data obtained through the sensor A-101 is accumulated in each of a plurality of node units A-102 (for example, servers and PCs) arranged in a distributed manner.
  • a centralized framework requires a central server and all data needs to be stored on the central server, but when using consensus building algorithms, the central server does not have to exist and the data is What is necessary is to accumulate
  • the data is not limited to data obtained from the sensor A-101, and may be character data obtained from an input device or the Web.
  • the node part A-102 of the network system of FIG. 1 is loosely coupled by the edge A-103, and may not be fully coupled, and some data is exchanged directly or indirectly between the node parts A-102. It should be in a relationship that can be done.
  • There is no restriction on the connection structure of the edge A-103 and it may be a tree structure or a circular / circular structure. However, all the node parts A-102 may be connected directly or indirectly. That is, the connection structure of the edge A-103 may not be a divided structure.
  • the mapping is optimized by exchanging variables generated in the process of learning the mapping between nodes, not the data itself, under the conditions of the network system in FIG. Can be shared, and the response time can be shortened or the amount of data can be reduced.
  • consensus-type edge computing based on convex optimization technology is described.
  • the cost function is limited to a convex function
  • consensus-type edge computing technology already exists.
  • the first is a method based on the Distributed ADMM method (Alternating Direction Method of Multipliers) (for example, see Non-Patent Document 1)
  • the second is a method based on the PDMM method (Primal Dual Method of Multipliers) (for example, Non-Patent Document). 2).
  • DNN is a non-convex cost function and does not enter this framework.
  • ⁇ Distributed ADMM method consensus building algorithm The consensus building algorithm of the Distributed ADMM method is described below.
  • the cost function is limited to the closed true convex function (Closed Proper Convex function).
  • the Distributed ADMM-based consensus building algorithm tries to optimize the whole while updating the main and dual variables.
  • a cost function is generated by sharing the main variables between nodes and consensus building so that they match.
  • FIG. 2 shows a situation where all three types of nodes are connected.
  • the variables are three main variables w 1 , w 2 , w 3 , and six types of dual variables ⁇ 1
  • 2 main variables w 1 ⁇ 1> , w 1 ⁇ 2> , w 2 ⁇ 1> , w 2 ⁇ 2> , w 3 ⁇ 1> , w exchanged between the six types of nodes 3 Consists of ⁇ 2> .
  • j be the dual variable for the j-th node at the i-th node.
  • mapping As an example of mapping, the least squares problem with teacher data is treated.
  • s teacher data
  • x input data (sometimes referred to as “observation data”)
  • w is a weight vector
  • ⁇ be a dual variable. It is assumed that the dimension of the dual variable ⁇ is the same as the dimension of the weight vector w.
  • the meaning of these alphabets with subscripts is the same as the alphabet without subscripts.
  • s i means teacher data like s.
  • ⁇ B ⁇ 1, ..., B ⁇ .
  • B is a predetermined positive integer.
  • B 1.
  • the teacher data s i has the following configuration.
  • x i [x i, 1 , ..., x i, B ] T
  • w i [w i, 1 , ..., w i, B ] T
  • j [ ⁇ i
  • the cost for optimizing the mapping can be expressed by the following true convex closed function f i .
  • f i be the cost function at the i-th node, and search for w that minimizes this.
  • the upper left ⁇ of s i, b indicates that it is obtained by w i, b obtained after learning or during learning.
  • p means Lp norm.
  • w is called the main variable.
  • w j, b ⁇ i> means a main variable of the j-th node accumulated in the i-th node. As will be described later, w j, b ⁇ i> is appropriately updated.
  • This expression is a cost under the condition that maximizes the dual variable ⁇ (the intention that the term applied to ⁇ becomes 0 if the condition that the main variable between nodes matches between connected nodes) This means that the main variable w is optimized so as to minimize the function.
  • the condition that the main variable w matches between connected nodes can be described, for example, in a relationship in which the matrix A is 0 by adding each other.
  • the matrix A can be described by I, ⁇ I, 0 as follows. I is the identity matrix and 0 is the zero matrix.
  • Non-Patent Document 3 p.154-155, if the cost function “f” is a true convex function, the optimization of the original problem of “minimizing the main variable while maximizing the dual variable” The solution agrees with the optimal solution when solving the problem of “maximizing dual variables while minimizing main variables”.
  • Non-Patent Document 2 There is an extended Lagrangian method as a method for solving this problem (for example, see Non-Patent Document 2). This is a method of adding penalty terms to stabilize the optimization process.
  • ⁇ i is a predetermined positive number.
  • w * refers to the point optimized with respect to w.
  • T represents an index of the number of updates.
  • the t + 1 update for the dual variable is performed as follows.
  • T is the number of repetitions, and is a predetermined positive integer.
  • T represents the number of repetitions or transposition of a matrix and a vector.
  • the disadvantages of the consensus building algorithm of the Distributed ADMM method are the following (1) to (4).
  • (1) The convergence rate is low.
  • (4) Transmission rate is slightly high. That is, when there is no statistical bias in the main variable data, the transmission rate tends to be high.
  • PDMM-based consensus building algorithm Next, the PDMM-based consensus building algorithm will be described.
  • a major difference from Distributed ADMM is that it shares not only main variables but also dual variables. As will be described later, a consensus is formed on a pair of dual variables.
  • 2 are three types of pairs ⁇ 1
  • 2 ⁇ 2
  • 3 ⁇ 3
  • 3 ⁇ 3
  • the dual variable physically corresponds to the difference between the main variables at the time of each update.
  • the cost function is limited to a closed true convex function.
  • the cost is as follows.
  • variables are expressed by connecting V nodes.
  • f * is also known to be a closed true convex function when f is a closed true convex function, such a description is made (see, for example, Non-Patent Document 3).
  • the indicating function is also a kind of convex function.
  • the matrix P is an operation of exchanging a pair of dual variables between the i and j-th nodes (permutation P), as shown below, and the indicating function outputs 0 when the dual variables match ( That means lower costs).
  • the problem to be solved consists of two types of convex functions.
  • As a technique for solving such a problem there is an operator division method (see, for example, Non-Patent Document 4). This is a technique that solves problems that are difficult to perform global optimization at once, while optimizing them alternately.
  • the PDMM-based consensus building algorithm using P-R partitioning is as follows.
  • Update the main variable between nodes may be discontinuous (it is not necessary to update every time), and may be executed independently (asynchronously) for each edge.
  • the disadvantages of this PDMM-based consensus building algorithm are (1) to (4) below.
  • (1) In some cases, when there is a difference in the statistical properties between the data sets stored in each node, the result of non-convergence was obtained. However, there is no theoretical guarantee that it will converge even for heterogeneous data sets.
  • (2) In principle, it cannot be applied to non-convex function optimization (including DNN).
  • (3) In terms of exchanging main variables, the confidentiality of information is slightly low. That is, since the main variable may reflect the data characteristic deeply, the statistical characteristic of the data may be obtained by hacking the main variable. (4) High transmission rate. That is, since the main variable and the dual variable are sent, the transmission rate tends to be high.
  • w ⁇ R m (m is an integer of 1 or more)
  • the input of G i is set to a vector, it may be a matrix or tensor. Since the matrix or tensor can be expressed using a vector, hereinafter the input of G i advances the story as a vector.
  • the optimal solution w * (also referred to as the w stop point) of this problem is obtained when the sub-derivative of the cost G includes a 0 vector (zero vector).
  • ⁇ G i represents a sub-derivative of G i .
  • N (i) represents the set of indexes of the node group connected to the i-th node.
  • the problem of consensus building in edge computing is the problem of global optimization by exchanging latent variables and their auxiliary variables (for example, dual variables) instead of exchanging huge amounts of data stored in each node between nodes. .
  • the cost expressed by the convex function at the i-th node is expressed as follows.
  • T represents a transpose
  • p represents an L p norm.
  • U (i) ⁇ 1,..., U (i) ⁇ .
  • This cost F 1, i as input data p 'dimensional vector v i ⁇ R p', so as to output the training data s i, U (i) of pieces of data set (v i, u, s i , u ) is a cost function for the problem of optimizing the latent variable p i (p i ⁇ R p ′ ).
  • the index indicates that the data and the number U (i) differ depending on the node. In general, the data stored in each node is different but may be the same.
  • a set of input data and teacher data is referred to as learning data.
  • m p′V.
  • parallel computing by multiple servers in the same location can be formulated as the same problem as the consensus building problem. For example, it corresponds to a case where models such as speech recognition and image recognition are learned at high speed by performing parallel calculation using a large number of computers.
  • the data set stored in each server is basically the same.
  • the stopping point that minimizes the cost is searched while constraining the value of the latent variable p to be the same between the nodes.
  • j is a p ′ ⁇ p ′ real matrix representing consensus formation. Any matrix can be used as this matrix A i
  • I is the identity matrix
  • Lagrange's undetermined multiplier method is often used.
  • the Lagrangian function L is defined as follows.
  • F 1, i * represents a convex conjugate function of the convex function F 1, i .
  • F 1, i is a convex function
  • F 1, i * is also a convex function
  • Equation (2-4) represents the problem of finding the dual variable ⁇ i, j that minimizes the convex function F 1, i * .
  • equation (2-4) should be solved, but in the form of equation (2-4), the process of updating the latent variable asynchronously for each node is performed. It cannot be realized. Therefore, the lifting process is performed so that the dual variable ⁇ i, j belongs to each node. Specifically, the dual variable ⁇ i
  • FIG. 10A and 10B are diagrams illustrating a state of lifting processing of dual variables.
  • FIG. 10A shows that the variable ⁇ i, j controls the error in consensus building between node i and node j.
  • the i-th latent variable and the j-th latent variable must be updated while being synchronized. Therefore, in order to be able to update the i-th latent variable and the j-th latent variable even asynchronously, the edge that is non-directional in FIG. 10A is rewritten with two directional edges as shown in FIG. 10B. Since these two edges are generated from one non-directional edge, the restriction of matching is necessary, but it is possible to solve the synchronization problem in the variable update.
  • Expression (2-5) is expressed as follows by expressing the variable group written in V using a vector or matrix. Of course, the meaning of the formula does not change and represents the same problem.
  • variable group that is, p i , ⁇ i
  • instruction function F 2 is defined as follows.
  • Applying the matrix P to the vector ⁇ is a process of replacing the dual variables ⁇ i
  • p ⁇ R m is a latent variable
  • ⁇ R m is a dual variable
  • A [a 1 ,..., A n ] T ⁇ R n ⁇ m represents input data.
  • the F 2 may be used L 1 norm as regularization term.
  • F 1 and F 2 are not limited to this.
  • s is teacher data of desired output information.
  • Equation (3-1) The P-R type monotone operator division and the D-R type monotone operator division are expressed by Equation (3-1) and Equation (3-2), respectively.
  • Equations (3-1) and (3-2) it can be seen that by introducing the averaging operator to the P-R type monotone operator division, the D-R type monotone operator division can be obtained.
  • variable update algorithm which is a recursive variable update rule obtained from Equation (3-1) and Equation (3-2), will be described using the consensus building problem in edge computing as an example.
  • This consensus building problem is expressed by replacing ⁇ in the following equation (2-7) with w.
  • the resolvent operator ⁇ 2 and the Cayley operator ⁇ 2 are as follows.
  • Non-Patent Document 2 when the above instruction function F 2 is used, the Cayley operator ⁇ 2 corresponds to the permutation matrix P.
  • Equation (3-5) corresponds to the P-R type monotone operator division of Equation (3-1)
  • Equation (3-6) corresponds to the D-R type monotone operator division of Equation (3-2).
  • T is a variable representing the number of updates.
  • Equation (3-3) includes updating the latent variable p and the dual variable w. As a method for updating these variables, a method described in Non-Patent Document 2 will be described. Equation (3-3) is transformed as follows.
  • F 1 * includes the optimization calculation of the latent variable p
  • the latent variable p is optimized, and after fixing p to the optimum value, a method for deriving the dual variable w is derived.
  • the latent variable p is sequentially optimized (that is, p t + 1 is calculated from p t ), a penalty term for p is calculated in addition to the cost included in F 1 * .
  • Equation (3-8) the third term in argmin on the right side of Equation (3-8) is a penalty term, and ⁇ > 0.
  • penal terms it is possible to perform sequential optimization calculation of the latent variable p.
  • equation (3-4) can be calculated as follows.
  • ⁇ can be calculated without using w.
  • Non-Patent Documents 1 and 2 described above cannot perform machine learning when the cost function is a non-convex function. This is the second problem.
  • the conventional variable update rule is generated based on monotonic operator division using a resolvent operator or a Cayley operator.
  • This conventional variable update rule has a problem that it takes time to converge to an optimal solution in some cases. In other words, there is a problem that it takes time to learn latent variables. This is the third problem.
  • an object of the present invention is to provide a machine learning technique capable of performing machine learning even when the cost function is not a convex function.
  • One aspect of the present invention includes a plurality of node units that machine-learn a mapping using a certain main variable that is common based on respective input data while transmitting / receiving information to / from each other, and originally corresponds to the machine learning.
  • machine learning is performed so as to minimize the surrogate convex function that is the upper bound of the cost function
  • the surrogate convex function is an expression of a linear gradient related to the main variable of the cost function, or It is represented by a first-order gradient equation and a second-order gradient equation for the main variable of the cost function.
  • machine learning can be performed even when the cost function is not a convex function by using a proxy convex function that is an upper bound of the cost function instead of the cost function.
  • FIG. 2 is a block diagram showing a configuration of a latent variable learning device 100.
  • FIG. 3 is a flowchart showing the operation of the latent variable learning device 100.
  • 3 is a block diagram illustrating a configuration of a model learning unit 120.
  • FIG. 3 is a flowchart showing the operation of a model learning unit 120.
  • FIG. 2 is a block diagram showing a configuration of a latent variable learning system 20.
  • FIG. 2 is a block diagram showing a configuration of a latent variable learning device 200.
  • FIG. 3 is a block diagram illustrating a configuration of a model learning unit 220.
  • FIG. 5 is a flowchart showing an operation of a model learning unit 220.
  • 3 is a block diagram illustrating a configuration of a model learning unit 230.
  • FIG. 5 is a flowchart showing the operation of a model learning unit 230.
  • the set of node parts connected to node part i is defined as ⁇ N (i).
  • j for the node part j in the node part i is ⁇ i
  • j, b is ⁇ i
  • f i be the cost function corresponding to the node part i used in machine learning.
  • j is introduced as an auxiliary variable of the dual variable ⁇ i
  • j, b be z i
  • j are the same as ⁇ i
  • j is introduced as an auxiliary variable of the dual variable ⁇ i
  • j, b be y i
  • T is the total number of updates, and is a positive integer, but is not a constant when online learning is assumed.
  • variable group main variable, dual variable, dual auxiliary variable
  • the symbol “ ⁇ ” does not represent the element of the set, but means that the calculation result on the right side is assigned to the left side.
  • PR partitioning is an optimization method that guarantees fast convergence.
  • the optimization z b ⁇ C 2 C 1 z b by PR partition is expressed as follows.
  • Non-Patent Document 2 The proof is published in Non-Patent Document 2 about the fact that the second Cary operator C 2 corresponds to the permutation matrix P. Updating the top dual variable using the resolve operator can be transformed as follows:
  • f * can be expressed as a function of ⁇ .
  • Q XX T.
  • Node j Node i (•) means that the i-th node unit i transmits information “•” to the node unit j.
  • step (5) is replaced with the following calculation, and instead of lowering the convergence, it becomes Douglas Rachford (D-R) partitioning that can expect high stability in the convergence process. Usually 1/2 is used for ⁇ .
  • the update of the above main variables and dual variables uses a general form of cost function.
  • cost function the consensus building algorithm is as follows.
  • step (5) is replaced with the following calculation, and instead of lowering the convergence, it becomes Douglas Rachford (D-R) partitioning that can expect high stability in the convergence process. Usually 1/2 is used for ⁇ .
  • the dual auxiliary variable y is exchanged between the nodes, but the nature of the variable can be said to be equivalent to the dual variable ⁇ .
  • the dual variable is calculated as follows.
  • the main variable w often reflects the statistical properties of the data, but the statistical properties of the dual variables depend on the data after the Legendre transformation. Since Legendre transformation cannot be returned to the main variable without knowing the structure of the function, transmitting a dual variable or its dual auxiliary variable between nodes is a highly confidential data communication.
  • the machine learning system comprises a plurality of nodes portions 1, ..., V, a plurality of sensor portions 1 S1, ..., S ⁇ 1, 2 S1, ..., 2 S ⁇ , V S1, ..., V S ⁇ ,
  • Internet 0 N , LAN 1 N ,..., V N are provided.
  • Each of the plurality of node units 1,..., V is an information processing device such as a server or a PC.
  • each of the node units 1,..., V is provided with a learning unit 10 and a transmission / reception unit 11, and a storage unit 12 is provided in the learning unit 10. It is assumed that the storage unit 12 stores data necessary for processing and calculation described below.
  • Sensor unit 1 S1, ..., S ⁇ 1, 2 S1, ..., 2 S ⁇ , V S1, ..., V S ⁇ a variety of environments (e.g., home, factory, field and buildings) in a number that is arranged in a dispersed Sensors (eg, microphone, camera, thermometer).
  • the sensor units are 1 S1 ,..., 1 S ⁇ are sensors corresponding to the node unit 1. That is, the sensor unit 1 S1 ,..., 1 S ⁇ is a sensor that acquires data used in machine learning in the learning unit 10 of the node unit 1, and each of the sensor units 1 S 1 ,. 1 and LAN 1 N are connected. The same applies to the other sensor units.
  • sensor unit 1 S1, ..., S ⁇ 1, 2 S1, ..., 2 S ⁇ , V S1, ..., data obtained through V S [gamma] has a plurality of nodes portions 1, ..., V (e.g., server, PC) Accumulated in.
  • V S [gamma] is LAN1 N, ..., node unit 1 V N, ..., the V have been, the sensor unit 1 S1, ..., 1 S ⁇ , 2 S1, ..., 2 S ⁇ , V S1, ..., V S ⁇ node unit 1 via the Internet 0 N, ..., be connected to V it may, or may be connected by other connecting means, in short, the sensor unit 1 S1, ..., S ⁇ 1, 2 S1, ..., 2 S ⁇ , V S1, ..., V S ⁇ node unit data obtained is 1, ..., V should just be used.
  • the node parts 1,..., V are connected via the Internet 0 N.
  • the node parts 1, Any relationship that can be exchanged.
  • the edge connection structure There is no restriction on the edge connection structure, and it may be a tree structure or a circular / circular structure. In short, all the node parts 1,..., V are connected directly or indirectly. That is, the edge connection structure is not a divided structure.
  • the plurality of node units 1,..., V receive data from the transmission / reception unit 11, transmit data from the transmission / reception unit 11, read data from the storage unit 12, and write data to the storage unit 12. Perform the machine learning process described.
  • the machine learning process is realized, for example, when the plurality of node units 1,..., V perform the processes from step S1 to step S8 in FIG.
  • the node unit i (more specifically, the learning unit 10 of the node unit i) uses the data obtained by the sensor unit corresponding to the node unit i to update the dual variable based on the following equation (step) S2). That is, the node part i calculates ⁇ i
  • the node unit i (more specifically, the learning unit 10 of the node unit i) updates the main variable based on the following equation (step S3). That is, the node unit i calculates w i, b (t + 1) defined by the following expression for each of i ⁇ ⁇ V, b ⁇ ⁇ B.
  • the process of step S3 is performed when a main variable is required. In other words, the process of step S3 may not be performed every time.
  • the node unit i (more specifically, the learning unit 10 of the node unit i) updates the dual auxiliary variable based on the following equation (step S4). That is, the node part i calculates y i
  • the process of step S4 may not be performed except when the dual auxiliary variable y i
  • the node unit i (more specifically, the transmission / reception unit 11 of the node unit i) transmits a dual auxiliary variable y i
  • the node unit i transmits the dual auxiliary variable y i
  • the transmission / reception unit 11 of the unit i operates so as to input the dual auxiliary variable received from the node unit j to the learning unit 10 of the node unit i as a dual auxiliary variable y j
  • the process of step S5 may not be performed every time or may be asynchronous between nodes. For example, only when t is an even number, all the node parts i transmit the dual auxiliary variable y i
  • At least one node part i and at least one node part j are dual auxiliary variables y i
  • the node part i (more specifically, the learning part 10 of the node part i) updates the dual auxiliary variable based on the following equation (step S6). That is, as i ⁇ ⁇ V, j ⁇ ⁇ N (i), b ⁇ ⁇ B, the node part i becomes z i
  • j, b (t + 1) y j
  • the machine learning system including a plurality of node units each storing input data and machine learning a mapping using the main variable w based on the teacher data and the input data while transmitting / receiving information to / from each other
  • the plurality of node units i perform machine learning so that if the dual variable used in machine learning is optimized, the main variable is also optimized, and not the main variable but the dual variable is transmitted / received to / from each other. Thereby, since a main variable is not transmitted / received between the node parts i, machine learning with higher secrecy than before can be performed.
  • ⁇ Modification> [Modification 1] If you use the following cost function instead of the general cost function,
  • step S2 the node unit i updates the dual variable based on the following equation.
  • step S3 the node unit i updates the main variable based on the following equation.
  • step S5 the node unit i may transmit and receive the dual variable ⁇ i
  • step S6 is not performed. Processing of steps other than step S6 is performed in the same manner as described above. [Modification 4] Below, the device for compressing transmission capacity is demonstrated.
  • the update difference approaches 0 as the optimization process converges. If irreversible compression processing is performed using this property, the transmission capacity should be further reduced.
  • j, b (t + 1) is update difference information.
  • j, b (t + 1) tends to be biased toward a number close to 0 as it converges.
  • j, b (t + 1) is information that is originally desired to be exchanged between nodes.
  • j, b (export) is already obtained reference information.
  • each element constituting v is compared with the threshold value thr, and if it is equal to or less than the threshold value, processing is performed to make it zero.
  • thr is a predetermined number larger than a predetermined 0, and is a very small number such as 1 ⁇ 10 ⁇ 5 .
  • u is generated by performing a process of assigning a symbol according to the appearance probability. For example, u is generated by assigning a short symbol to an appearance probability value.
  • the node unit i may perform the processing from step S9 to step S16 described below instead of the processing from step S5 to step S6. Since other processes are the same as those in the above-described embodiment, a duplicate description is omitted here.
  • FIG. 8 shows a flowchart of an example of a machine learning method in which transmission capacity is reduced.
  • the node unit i (more specifically, the learning unit 10 of the node unit i) updates the reference data based on the following equation (step S10). . That is, the node unit i updates the reference data for each of i ⁇ ⁇ V, j ⁇ ⁇ N (i), b ⁇ ⁇ B based on the following formula (step S10).
  • the node part i (more specifically, the transmission / reception part 11 of the node part i) transmits m i
  • the transmission / reception unit 11 of the node unit i transmits m i
  • the processing shown in the following equation may be performed only for some node portions i, not for all node portions i, j, but only for some node portions j.
  • At least one node part i sends mi i
  • the node part i (more specifically, the learning part 10 of the node part i), for each of i ⁇ ⁇ V, j ⁇ ⁇ N (i), b ⁇ ⁇ B, is expressed as follows:
  • j, b (t + 1) is updated using the information obtained by the exchange (step S12).
  • the node unit i calculates an update difference based on the following equation (step S13). That is, the node part i calculates v i
  • the node unit i (more specifically, the learning unit 10 of the node unit i) performs data for each of i ⁇ ⁇ V, j ⁇ ⁇ N (i), b ⁇ ⁇ B based on the following equations: To generate a code u i
  • This data compression may be irreversible.
  • C means a predetermined compression process such as a flooring-based compression process or an entropy coding-based compression process.
  • the node unit i (more specifically, the transmission / reception unit 11 of the node unit i) transmits u i
  • the node unit i transmits u i
  • the transmission / reception unit 11 operates to input u j
  • the processing shown in the following equation may be performed only for some node portions i, not for all node portions i, j, but only for some node portions j.
  • at least one node part i assigns a code u i
  • i, b (t + 1) output by the node unit j is received (step S15).
  • the node unit i (more specifically, the learning unit 10 of the node unit i) performs dual processing for each of i ⁇ ⁇ V, j ⁇ ⁇ N (i), b ⁇ ⁇ B based on the following formulas.
  • j, b (t + 1) is updated (step S16).
  • the node unit i may update the D-R division base exemplified below. Usually 1/2 is used for ⁇ .
  • the node unit i may perform the D-R division base update exemplified below. Usually 1/2 is used for ⁇ .
  • the machine learning system may be realized by a single computer.
  • the processing contents of the functions that each unit of the machine learning system should have are described by a program.
  • the machine learning system process is realized on the computer.
  • the program describing the processing contents can be recorded on a computer-readable recording medium.
  • a computer-readable recording medium for example, any recording medium such as a magnetic recording device, an optical disk, a magneto-optical recording medium, and a semiconductor memory may be used.
  • each unit may be configured by executing a predetermined program on a computer, or at least a part of these processing may be realized by hardware.
  • the set of node parts connected to node part i is defined as ⁇ N (i).
  • j for the node part j in the node part i is ⁇ i
  • j, b is ⁇ i
  • j is introduced as an auxiliary variable of the dual variable ⁇ i
  • j, b be z i
  • j are the same as ⁇ i
  • j is introduced as an auxiliary variable of the dual variable ⁇ i
  • j, b be y i
  • the b- th element of the main variable w i of the node part i is set to w i, b, and the dual auxiliary variable w i, b after the t-th update is set to w i, b (t) .
  • f i be the cost function corresponding to the node part i used in machine learning
  • ⁇ f i (w i, b (t) ) be the first-order gradient for w i, b (t) of the cost function f i .
  • T is the total number of updates, and is a positive integer, but is not a constant when online learning is assumed.
  • ⁇ be a positive number.
  • f i is called a 1 / ⁇ smoothing function.
  • x and y are arbitrary vectors
  • ⁇ x, y> represents an inner product of x and y.
  • ⁇ the larger the gradient of the convex function on the right side (becomes a sharp function), which satisfies the condition that the cost is an upper bound. For this reason, ⁇ may be a small number. However, if ⁇ is too small, the update step is small, so that it takes time to reach the optimal solution.
  • the solid line represents the original cost function f i .
  • the cost function f i is written as a non-convex function.
  • the alternate long and short dash line represents the surrogate convex function g i that is the upper bound.
  • f i (w i, b (t) ) is a function output at the update time t and can be calculated.
  • ⁇ f i (w i, b (t) ) is the gradient of the function at the update time t, and can be calculated in the framework of probabilistic optimization when DNN is assumed.
  • the proxy function may be other than the above.
  • the above-described surrogate convex function g i represents the upper bound of the original cost, and has an advantage that only the first-order gradient of the cost function needs to be obtained. It is also an advantage that it can be applied to non-convex functions.
  • the following proxy function may be used.
  • the underlined part of the following formula is the surrogate function.
  • the concept of the surrogate convex function is a convex function that does not contradict the minimization of the original cost function, and can be implemented with the idea of upper bounds and approximation. Specifically, it is a convex function that can be calculated using a first-order and possibly a second-order gradient for the main variable of the original cost function.
  • the optimal solution of w is derived by solving the convex conjugate function g * of the function g.
  • This process can be written separately for each node.
  • the symbol “ ⁇ ” does not represent the element of the set, but means that the calculation result on the right side is assigned to the left side.
  • Quadratic PDMM When divided into operations for each node, a variable optimization algorithm can be obtained using a surrogate convex function on a P-R partition basis. This algorithm is also called Quadratic PDMM.
  • the Quadratic PDMM is as follows.
  • step (5) is replaced with the following calculation, and instead of lowering the convergence, it becomes Douglas Rachford (D-R) partitioning that can expect high stability in the convergence process. Usually 1/2 is used for ⁇ .
  • the surrogate convex function changes at every update time, so it can be said that the secrecy is high.
  • g indicates a 1 / ⁇ -strong convex function.
  • 2 is a convex function, it is equivalent to g being a 1 / ⁇ -strong convex function (for example, non-patent (Refer to Section 2.2.5 of Reference 3.)
  • 2 is a convex function, so g will be a 1 / ⁇ -strongly convex function.
  • g * is a ⁇ -smooth function when g is a 1 / ⁇ -strong convex function. At that time, the following properties are satisfied.
  • the proximity mapping function is defined as follows.
  • G is composed of g * which is an ⁇ -smooth function and an indicator function ⁇ having a very strong convexity. Since the indicating function is included in G, it can be said that G is a strong convex function. Assuming G is a ⁇ -strong convex function,
  • the machine learning system comprises a plurality of nodes portions 1, ..., V, a plurality of sensor portions 1 S1, ..., S ⁇ 1, 2 S1, ..., 2 S ⁇ , V S1, ..., V S ⁇ ,
  • Internet 0 N , LAN 1 N ,..., V N are provided.
  • Each of the plurality of node units 1,..., V is an information processing device such as a server or a PC.
  • each of the node units 1,..., V is provided with a learning unit 10 and a transmission / reception unit 11, and a storage unit 12 is provided in the learning unit 10. It is assumed that the storage unit 12 stores data necessary for processing and calculation described below.
  • Sensor unit 1 S1, ..., S ⁇ 1, 2 S1, ..., 2 S ⁇ , V S1, ..., V S ⁇ a variety of environments (e.g., home, factory, field and buildings) in a number that is arranged in a dispersed Sensors (eg, microphone, camera, thermometer).
  • the sensor units are 1 S1 ,..., 1 S ⁇ are sensors corresponding to the node unit 1. That is, the sensor unit 1 S1 ,..., 1 S ⁇ is a sensor that acquires data used in machine learning in the learning unit 10 of the node unit 1, and each of the sensor units 1 S 1 ,. 1 and LAN 1 N are connected. The same applies to the other sensor units.
  • sensor unit 1 S1, ..., S ⁇ 1, 2 S1, ..., 2 S ⁇ , V S1, ..., data obtained through V S [gamma] has a plurality of nodes portions 1, ..., V (e.g., server, PC) Accumulated in.
  • V S [gamma] is LAN1 N, ..., node unit 1 V N, ..., the V have been, the sensor unit 1 S1, ..., 1 S ⁇ , 2 S1, ..., 2 S ⁇ , V S1, ..., V S ⁇ node unit 1 via the Internet 0 N, ..., be connected to V it may, or may be connected by other connecting means, in short, the sensor unit 1 S1, ..., S ⁇ 1, 2 S1, ..., 2 S ⁇ , V S1, ..., V S ⁇ node unit data obtained is 1, ..., V should just be used.
  • the node parts 1,..., V are connected via the Internet 0 N.
  • the node parts 1, Any relationship that can be exchanged.
  • the edge connection structure There is no restriction on the edge connection structure, and it may be a tree structure or a circular / circular structure. In short, all the node parts 1,..., V are connected directly or indirectly. That is, the edge connection structure is not a divided structure.
  • the plurality of node units 1,..., V receive data from the transmission / reception unit 11, transmit data from the transmission / reception unit 11, read data from the storage unit 12, and write data to the storage unit 12. Perform the machine learning process described.
  • the machine learning process is realized, for example, when the plurality of node units 1,..., V perform the processes from step S1 to step S8 in FIG.
  • the node unit i (more specifically, the learning unit 10 of the node unit i) uses the data obtained by the sensor unit corresponding to the node unit i to update the dual variable based on the following equation (step) S2). That is, the node part i calculates ⁇ i
  • the node unit i (more specifically, the learning unit 10 of the node unit i) updates the main variable based on the following equation (step S3). That is, the node unit i calculates w i, b (t + 1) defined by the following expression for each of i ⁇ ⁇ V, b ⁇ ⁇ B.
  • the node unit i (more specifically, the learning unit 10 of the node unit i) updates the dual auxiliary variable based on the following equation (step S4). That is, the node part i calculates y i
  • the process of step S4 may not be performed except when the dual auxiliary variable y i
  • the node unit i (more specifically, the transmission / reception unit 11 of the node unit i) transmits a dual auxiliary variable y i
  • the node unit i transmits the dual auxiliary variable y i
  • the transmission / reception unit 11 of the unit i operates so as to input the dual auxiliary variable received from the node unit j to the learning unit 10 of the node unit i as a dual auxiliary variable y j
  • the process of step S5 may not be performed every time or may be asynchronous between nodes. For example, only when t is an even number, all the node parts i transmit the dual auxiliary variable y i
  • At least one node part i and at least one node part j are dual auxiliary variables y i
  • the node part i (more specifically, the learning part 10 of the node part i) updates the dual auxiliary variable based on the following equation (step S6). That is, as i ⁇ ⁇ V, j ⁇ ⁇ N (i), b ⁇ ⁇ B, the node part i becomes z i
  • j, b (t + 1) y j
  • machine learning in the machine learning system including a plurality of node units that each store input data and machine learn a mapping using the main variable based on the teacher data and the input data while transmitting and receiving information to and from each other.
  • machine learning is performed so as to minimize the surrogate convex function that is the upper bound of the cost function.
  • a machine learning method including a step in which a plurality of node units perform machine learning using a single main variable that is common based on respective input data while transmitting and receiving information to and from each other.
  • the plurality of node units are machine-learned so as to minimize the surrogate convex function that is the upper bound of the cost function, instead of the cost function of the non-convex function that originally corresponds to machine learning.
  • the surrogate convex function is expressed by a linear gradient equation regarding the main variable of the cost function, or a linear gradient equation and a quadratic gradient equation regarding the main variable of the cost function.
  • step S5 the node unit i may transmit and receive the dual variable ⁇ i
  • step S6 is not performed. Processing of steps other than step S6 is performed in the same manner as described above. [Modification 3] Below, the device for compressing transmission capacity is demonstrated.
  • the update difference approaches 0 as the optimization process converges. If irreversible compression processing is performed using this property, the transmission capacity should be further reduced.
  • j, b (t + 1) is update difference information.
  • j, b (t + 1) tends to be biased toward a number close to 0 as it converges.
  • j, b (t + 1) is information that is originally desired to be exchanged between nodes.
  • j, b (export) is already obtained reference information.
  • each element constituting v is compared with the threshold value thr, and if it is equal to or less than the threshold value, processing is performed to make it zero.
  • thr is a predetermined number larger than a predetermined 0, and is a very small number such as 1 ⁇ 10 ⁇ 5 .
  • u is generated by performing a process of assigning a symbol according to the appearance probability. For example, u is generated by assigning a short symbol to an appearance probability value.
  • T interval is a predetermined positive integer.
  • the node unit i may perform the processing from step S9 to step S16 described below instead of the processing from step S5 to step S6. Since other processes are the same as those in the above-described embodiment, a duplicate description is omitted here.
  • FIG. 8 shows a flowchart of an example of a machine learning method in which transmission capacity is reduced.
  • the node unit i (more specifically, the learning unit 10 of the node unit i) updates the reference data based on the following equation (step S10). . That is, the node unit i updates the reference data for each of i ⁇ ⁇ V, j ⁇ ⁇ N (i), b ⁇ ⁇ B based on the following formula (step S10).
  • the node part i (more specifically, the transmission / reception part 11 of the node part i) transmits m i
  • the transmission / reception unit 11 of the node unit i transmits m i
  • the processing shown in the following equation may be performed only for some node portions i, not for all node portions i, j, but only for some node portions j.
  • At least one node part i sends mi i
  • the node part i (more specifically, the learning part 10 of the node part i), for each of i ⁇ ⁇ V, j ⁇ ⁇ N (i), b ⁇ ⁇ B, is expressed as follows:
  • j, b (t + 1) is updated using the information obtained by the exchange (step S12).
  • the node unit i calculates an update difference based on the following equation (step S13). That is, the node part i calculates v i
  • the node unit i (more specifically, the learning unit 10 of the node unit i) performs data for each of i ⁇ ⁇ V, j ⁇ ⁇ N (i), b ⁇ ⁇ B based on the following equations: To generate a code u i
  • This data compression may be irreversible.
  • C means a predetermined compression process such as a flooring-based compression process or an entropy coding-based compression process.
  • the node unit i (more specifically, the transmission / reception unit 11 of the node unit i) transmits u i
  • the node unit i transmits u i
  • the transmission / reception unit 11 operates to input u j
  • the processing shown in the following equation may be performed only for some node portions i, not for all node portions i, j, but only for some node portions j.
  • at least one node part i assigns a code u i
  • i, b (t + 1) output by the node unit j is received (step S15).
  • the node unit i (more specifically, the learning unit 10 of the node unit i) performs dual processing for each of i ⁇ ⁇ V, j ⁇ ⁇ N (i), b ⁇ ⁇ B based on the following formulas.
  • j, b (t + 1) is updated (step S16).
  • the node unit i may update the D-R division base exemplified below. Usually 1/2 is used for ⁇ .
  • the node unit i may perform the D-R division base update exemplified below. Usually 1/2 is used for ⁇ .
  • the machine learning system may be realized by a single computer.
  • the processing contents of the functions that each unit of the machine learning system should have are described by a program.
  • the machine learning system process is realized on the computer.
  • the program describing the processing contents can be recorded on a computer-readable recording medium.
  • a computer-readable recording medium for example, any recording medium such as a magnetic recording device, an optical disk, a magneto-optical recording medium, and a semiconductor memory may be used.
  • each unit may be configured by executing a predetermined program on a computer, or at least a part of these processing may be realized by hardware.
  • _ (Underscore) represents a subscript.
  • xy_z represents that yz is a superscript to x
  • xy_z represents that yz is a subscript to x.
  • Bregman resolvent operator or a Bregman Cary operator is used instead of using a resolvent operator or a Cayley operator. That is, the variable update rule is constructed based on monotone operator division using the Bregman resolvent operator or the Bregman Cary operator. Details will be described below.
  • any narrowly-defined convex function can be used as the function D.
  • the Euclidean distance is also a kind of Bregman divergence. It may also be written as Bregman divergence B D to clarify that Bregman divergence B is defined using function D.
  • the narrowly convex function D is a function having some kind of continuity. Specifically, the narrowly-convex convex function D has properties of strong convex (SC) and Lipschitz smooth (LS). These properties can be expressed as follows. (Characteristic 1) When the second-order Taylor expansion is used, the following approximate expression is established for the function D around the point w.
  • the Hessian matrix H D (w) (H D (w) ⁇ R m ⁇ m ) is a positive definite matrix.
  • the Hessian matrices K D and M D (K D ⁇ R m ⁇ m , M D ⁇ R m ⁇ m ) are positive definite matrices.
  • the following relationship holds with the Hessian matrix H D (w).
  • the Resolvent operator and the Cayley operator are generalized using Bregman divergence.
  • the generalized Resolvent operator and Cary operator are called Bregman Resolvent operator and Bregman Cary operator, respectively.
  • the Bregman Resolvent operator is described in Reference Non-Patent Document 2.
  • Reference Non-Patent Document 2 H. H. Bauschke, J. M. Borwein, and P. L. Combettes, “Bregman Monotone Optimization Algorithms”, SIAM Journal on Control and Optimization, Vol. 42, Issue 2, pp. 596-636, 2003.
  • the Bregman resolvent operator R n and the Bregman Cary operator C n are given by the following equations.
  • Bregman divergence B corresponds to Euclidean distance
  • Bregman Resolvent operator R n and Bregman Cary operator C n are respectively Resolvent operators.
  • ⁇ n corresponding to the Cary operator ⁇ n . This will be specifically described.
  • the subdifferentiation of function D is
  • the Hessian matrix H G_1 (w), K G_1 , M G_1 has the following relationship.
  • Theorem 1 When the function G 1 is SC and LS, the Bregman resolvent operator R 1 has the following convergence rate.
  • ⁇ max, 1 and ⁇ min, 1 included in the equation (4-8) are given by the following equations.
  • ⁇ max represents the maximum eigenvalue
  • ⁇ min represents the minimum eigenvalue.
  • LS (upper bound) and SC (lower bound) of the function G 2 can be expressed as follows using an arbitrary vector h ⁇ R m .
  • Hessian matrices H G_2 (w), K G_2 , and M G_2 have the following relationship.
  • the coefficients ⁇ max, 2 and ⁇ min, 2 are given by the equations (4-18) and (4-19).
  • ⁇ 3 Variable update rule and convergence rate of generalized PR type monotone operator division, generalized DR type monotone operator division >>
  • the PR-type monotone operator partition and the DR-type monotone operator partition are derived by transforming the equation (1-2) using the Bregman resolvent operator and the Bregman-Cary operator.
  • the PR-type monotone operator division and the DR-type monotone operator division described here correspond to the generalization of the PR-type monotone operator division and the DR-type monotone operator division using Bregman divergence.
  • the generalized PR type monotone operator division and the generalized DR type monotone operator division are used.
  • [Generalized PR type monotone operator division] Equation (1-2) is transformed as follows.
  • Equation (4-22) is obtained by replacing the Cary operator in Equation (3-1) with the Bregmann-Cary operator.
  • Equation (4-37) is obtained by replacing the Cayley operator in Equation (3-2) with the Bregman Cayley operator.
  • the inverse matrix of the Hessian matrix H D of the function D is the inverse matrix of the Hessian matrix H G_i of the function G i .
  • equation (4-48) Substituting equation (4-48) into equation (4-1), which is the definition formula for Bregman divergence, yields:
  • the real number ⁇ > 0 corresponds to a parameter that determines the learning step size, and must be selected so that the eigenvalue of the Hessian matrix H D (2GD) is greater than 0 and less than or equal to 1.
  • Equation (4-50) the arithmetic mean is used in (case 2), but a geometric mean may be used instead of the arithmetic mean.
  • Equation (4-50) (formula (4-50 ')) shows that the case 1, has designed a Hessian matrix H D is divided into the case 2.
  • case 2 it is ideal to satisfy equation (4-47) for both functions G 1 and G 2 , but in practice this is difficult to ensure. Therefore, we decided to design Case 2 as shown in Equation (4-50) (Equation (4-50 ')).
  • Equation (4-50 ') The reason why this design is preferable is that the following mathematical properties hold for the Hessian matrix. This will be specifically described. First, to calculate the inverse matrix of the Hessian matrix H D.
  • the real number ⁇ > 0 corresponds to a parameter that determines the learning step size, and must be selected so that the eigenvalue of the Hessian matrix H D (AGD) is greater than 0 and less than or equal to 1.
  • Equation (4-51) the arithmetic mean is used in (case 2), but a geometric mean may be used instead of the arithmetic mean.
  • L G_1 and L G_2 are basically matrices assumed to be diagonal matrices, and are designed as follows in the RMSProp method.
  • L G_1, L G_2 need not necessarily be a diagonal matrix.
  • the design is as follows.
  • Equation (3-3) The recursive variable update rules corresponding to Equation (3-3) to Equation (3-6) are as follows.
  • Equation (4-54) corresponds to generalized P-R type monotone operator division
  • equation (4-55) corresponds to generalized D-R type monotone operator division
  • the Hessian matrix H D (z) and its inverse matrix H D ⁇ 1 (z) are both block diagonalization matrices as follows.
  • Expression (4-52) includes updating of the latent variable p and the dual variable w, and two methods described below can be considered for handling the latent variable p and the dual variable w.
  • Method 1 In this method, as in the conventional method, p is optimized using a penalty term and then w is optimized.
  • variable update rules of equations (4-52) to (4-55) are specifically expressed as follows.
  • Formula (4-54) and Formula (4-55) were divided into Formula (4-63), Formula (4-64), and Formula (4-65). This is because the variable can be updated asynchronously for each node.
  • the algorithm shown in FIG. 12 is obtained.
  • the Hessian matrix H D in the algorithm is preferably designed using the equation (4-50) or Formula (4-51).
  • Method 2 In this method, the dual variable w is updated, and the latent variable p is updated as necessary.
  • variable update rule is specifically expressed from the equations (4-68), (4-69), (4-54), and (4-55) as follows.
  • the algorithm shown in FIG. 13 is obtained.
  • the Hessian matrix H D in the algorithm is preferably designed using the equation (4-50) or Formula (4-51).
  • v i, u and s i, u are a set of input data and teacher data at node i
  • p i is a latent variable at node i.
  • p * is the optimum value of the latent variable p
  • p i t is the value of the latent variable at node i obtained by t updates
  • m p′V.
  • FIG. 15 shows the experimental results.
  • B-MOS (GD) is the conventional method (algorithm in FIG. 11)
  • B-MOS (AGD) is the method of the present application when the Hessian matrix is designed by the acceleration gradient method (AGD) (algorithm in FIG. 13)
  • MOS (2GD) indicates the method of the present application (algorithm in FIG. 13) when a Hessian matrix is designed by the Newton method.
  • D-ADMM represents another conventional method different from B-MOS (GD).
  • the method of the present application has a higher convergence rate than the conventional method.
  • the Hessian matrix is designed according to the Newton method, the highest convergence rate is obtained.
  • ⁇ 7 Expression using differentiation >> At the beginning of ⁇ 1: Definition of Bregman Resolvent and Bregman Cary Operators >>, it is assumed that function D is a narrowly convex function that can be differentiated.
  • the explanation that the description is “differentiation of function D” holds. In the following, an expression in which the sub-derivative is replaced with the derivative with respect to the main expression will be shown.
  • Bregman divergence B is defined as follows.
  • ⁇ represents an operation that differentiates a function.
  • (Nature 1) and (Nature 2) of the narrowly convex function D can be expressed as follows. (Characteristic 1) When the second-order Taylor expansion is used, the following approximate expression is established for the function D around the point w.
  • the Bregman resolvent operator R n and the Bregman Cary operator C n are given by the following equations.
  • the Bregman resolver operator R n and the Bregman Cary operator C n become the resolvent operator ⁇ n and the Cayley operator ⁇ n , as in the case of using the sub-derivative.
  • the generalized P-R type monotone operator division is as follows, as in the case of subdifferentiation.
  • the generalized D-R type monotonic operator division is as follows, as in the case of subdifferentiation.
  • the function D is expressed by the quadratic expression of the expression (4-48) and substituted into the expression (4-1) * which is the definition expression of the Bregman divergence, thereby obtaining the following.
  • the Bregman-Cary operator C 2 satisfies the following expression.
  • the function G i is differentiable. That is, it is assumed that the differential ⁇ G i of the function G i exists. Even if not those that function G i is differentiable, e.g., for the function G i in the process, such as smoothing may be differentiable function, the function G i is also assumed to be differentiable problem Absent.
  • ⁇ D is updated at an arbitrary timing only when the condition expressed by the following formula is satisfied in order to satisfy that function D is strongly convex. Therefore, if the condition is not satisfied, ⁇ D is not updated.
  • the function D may be expressed by the following equation.
  • FIG. 16 is a block diagram illustrating a configuration of the latent variable learning device 100.
  • FIG. 17 is a flowchart showing the operation of the latent variable learning device 100.
  • the latent variable learning device 100 includes a model learning unit 120 and a recording unit 190.
  • the latent variable learning device 100 learns a latent variable w ⁇ R m (m is an integer of 1 or more) of a model to be machine-learned using learning data.
  • a model is a function that takes input data as input and output data as output.
  • Learning data means input data used to learn model latent variables or model latent variables.
  • the model learning unit 120 learns the latent variable w by using a predetermined procedure using the learning data.
  • the procedure will be specifically described below. (Procedure 1)
  • a learning procedure using Bregman divergence will be described.
  • the model learning unit 120 calculates setup data used when learning the latent variable w using the learning data.
  • a cost function G (w): R m ⁇ R (where G (w) ⁇ i G i (w), function G i ) for optimizing the latent variable w, calculated using learning data
  • G (w) (where N is an integer of 2 or more and i is an integer satisfying 1 ⁇ i ⁇ N (that is, i is an index)).
  • w 2 ) D (w 1 ) -D (w 2 ) defined using the function D (where D: R m ⁇ R is a strictly convex function)
  • D the function D (where D: R m ⁇ R is a strictly convex function)
  • the model learning unit 120 uses the w stop point w that minimizes the cost function G (w).
  • the latent variable w is learned so that Bregman divergence B D (B D (w
  • the function D is a narrowly convex function that can be arbitrarily designed.
  • the model learning unit 120 calculates setup data used when learning the latent variable w using the learning data.
  • G (w) the function D and functions G i blur is defined using grayed man resolvase Vento operator R i (1 ⁇ i ⁇ N ), the blur grayed man resolvase Vento operator R i
  • the Bregman-Cary operator C i (1 ⁇ i ⁇ N) defined by using is calculated as setup data.
  • the value of the latent variable w is recursively calculated using the Bregman resolvent operator R i (1 ⁇ i ⁇ N) and the Bregman Cary operator C i (1 ⁇ i ⁇ N).
  • t is a variable used for counting the number of updates (hereinafter also referred to as a counter)
  • the model learning unit 120 performs Bregman Resolvent operator R i (1 ⁇ i ⁇ N) and Bregman Cary operator C Using i (1 ⁇ i ⁇ N), w t + 1 that is the t + 1th update result of the latent variable w is recursively calculated.
  • the counter t takes an integer value of 0 or more.
  • FIG. 18 is a block diagram illustrating a configuration of the model learning unit 120.
  • FIG. 19 is a flowchart showing the operation of the model learning unit 120.
  • the model learning unit 120 includes an initialization unit 121, a latent variable calculation unit 122, a first auxiliary variable calculation unit 123, a second auxiliary variable calculation unit 124, and a third auxiliary variable calculation unit 125. And a counter update unit 126 and an end condition determination unit 127.
  • model learning unit 120 The operation of the model learning unit 120 will be described with reference to FIG.
  • auxiliary variables x, y, z ⁇ R m of the latent variable w are used.
  • the latent variable calculation unit 122 calculates w t + 1 that is the t + 1th update result of the latent variable w from z t that is the tth update result of the auxiliary variable z, using Equation (5-1). calculate.
  • the first auxiliary variable calculation unit 123 obtains the t + 1th update result of the auxiliary variable x from z t used in S122 and w t + 1 calculated in S122 according to Expression (5-2). t + 1 is calculated.
  • the second auxiliary variable calculation unit 124 calculates y t + 1 that is the t + 1th update result of the auxiliary variable y from x t + 1 calculated in S123, using Expression (5-3).
  • the third auxiliary variable calculation unit 125 calculates z t + 1 that is the t + 1th update result of the auxiliary variable z. This will be specifically described.
  • the third auxiliary variable calculation unit 125 calculates the auxiliary variable z from x t + 1 calculated in S123 and y t + 1 calculated in S124 according to the equation (5-4). Calculate z t + 1 which is the t + 1th update result.
  • the third auxiliary variable calculation unit 125 calculates z t used in S122 and x t + 1 calculated in S123 and S124 using Expression (5-5).
  • z t + 1 which is the t + 1th update result of the auxiliary variable z is calculated from y t + 1 (where ⁇ is a real number satisfying 0 ⁇ ⁇ 1).
  • the counter update unit 126 increments the counter t by 1. Specifically, t ⁇ t + 1.
  • the function D may be a function that satisfies the following conditions.
  • the function D is a function whose Hessian matrix is close to the inverse of the Hessian matrix of the function G i (w).
  • the function D is a function such that the product of the inverse matrix of the Hessian matrix and the Hessian matrix of the function G i (w) is close to the unit matrix”.
  • the Hessian matrix of the function D may be calculated as follows according to the Newton method or the acceleration gradient method.
  • the function G 1 is a strictly convex function, that is, strongly convex (SC) and Lipschitz smoothing (LS).
  • Equation (5-6) and Equation (5-8) follow the Newton method
  • Equation (5-7) and Equation (5-9) follow the acceleration gradient method.
  • the matrices L G_1 and L G_2 are matrices given by Expressions (5-10) and (5-11).
  • the matrices L G_1 and L G_2 are matrices given by the equations (5-12) and (5-13).
  • the matrix L G — 1 in Expression (5-10) and Expression (5-12) is a matrix calculated using the gradient of the function G 1 (w). Further, the matrix L G_2 of formula (5-11) and (5-13) is a matrix that is calculated by using the gradient of the function G 2 (w).
  • the function G 1 (w) and the function G 2 (w) are strictly convex functions. However, the functions are not necessarily strictly strictly convex functions. . In other words, even when the function G 1 (w) or the function G 2 (w) may be treated as a narrowly convex function, the Hessian matrix of the function D is obtained by the equations (5-6) to (5-9). Can be calculated. More specifically: [Case 1]: The function G 1 is a strictly convex function (strongly convex (SC) and Lipschitz smoothing (LS)) or a narrowly convex function (strongly convex (SC) and Lipschitz smoothing (LS) ).
  • the Hessian matrix of the function D can be calculated by the equations (5-6) and (5-7).
  • G 1 and G 2 are a narrowly convex function (strongly convex (SC) and Lipschitz smoothing (LS)) or a narrowly convex function (strongly convex (SC) and When it can be assumed that it is Lipschitz smoothing (LS).
  • the Hessian matrix of the function D can be calculated by the equations (5-8) and (5-9).
  • the sub-differentiation is used.
  • a differentiation may be used instead of the sub-differentiation.
  • the following equation may be used instead of equations (5-1) to (5-5).
  • ⁇ D when using differentiation, ⁇ D may be updated under the condition expressed by the following equation.
  • ⁇ D shall be updated at an arbitrary timing only if the conditions expressed by the following formula are satisfied.
  • the invention of this embodiment it is possible to learn a latent variable of a model that is a target of machine learning at high speed.
  • a variable update rule based on monotone operator division using Bregman Resolvent operators and Bregman Cary operators, convergence to a stationary point (optimal solution) is fast.
  • the latent variable can be updated so that It is also based on monotonic operator division using Bregman Resolvent and Bregman Cary operators, so that the convex function used to define Bregman divergence can be configured appropriately to speed up convergence to the stopping point.
  • Variable update rules can be configured.
  • FIG. 20 is a block diagram illustrating a configuration of the latent variable learning system 20.
  • Latent variable learning system 20 as shown in FIG. 20, (the V 1 or more integer) V pieces including latent variable learning device 200 1, ..., a 200 V.
  • Each latent variable learning device 200 i is connected to the network 900 and communicates with the latent variable learning device 200 j (j ⁇ i) as necessary.
  • the network 900 for example, the Internet can be used.
  • FIG. 21 is a block diagram showing a configuration of the latent variable learning apparatus 200.
  • the latent variable learning device 200 includes a model learning unit 220, a communication unit 280, and a recording unit 290.
  • the latent variable learning device 200 i learns a latent variable p i ⁇ R p ′ (p ′ is an integer of 1 or more) of a model to be machine learning using the learning data.
  • the learning data may be common to all the latent variable learning devices 200 i , or may be different for each latent variable learning device 200 i .
  • FIG. 22 is a block diagram illustrating a configuration of the model learning unit 220.
  • FIG. 23 is a flowchart showing the operation of the model learning unit 220.
  • the model learning unit 220 includes an initialization unit 221, a latent variable calculation unit 222, a first dual variable calculation unit 223, a synchronization variable update unit 224, a second dual variable calculation unit 225, The counter update unit 226 and the end condition determination unit 227 are included.
  • model learning unit 220 The operation of the model learning unit 220 will be described with reference to FIG. Before entering a specific description, some symbols will be described. These symbols have been used in the discussion so far, and the following description corresponds to the summary.
  • N (i) represents an index set of the latent variable learning device 200 group communicating with the latent variable learning device 200 i .
  • the function F 1, i (p i ): R p ′ ⁇ R is a cost function for optimizing the latent variable p i calculated using the training data (where F 1, i (p i ) is Closed true convex function).
  • j , ⁇ i are variables of the latent variable learning device 200 i for storing data transmitted from the latent variable learning device 200 j (where j ⁇ N (i)).
  • j and ⁇ i are also referred to as synchronization variables.
  • t is a variable (hereinafter also referred to as a counter) for counting the number of updates of the variable, and ⁇ ( ⁇ is an integer of 1 or more) is a predetermined number of updates. This ⁇ represents the upper limit of the number of repetitions of S222 to S225 described later.
  • the latent variable learning system 20 includes the latent variable learning device S i (i ⁇ v), and the latent variable learning device S i (i ⁇ v) uses the learning data to perform the latent variable p i according to a predetermined procedure. To learn. The procedure will be described below with reference to FIG.
  • the initialization unit 221 calculates setup data.
  • the cost function F 1, i (p i ) is an example.
  • the latent variable calculation unit 222 by the following equation, dual variable z i
  • the first dual variable calculator 223 calculates the dual variable ⁇ i
  • j represents the Hessian matrix of the function D i
  • the synchronization variable updating unit 224 uses the communication unit 280 to change the values obtained by learning of the latent variable learning device S j (j ⁇ N (i)) into the variables ⁇ i
  • ⁇ is a real number satisfying 0 ⁇ ⁇ 1.
  • equation (6-1) corresponds to the case where generalized P-R type monotone operator division is used
  • equation (6-2) corresponds to the case where generalized DR type monotone operator division is used.
  • the counter update unit 226 increments the counter t by 1. Specifically, t ⁇ t + 1.
  • the termination condition determination unit 227 sets the value p of the latent variable p i at that time. i ⁇ is output and the process is terminated. Otherwise, the process returns to S222. That is, the model learning unit 220 repeats the calculations of S222 to S225. Note that z i
  • j is preferably designed using the equations (5-6) to (5-9). (Modification 1)
  • the above procedure corresponds to the algorithm of FIG.
  • a procedure corresponding to the algorithm of FIG. 13 will be described.
  • the variable ⁇ i is not used.
  • the latent variable learning device 200 includes a model learning unit 230 instead of the model learning unit 220, as shown in FIG.
  • the model learning unit 230 will be described with reference to FIGS.
  • FIG. 24 is a block diagram illustrating a configuration of the model learning unit 230.
  • FIG. 25 is a flowchart showing the operation of the model learning unit 230.
  • the model learning unit 230 includes an initialization unit 231, a first dual variable calculation unit 232, a latent variable calculation unit 233, a synchronization variable update unit 234, a second dual variable calculation unit 235,
  • the counter update unit 236 and the end condition determination unit 237 are included.
  • model learning unit 230 The operation of the model learning unit 230 will be described with reference to FIG.
  • the first dual variable calculation unit 232 for j ⁇ N (i), the following equation, dual variable z i
  • j represents a Hessian matrix of the function D i
  • H F_1, i represents a Hessian matrix of the function F 1, i . That is, H D — i
  • ⁇ F 1, i represents the sub-derivative of the function F 1, i .
  • the latent variable calculation unit 233 calculates p i t + 1 that is the t + 1th update result of the latent variable p i by the following equation.
  • j t represents the t-th update result of the dual variable w i
  • the synchronization variable updating unit 234 uses the communication unit 280 to change the value obtained by learning of the latent variable learning device S j (j ⁇ N (i)) to the variable ⁇ i
  • ⁇ is a real number satisfying 0 ⁇ ⁇ 1.
  • equation (6-1) corresponds to the case where generalized P-R type monotone operator division is used
  • equation (6-2) corresponds to the case where generalized DR type monotone operator division is used.
  • the counter update unit 236 increments the counter t by 1. Specifically, t ⁇ t + 1.
  • the termination condition determination unit 237 determines the value p of the latent variable p i at that time. i ⁇ is output and the process is terminated. Otherwise, the process returns to S232. That is, the model learning unit 230 repeats the calculations of S232 to S235. Note that z i
  • j is preferably designed using the equations (5-6) to (5-9).
  • the invention of this embodiment it is possible to learn a latent variable of a model that is a target of machine learning at high speed.
  • a variable update rule based on monotone operator division using Bregman Resolvent operators and Bregman Cary operators, convergence to a stationary point (optimal solution) is fast.
  • the latent variable can be updated so that It is also based on monotonic operator division using Bregman Resolvent and Bregman Cary operators, so that the convex function used to define Bregman divergence can be configured appropriately to speed up convergence to the stopping point.
  • Variable update rules can be configured.
  • the apparatus of the present invention includes, for example, a single hardware entity as an input unit to which a keyboard or the like can be connected, an output unit to which a liquid crystal display or the like can be connected, and a communication device (for example, a communication cable) capable of communicating outside the hardware entity Can be connected to a communication unit, a CPU (Central Processing Unit, may include a cache memory or a register), a RAM or ROM that is a memory, an external storage device that is a hard disk, and an input unit, an output unit, or a communication unit thereof , A CPU, a RAM, a ROM, and a bus connected so that data can be exchanged between the external storage devices.
  • the hardware entity may be provided with a device (drive) that can read and write a recording medium such as a CD-ROM.
  • a physical entity having such hardware resources includes a general-purpose computer.
  • the external storage device of the hardware entity stores a program necessary for realizing the above functions and data necessary for processing the program (not limited to the external storage device, for example, reading a program) It may be stored in a ROM that is a dedicated storage device). Data obtained by the processing of these programs is appropriately stored in a RAM or an external storage device.
  • each program stored in an external storage device or ROM or the like
  • data necessary for processing each program are read into a memory as necessary, and are interpreted and executed by a CPU as appropriate.
  • the CPU realizes a predetermined function (respective component requirements expressed as the above-described unit, unit, etc.).
  • the processing functions in the hardware entity (the device of the present invention) described in the above embodiment are realized by a computer, the processing contents of the functions that the hardware entity should have are described by a program. Then, by executing this program on a computer, the processing functions in the hardware entity are realized on the computer.
  • the program describing the processing contents can be recorded on a computer-readable recording medium.
  • a computer-readable recording medium for example, any recording medium such as a magnetic recording device, an optical disk, a magneto-optical recording medium, and a semiconductor memory may be used.
  • a magnetic recording device a hard disk device, a flexible disk, a magnetic tape or the like, and as an optical disk, a DVD (Digital Versatile Disc), a DVD-RAM (Random Access Memory), a CD-ROM (Compact Disc Read Only) Memory), CD-R (Recordable) / RW (ReWritable), etc., magneto-optical recording media, MO (Magneto-Optical disc), etc., semiconductor memory, EEP-ROM (Electronically Erasable and Programmable-Read Only Memory), etc. Can be used.
  • this program is distributed by selling, transferring, or lending a portable recording medium such as a DVD or CD-ROM in which the program is recorded. Furthermore, the program may be distributed by storing the program in a storage device of the server computer and transferring the program from the server computer to another computer via a network.
  • a computer that executes such a program first stores a program recorded on a portable recording medium or a program transferred from a server computer in its own storage device. When executing the process, this computer reads the program stored in its own storage device and executes the process according to the read program.
  • the computer may directly read the program from a portable recording medium and execute processing according to the program, and the program is transferred from the server computer to the computer. Each time, the processing according to the received program may be executed sequentially.
  • the program is not transferred from the server computer to the computer, and the above-described processing is executed by a so-called ASP (Application Service Provider) type service that realizes a processing function only by an execution instruction and result acquisition. It is good.
  • the program in this embodiment includes information that is used for processing by an electronic computer and that conforms to the program (data that is not a direct command to the computer but has a property that defines the processing of the computer).
  • the hardware entity is configured by executing a predetermined program on the computer.
  • a predetermined program on the computer.
  • at least a part of these processing contents may be realized in hardware.

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • Mathematical Physics (AREA)
  • Software Systems (AREA)
  • Mathematical Analysis (AREA)
  • Computational Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Pure & Applied Mathematics (AREA)
  • Mathematical Optimization (AREA)
  • Algebra (AREA)
  • Databases & Information Systems (AREA)
  • Artificial Intelligence (AREA)
  • Evolutionary Computation (AREA)
  • Operations Research (AREA)
  • Medical Informatics (AREA)
  • Computing Systems (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Bioinformatics & Cheminformatics (AREA)
  • Bioinformatics & Computational Biology (AREA)
  • Evolutionary Biology (AREA)
  • Probability & Statistics with Applications (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Machine Translation (AREA)

Abstract

コスト関数が凸関数でない場合にも機械学習を行うことができる機械学習技術を提供する。機械学習システムは、情報を互いに送受信しながら、それぞれの入力データに基づいて共通するある１つの主変数を用いた写像を機械学習する複数のノード部を含み、機械学習に本来対応する非凸関数のコスト関数に代えて、コスト関数の上界となる代理凸関数を最小化するように機械学習が行われ、代理凸関数は、コスト関数の主変数に関する一次勾配の式、又は、コスト関数の主変数に関する一次勾配の式及び二次勾配の式で表されている。

Description

機械学習システム、機械学習方法、プログラム
　本発明は、機械学習の技術に関する。
　近年、機械学習がブームになっており、収集したデータと出力したい情報の間の写像(mapping)を、データと教師データを用いた学習により得るフレームワークが一般的になってきている。なお、教師データに代えて、コスト関数が用いられる場合もある。
　現在行われている研究のほとんどで、データを中央集約化し、教師データ又は設計したコスト関数を用いて写像を学習するフレームワークが取られている。しかし、音声及び映像といった情報を中央集約化するのは、データ容量がかなり膨大になってきている今日では現実的ではなくなりつつある。円滑なサービスを提供する上で(例えば、ユーザとサーバ間のネットワーク距離が近ければレスポンスタイムが早くなる)、分散したノード群(例えば、サーバ、PC)に分散してデータを収集し、そのノード群が連結し、容量の大きなデータそのものではなく、その潜在変数のみをやりとりするだけで、写像が最適化され、すべてのノード間で共有されるようなフレームワークこそが、今日の機械学習の分野で熱望されている技術の一つである。こういった技術は、エッジコンピューティングにおける合意形成アルゴリズム(コンセンサスアルゴリズム)と呼ばれる。
　図１に、この合意形成アルゴリズムの適用先となるネットワークシステムを例示する。図１のネットワークシステムには、様々な環境(例えば、家、工場、野外及びビル)に多数のセンサーＡ－１０１など(例えば、マイク、カメラ、温度計)が分散して配置されており、それらのセンサーＡ－１０１を通じて得られたデータが、分散して配置された複数のノード部Ａ－１０２(例えば、サーバ、PC)のそれぞれに蓄積される。中央集約型のフレームワークでは中央サーバが必要であり、全てのデータが中央サーバに蓄積される必要があるが、合意形成アルゴリズムを用いる場合には、中央サーバは存在しなくてもよく、データは分散して配置された複数のノード部Ａ－１０２のそれぞれに蓄積されればよい。なお、データは、センサーＡ－１０１から得られるものに限らず、入力装置やWeb等から得られる文字データ等でも構わない。図１のネットワークシステムのノード部Ａ－１０２間は、エッジＡ－１０３によって疎に結合しており、全結合でなくてもよく、ノード部Ａ－１０２間で直接または間接的に何らかのデータを交換できる関係にあればよい。エッジＡ－１０３の連結構造についての制約はなく、木構造、循環/円構造でもなんでもよい。しかし、全てのノード部Ａ－１０２が直接または間接的につながっていればよい。すなわち、エッジＡ－１０３の連結構造は、分割された構造でなければよい。
　エッジコンピューティングにおける合意形成アルゴリズムを用いれば、図１のネットワークシステムのような条件の下で、データそのものではなく、写像を学習する過程で生成される変数をノード間で交換しながら、写像を最適化し、共有することができ、レスポンスタイムを早めたりデータ量を削減したりすることが可能である。
　従来技術として、凸最適化技術に基づく合意形成型のエッジコンピューティングについて述べる。コスト関数が凸関数であることに限定されるが、合意形成型のエッジコンピューティング技術は既に存在する。１つ目はDistributed ADMM法(Alternating Direction Method of Multipliers)に基づく方法（例えば、非特許文献１参照。）、２つ目はPDMM法(Primal Dual Method of Multipliers)に基づく方法（例えば、非特許文献２参照）である。なお、DNNは、非凸のコスト関数であるのでこの枠組みには入らない。
《Distributed ADMM法の合意形成アルゴリズム》
　以下、Distributed ADMM法の合意形成アルゴリズムについて説明する。
　コスト関数は、閉真凸関数(Closed Proper Convex function)に限定する。Distributed ADMMベースの合意形成アルゴリズムでは、主変数と双対変数を更新しながら全体最適化を図る。その過程において、主変数をノード間で共有し、それらが一致するように合意形成するようにして、コスト関数が生成される。
　図２は、３種類のノードが全連結されている状況を示している。図２の例では、変数は、３種類の主変数w1,w2,w3、６種類の双対変数λ1|2,λ2|1,λ1|3,λ3|1,λ2|3,λ3|2、６種類のノード間で交換される主変数w1 <1>,w1 <2>,w2 <1>,w2 <2>,w3 <1>,w3 <2>で構成される。
　ノードを表すインデックス集合~Vとノード数Vを以下のように書く。
Figure JPOXMLDOC01-appb-M000013
　i番目のノードにつながっているノードのインデックス集合(エッジの情報)~N(i)とその数N(i)を以下のように書く。なお、~N(i)は、N(i)の上に「~」が付されていることを表す。後に出てくる~V,~Bについても同様である。
Figure JPOXMLDOC01-appb-M000014
　i番目のノードにおけるj番目のノードに対する双対変数をλi|jとする。
　写像の一つの事例として、教師データとの最小二乗問題を扱う。
　以下のように記号を定義する。sを教師データ、xを入力データ（「観測データ」と言う場合もある）、wを重みベクトル、Bを教師データ(「出力データ」と言う場合もある)の次元(b=1,…,B)、λを双対変数とする。なお、双対変数λの次元は、重みベクトルwの次元と同じであるとする。添え字が付いたこれらのアルファベットの意味は、添え字が付いてないアルファベットと同じであるとする。例えば、siは、sと同じく教師データを意味する。また、~B={1,…,B}であるとする。Bは所定の正の整数である。識別問題を扱う場合には、Bを２以上の整数とする。例えば、10種類の数字を認識するタスクであれば、B=10である。また、回帰問題を扱う場合には、例えばB=1とする。
　このとき、i=1,…,Vとして、教師データsiは以下のような構成になる。
Figure JPOXMLDOC01-appb-M000015
　同様にして、xi=[xi,1,…,xi,B]Tであり、wi=[wi,1,…,wi,B]Tであり、λi|j=[λi|j,1,…, λi|j,B]Tであるとする。
　i番目ノードにあるデータxiに重み付け加算することでsiを得るような算術を写像として用いるとき、写像を最適化するためのコストは以下の真凸閉関数fiで書ける。i番目のノードにおけるコスト関数をfiとし、これを最小化するようなwを探索する。
Figure JPOXMLDOC01-appb-M000016
　ここで、写像関数は線形の重みづけ加算^si,b=xi Twi,bであるとする。si,bの左上の^は、学習後又は学習途中に得られたwi,bにより得られることを表す。また、・を任意の数として、||・||pはL-pノルムを意味する。
　wを以後、主変数と呼ぶ。V個のノードが連結していて、変数が同一となるような制約下でコストを最小化する問題は以下で書ける。
Figure JPOXMLDOC01-appb-M000017
　ここで、wj,b <i>は、i番目のノードに蓄積されたj番目のノードの主変数を意味する。後述するように、wj,b <i> は適宜更新される。
　この式は、双対変数λを最大化する条件下(ノード間の主変数が連結しているノード間で一致する条件を満たせば、λに掛かっている項が０になるという意図)で、コスト関数を最小化するように主変数wを最適化するということを表している。
　なお、主変数wが連結しているノード間で一致するという条件は、例えば行列Aを、互いを加算して０になる関係で記述することができる。例えば、行列Aは、以下のようにI,-I,0で記述することができる。Iは単位行列であり、0は零行列である。
Figure JPOXMLDOC01-appb-M000018
　非特許文献３のp.154-155にあるミニマックス定理より、コスト関数”f”が真凸関数であれば、「双対変数を最大化しながら主変数を最小化する」という元々の問題の最適解は、「主変数を最小化しながら、双対変数を最大化する」問題を解いた場合の最適解と一致する。
Figure JPOXMLDOC01-appb-M000019
　この問題を解くための方式として拡張ラグランジュ法がある（例えば、非特許文献２参照。）。これは、最適化処理を安定化させるために、罰則項を加算する方法である。ρiは、所定の正の数である。
Figure JPOXMLDOC01-appb-M000020
　内側のwに関する最小化する問題を最初に解く。すなわち、wに関して微分が０になるポイントを探る。w*は、wに関して最適化されたポイントを指す。また、tは更新回数のインデックスを表す。
Figure JPOXMLDOC01-appb-M000021
　このため、t+1回目の主変数の更新は以下のように行われる。
Figure JPOXMLDOC01-appb-M000022
　双対変数に関するt+1回目の更新は以下のように行われる。
Figure JPOXMLDOC01-appb-M000023
　従来法のDistributed ADMM法の合意形成アルゴリズムをまとめると以下になる。
　T回更新するとして、t∈{0,…,T-1}に対して、以下の(1)から(3)の処理を行う。ここで、Tは、繰り返し回数であり、所定の正の整数である。この明細書では、Tは、繰り返し回数又は行列及びベクトルの転置を表すが、当業者であれば文脈に応じてどちらを意味するのか明確であるため、以降の説明ではどちらを意味するのかを明示せずにTを用いることにする。
(1)主変数更新
Figure JPOXMLDOC01-appb-M000024
(2)双対変数更新
Figure JPOXMLDOC01-appb-M000025
(3)毎回である必要はないし、エッジごとに独立(非同期)でよいが、主変数をノード間で更新する。
Figure JPOXMLDOC01-appb-M000026
　Distributed ADMM法の合意形成アルゴリズムの長所は、理論的な背景はないが、いくつかの実験を通じて、各ノードに蓄積されるデータセット間に統計的性質差がある場合にも収束することが確認されているということである。ただし、その収束率は低い。
　一方、Distributed ADMM法の合意形成アルゴリズムの短所は、以下の(1)から(4)である。(1)収束率が低い。(2)原理的に、非凸関数の最適化(DNN等を含む)に適用できない。(3)主変数を交換するという観点で、情報の秘密性がやや低い。すなわち、主変数にはデータの性質が色濃く反映されることがあるので、主変数をハッキングすることで、データの統計的性質を得られる可能性がある。(4)伝送レートがやや高い。すなわち、主変数のデータに統計的な偏りが見られない場合、伝送レートは高くなりがちであることである。
《PDMMベースの合意形成アルゴリズム》
　次に、PDMMベースの合意形成アルゴリズムについて説明する。Distributed ADMMと大きく異なる点は、主変数だけでなく、双対変数も共有することである。後述するが、双対変数のペアについて合意形成される。
　λi|j=λj|iという条件下で最適化問題を解くことは、主変数も暗に合意することに相当する。すなわち、主変数及び双対変数のそれぞれで合意形成される。また、その制約を課すことで、収束速度が高くなることが理論的に明らかになっている。
　図３の例では、６種類の双対変数λ1|2,λ2|1,λ1|3,λ3|1,λ2|3,λ3|2が３種類のペアλ1|2=λ2|1,λ1|3=λ3|1,λ2|3=λ3|2を形成している。双対変数と主変数を連結しているノード間で情報交換しながら、合意形成することを目指す。なお、双対変数は、各更新時における主変数間の差分に物理的には相当する。
　Distributed ADMMと同様にコスト関数は閉真凸関数に限る。一つの事例として、最小二乗問題を解く場合、以下がコストとなる。
Figure JPOXMLDOC01-appb-M000027
　Distributed ADMMと同様に双対問題を定義すると以下のようになる。
Figure JPOXMLDOC01-appb-M000028
　以下に変数の定義を書く。以下では、V個のノードを連結して変数を表現している。
Figure JPOXMLDOC01-appb-M000029
　図３のようなエッジ構成を想定して、言い換えればλi|j=λj|iという制約の下で式を書き下すと以下のようになる。
Figure JPOXMLDOC01-appb-M000030
　主変数及び双対変数のそれぞれで合意形成するという条件は以下で書ける。
Figure JPOXMLDOC01-appb-M000031
　wを最適化するうえでの一つのテクニックとして、fのルジャンドル変換である凸共役関数f*を導入する。これは、fが閉真凸関数であるとき、f*もまた閉真凸関数になることが知られているので、このような記述をする（例えば、非特許文献３参照。）。
Figure JPOXMLDOC01-appb-M000032
　なお、上記の第一式の右辺は、下記の式の下線部分を取り出したものである。
Figure JPOXMLDOC01-appb-M000033
　元々の問題は、以下のようにかける。以下の式変形では、f*が閉真凸関数であるので、その最小化問題として書けることを利用している。
Figure JPOXMLDOC01-appb-M000034
　双対変数の合意条件下での最適化問題であることを追加すると、解くべき問題は以下で再定義される。
Figure JPOXMLDOC01-appb-M000035
　この問題は、以下を解くことに相当する。
Figure JPOXMLDOC01-appb-M000036
　関数δは指示関数と呼ばれる。指示関数も凸関数の一種である。行列Pは、以下に示すように、i,j番目のノード間にある双対変数のペアを交換するという演算(permutationのP)であり、双対変数が一致した時に指示関数が0を出力する(コストを下げる)ということを意味している。
Figure JPOXMLDOC01-appb-M000037
　解くべき問題は、２種類の凸関数で構成されている。こういった問題を解くためのテクニックとして、オペレータ分割法がある（例えば、非特許文献４参照。）。これは、全体最適化を一度に行うことが難しい問題であっても、交互に最適化しながら解くテクニックである。
　オペレータ分割法には、様々な方法が存在するが、代表的なものとして、Peaceman-Rachford splitting (P-R分割) がある。
　P-R分割を使ったPDMMベースの合意形成アルゴリズムは、以下のようになる。
　T回更新するとして、t∈{0,…,T-1}に対して、以下の(1)から(3)の処理を行う。
(1)主変数更新
Figure JPOXMLDOC01-appb-M000038
(2)双対変数更新
Figure JPOXMLDOC01-appb-M000039
(3) 主変数をノード間で更新する。なお、更新過程は非連続であってもよく(毎回更新する必要はない)、かつ、エッジごとに独立(非同期)に実行してよい。
Figure JPOXMLDOC01-appb-M000040
　このPDMMベースの合意形成アルゴリズムの長所は、収束率が高いということである。
　一方、このPDMMベースの合意形成アルゴリズムの短所は、以下の(1)から(4)である。(1)いくつかのケースで、各ノードに蓄積されるデータセット間に統計的性質差がある場合に、収束しないという結果を得たということである。しかし、異質なデータセットに対しても収束するという理論的保証はない。(2) 原理的に、非凸関数の最適化(DNN等を含む)に適用できない。(3)主変数を交換するという観点で、情報の秘密性がやや低い。すなわち、主変数にはデータの性質が濃く反映されることがあるので、主変数をハッキングすることで、データの統計的性質を得られる可能性がある。(4)伝送レートが高い。すなわち、主変数と双対変数を送るので、伝送レートは高くなりがちである。
　次に、機械学習の対象となるモデルの潜在変数を学習する際に扱うコストの最小化問題を考える。この最小化問題は、以下のように定式化される。
（問題）
　コスト関数Gは、関数G1と関数G2に加法分割されるものとする。ただし、関数G1, G2はいずれも閉真凸関数であるものとする（以後、閉真凸関数のことを単に凸関数という）。
Figure JPOXMLDOC01-appb-M000041
　ここで、w∈Rm（mは1以上の整数）、Gi:Rm→R∪{∞} (i=1, 2)である。つまり、wは、m次元実ベクトル空間Rmの要素であり、Giは、m次元実ベクトルwを入力とし、（1次元の）実数を出力する関数である。
　なお、Giの入力は、ベクトルであるとしたが、行列やテンソルであってもよい。行列やテンソルはベクトルを用いて表現することができるので、以下、Giの入力はベクトルであるものとして話を進める。
　コストGを最小化するように潜在変数wを最適化する問題は、以下のように表される。
Figure JPOXMLDOC01-appb-M000042
　この問題の最適解w*（wの停留点ともいう）は、コストGの劣微分が0ベクトル（零ベクトル）を含むときに得られる。
Figure JPOXMLDOC01-appb-M000043
　ここで、∂Giは、Giの劣微分を表す。なお、入力と出力が１対１対応となる等号を表す記号”=“の代わりに、記号“∈”を用いるのは、凸関数Giが不連続点を含む場合、その劣微分は不連続点において多点出力対応となるためである。
　最適解w*を求める従来方法を説明する前に、式(1-1)に従う具体的問題をいくつか挙げる。
《具体的問題１：エッジコンピューティングにおける合意形成問題》
　V個のノードが任意に接続されたグラフG(v, e)（ただし、vはノードの集合、eはエッジの集合である）を考える。
Figure JPOXMLDOC01-appb-M000044
　ここで、N(i)はi番目のノードに接続されたノード群のインデックスの集合を表す。
　図９は、V個のノード（サーバ）がエッジ構造eに従って繋がっている状態（V=5の場合）を示す。各ノードに蓄積された膨大なデータをノード間で交換するのではなく、潜在変数やその補助変数（例えば、双対変数）を交換しながら全体最適化する問題がエッジコンピューティングにおける合意形成問題である。
　i番目のノードにある凸関数で表現されたコストを以下のように表す。
Figure JPOXMLDOC01-appb-M000045
　ここでは、問題の理解を容易にするために、コストF1,iの具体例として、教師データsiに対する二乗誤差を用いることにする。
Figure JPOXMLDOC01-appb-M000046
　ここで、Tは転置、||・||pはLpノルムを表す。また、u(i)={1,…,U(i)}である。
　このコストF1,iは、p’次元ベクトルvi∈Rp’を入力データとし、教師データsiを出力するように、U(i)個のデータの組(vi,u, si,u)を用いて、潜在変数pi(pi∈Rp’)を最適化する問題のコスト関数である。ノードによってデータやその数U(i)が異なることをインデックスが示している。一般に、各ノードに蓄積されたデータは異なるが、同一であってもよい。なお、入力データと教師データの組のことを学習データという。また、以下、m=p’Vとする。
　この例では、教師データを用いる形で定式化したが、教師データを用いることなく定式化することもできる。
　また、同一のロケーションにある複数のサーバによる並列コンピューティングについても、上記合意形成問題と同一の問題として定式化できる。例えば、多数のコンピュータを使って並列計算をして、音声認識、画像認識などのモデルを高速に学習するような場合が該当する。この場合、各サーバに蓄積されるデータセットは基本的には同一になる。
　合意形成問題では、ノード間で潜在変数pの値が同一になるように制約しながら、コストを最小化する停留点を探すことになる。
Figure JPOXMLDOC01-appb-M000047
　ここで、pi∈Rp’、Ai|j∈Rp’×p’である。Ai|jは合意形成を表現するp’×p’の実数行列である。この行列Ai|jとして任意の行列を用いることができるが、”ノード間で潜在変数の値が同一になるように学習を進めたい”という意図がある場合、例えば、以下のような簡単な行列を用いることができる。
Figure JPOXMLDOC01-appb-M000048
　ここで、Iは単位行列である。
　式(2-1)のような線形拘束下でのコスト最小化問題を解く場合、ラグランジュの未定乗数法を用いることが多い。双対変数νi,j∈Rp’を用いて、ラグランジュ関数Lを以下のように定義する。
Figure JPOXMLDOC01-appb-M000049
　式(2-1)を解くことは、以下の式(2-2)の問題（主問題）を解くことに対応する。しかし、この問題を直接解くことは困難な場合が多い。
　F1,iが閉真凸関数であるとき、強双対性が成立する、つまり、最適点において式(2-2)と式(2-3)間の統合性が成り立つので、式(2-2)を解く代わりに、式(2-3)の問題（双対問題）を解くことが一般的である。
Figure JPOXMLDOC01-appb-M000050
　ここで、F1,i *は、凸関数F1,iの凸共役関数を表す。
Figure JPOXMLDOC01-appb-M000051
　F1,iが凸関数である場合、F1,i *も凸関数になる。
　式(2-4)は、凸関数F1,i *を最小化する双対変数νi,jを探す問題を表している。式(2-1)を解くためには、式(2-4)を解けばよいが、式(2-4)の形式のままでは、ノードごとに非同期で潜在変数を更新するような処理を実現することができない。そこで、双対変数νi,jをノードごとに帰属するようにリフティング処理を行う。具体的には、双対変数νi,jをi番目のノードに帰属する双対変数λi|j∈Rp’とj番目のノードに帰属する双対変数λj|i∈Rp’の2つに分け、これらの変数が一致するという制約を入れる。
Figure JPOXMLDOC01-appb-M000052
　図１０Ａ及び図１０Ｂは、双対変数のリフティング処理の様子を示す図である。図１０Ａは、ノードiとノードjの合意形成における誤差を制御しているのが変数νi,jであることを表している。しかし、このままではi番目の潜在変数とj番目の潜在変数を同期しながら更新しなければならない。そこで、i番目の潜在変数とj番目の潜在変数を非同期でも更新できるようにするために、図１０Ａでは無方向であったエッジを、図１０Ｂのように方向性のある2つのエッジに書き換える。この2つのエッジは1つの無方向のエッジから生成されたものであるので、一致するという制約が必要になるが、変数更新における同期性の問題を解決することができる。
　双対変数のリフティング処理により、式(2-4)の問題は、以下の問題（線形拘束付の最適化問題）に書き換えられる。
Figure JPOXMLDOC01-appb-M000053
　V個に分けて書いていた変数群をベクトルや行列を用いて表現することにより、式(2-5)は以下のように表現する。もちろん、式の意味は変わることなく、同一の問題を表している。
Figure JPOXMLDOC01-appb-M000054
　ここで、凸共役関数F1 *は、次式のようになる。
Figure JPOXMLDOC01-appb-M000055
　なお、F1:Rm→R∪{∞}, F1 *:Rm→R∪{∞}(m=p’V)である。
　また、V個のノードごとに分けて書いていた変数群（つまり、pi, λi|j, Ai|j）は以下のようになる。
Figure JPOXMLDOC01-appb-M000056
　ここで、さらに、リフティング処理された双対変数が一致するという制約を記述するにあたって、変数が一致するという観点で適切な性質をもつ指示関数F2を用いることにする。指示関数F2を用いると、式(2-6)の問題は、以下の問題に帰着する。
Figure JPOXMLDOC01-appb-M000057
　ここで、指示関数F2は、以下のように定義される。
Figure JPOXMLDOC01-appb-M000058
　ここで、Pは順序入替行列（パーミュテーション行列）である。順序入替行列Pの要素はすべて0または1であり、P2=Iという性質を持つ。行列Pをベクトルλにかけることは、以下のようにノードiとノードjの間のエッジに対応する双対変数λi|j, λj|iを入れ替える処理（λj|i⇔λi|j）に相当する。
Figure JPOXMLDOC01-appb-M000059
　ここで、式(2-7)に対して以下のようなに置き換えを適用することにより、エッジコンピューティングにおける合意形成問題（つまり、式(2-7)）が式(1-1)に帰着することがわかる。
Figure JPOXMLDOC01-appb-M000060
　また、別の例として以下のようなものがある。
《具体的問題２：画像／音声／言語の認識タスクにおける汎用モデル生成問題》
　画像/音声/言語等の認識タスクにおける汎用モデルを生成するための方法として、以下のようなコストを用いて潜在変数pを学習させることが有用であることが知られている（参考非特許文献１）。
（参考非特許文献１：V. Vapnik, “Principles of Risk Minimization for Learning Theory”, Advances in Neural Information Processing Systems 4 (NIPS1991), pp.831-838, 1992.）
Figure JPOXMLDOC01-appb-M000061
　ここで、p∈Rmは潜在変数、λ∈Rmは双対変数、A=[a1, …, an]T∈Rn×mは入力データを表す。
　式(2-8)に対して以下のようなに置き換えを適用することにより、画像／音声／言語の認識タスクにおける汎用モデル生成問題（つまり、式(2-8)）は式(1-1)に帰着することがわかる。
Figure JPOXMLDOC01-appb-M000062
　また、式(2-9)に対しても以下のようなに置き換えを適用することにより、式(1-1)に帰着することがわかる。
Figure JPOXMLDOC01-appb-M000063
　例えば、F1には二乗誤差やクロスエントロピーを用い、F2には正則化項としてL1ノルムを用いることができる。もちろん、F1、F2はこれに限るものではない。
Figure JPOXMLDOC01-appb-M000064
　ここで、sは、所望する出力情報の教師データである。なお、aiは、上述の入力データA=[a1, …, an]T∈Rn×mを構成するベクトルである。
　なお、認識タスク以外のタスク、例えば、画像／音声の雑音除去にも用いることができる。
《最適解w*を求める従来方法》
　ここでは、従来の解法について簡単に説明する。先述したように解くべき問題は式(1-1)である。また、式(1-1)で表される問題の最適解w*（wの停留点）は、式(1-2)が示すように、コストGの劣微分が0ベクトル（零ベクトル）を含むときに得られる。なお、Giが凸関数である場合、Giの劣微分∂Giは単調作用素となる。
　式(1-2)を解いて最適解w*を求めるために、劣微分を連続線形写像に変換する。この変換方法のことを単調作用素分割法(Monotone operator splitting)という（非特許文献４）。単調作用素分割法には様々な方法が存在するが、ここでは、再帰的な変数更新に伴うコストの非拡大性（つまり、変数を更新するにつれて、コストが縮小していくという性質）を担保することができるPeaceman-Rachford(P-R)型とDouglus-Rachford(D-R)型の2種類の単調作用素分割法について説明する。
　具体的な導出手続きについては省略するが、式(1-2)を変形していくと、P-R型単調作用素分割とD-R型単調作用素分割が得られる。なお、変形に際して、リゾルヴェント作用素Ωnとケーリー作用素Ψnを用いる(n=1, 2)。
Figure JPOXMLDOC01-appb-M000065
　ただし、Iは同一作用素、-1は逆作用素を表す。
　また、w(w∈Rm)の補助変数z(z∈Rm)を導入する。その関係は以下のようにリゾルヴェント作用素で接続される。
Figure JPOXMLDOC01-appb-M000066
　P-R型単調作用素分割、D-R型単調作用素分割は、それぞれ式(3-1)、式(3-2)で表される。
Figure JPOXMLDOC01-appb-M000067
　式(3-1)と式(3-2)をみると、P-R型単調作用素分割に平均化作用素を導入することで、D-R型単調作用素分割が得られることがわかる。
　以下、エッジコンピューティングにおける合意形成問題を例として、式(3-1)、式(3-2)から得られる再帰的な変数更新則である変数更新アルゴリズムについて説明する。この合意形成問題は、以下の式(2-7)のλをwで置き換えたもので表される。
Figure JPOXMLDOC01-appb-M000068
　このとき、リゾルヴェント作用素Ω2とケーリー作用素Ψ2は次のようになる。
Figure JPOXMLDOC01-appb-M000069
　ここで、上記指示関数F2を用いる場合、ケーリー作用素Ψ2は順序入替行列Pに対応することが非特許文献２に示されている。
　式(3-1)、式(3-2)を再帰的な変数更新則として表現すると、以下のようになる。式(3-5)が式(3-1)のP-R型単調作用素分割に、式(3-6)が式(3-2)のD-R型単調作用素分割に対応する。
Figure JPOXMLDOC01-appb-M000070
　ここで、変数w, λ, z(w∈Rm, λ∈Rm, z∈Rm, m=p’V)はリゾルヴェント作用素やケーリー作用素を通して得られる変数であり、いずれも双対変数である。また、tは更新回数を表す変数である。
　関数F1 *の定義からわかるように、式(3-3)には潜在変数pと双対変数wの更新が含まれている。これらの変数を更新するための方法として、非特許文献２に記載の方法を説明する。式(3-3)を以下のように変形していく。
Figure JPOXMLDOC01-appb-M000071
　なお、上記変形で第2式から第3式を導出する際、積分形を用いた。
　F1 *は潜在変数pの最適化計算を含むため、式(3-7)を解く方法は、2種類ある。ここでは、まず潜在変数pを最適化し、pをその最適値に固定したうえで、双対変数wを最適化する方法を導出することにする。潜在変数pを逐次最適化計算する（つまり、ptからpt+1を計算する）ため、pに関する罰則項をF1 *に含まれるコストに加えて計算する。
Figure JPOXMLDOC01-appb-M000072
　ここで、式(3-8)の右辺のargminの中の第3項が罰則項であり、γ>0である。罰則項を用いることで潜在変数pの逐次最適化計算が可能になる。
　次に、潜在変数pを固定したうえで、式(3-7)に含まれる双対変数wの最適化を行う。
Figure JPOXMLDOC01-appb-M000073
　また、式(3-4)は以下のように計算できる。
Figure JPOXMLDOC01-appb-M000074
　式(3-10)からわかるように、wを用いることなく、λを計算できるようになる。
　以上まとめると、再帰的な変数更新則（式(3-3)～式(3-6)）は、以下のようになる。
Figure JPOXMLDOC01-appb-M000075
　この更新則をノードごとに変数を更新できるようにすると、図１１に示すアルゴリズムが得られる。なお、Transmitj→i{・}はノードjからノードiへ変数を送信する演算を表す。
S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, "Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers", Foundations and Trends in Machine Learning, 3(1):1-122, 2011. T. Sherson, R. Heusdens, and W. B. Kleijn, "Derivation and Analysis of the Primal-Dual Method of Multipliers Based on Monotone Operator Theory", arXiv:1706.02654 金森敬文，鈴木 大慈，竹内 一郎，佐藤 一誠，"機械学習のための連続最適化"，講談社，2016年． E. K. Ryu and S. Boyd, "Primer on Monotone Operator Methods", Appl. Comput. Math., 15(1):3-43, January 2016.
　まず、第１の課題について説明する。上記の非特許文献１及び２の技術は、ノード間で主変数が送受信されているため、情報の秘密性が高くないと言える。これが第１の課題である。
　次に、第２の課題について説明する。上記の非特許文献１及び２の技術は、コスト関数が非凸関数である場合には機械学習を行うことができなかった。これが第２の課題である。
　次に、第３の課題について説明する。従来の変数更新則は、リゾルヴェント作用素やケーリー作用素を用いた単調作用素分割に基づき生成したものである。この従来の変数更新則では、場合によっては、最適解への収束に時間がかかるという問題があった。つまり、潜在変数の学習に時間がかかるという問題があった。これが第３の課題である。
　そこで本発明では、コスト関数が凸関数でない場合にも機械学習を行うことができる機械学習技術を提供することを目的とする。
　本発明の一態様は、情報を互いに送受信しながら、それぞれの入力データに基づいて共通するある１つの主変数を用いた写像を機械学習する複数のノード部を含み、上記機械学習に本来対応する非凸関数のコスト関数に代えて、コスト関数の上界となる代理凸関数を最小化するように機械学習が行われ、代理凸関数は、コスト関数の主変数に関する一次勾配の式、又は、コスト関数の主変数に関する一次勾配の式及び二次勾配の式で表されている。
　本発明によれば、コスト関数に代えてコスト関数の上界となる代理凸関数を用いることで、コスト関数が凸関数でない場合にも機械学習を行うことができる。
従来技術を説明するための図である。 従来技術を説明するための図である。 従来技術を説明するための図である。 技術的背景を説明するための図である。 機械学習システムの例を説明するためのブロック図である。 ノード部の例を説明するためのブロック図である。 機械学習方法の例を説明するための流れ図である。 機械学習方法の変形例を説明するための流れ図である。 エッジコンピューティングの一例を示す図である。 双対変数のリフティング処理の様子を示す図である。 双対変数のリフティング処理の様子を示す図である。 エッジコンピューティングにおける合意形成問題に関する従来の変数更新アルゴリズムを示す図である。 エッジコンピューティングにおける合意形成問題に関する本願の変数更新アルゴリズムを示す図である。 エッジコンピューティングにおける合意形成問題に関する本願の変数更新アルゴリズムを示す図である。 実験で用いた分散計算器の構成を示す図である。 実験結果を示す図である。 潜在変数学習装置１００の構成を示すブロック図である。 潜在変数学習装置１００の動作を示すフローチャートである。 モデル学習部１２０の構成を示すブロック図である。 モデル学習部１２０の動作を示すフローチャートである。 潜在変数学習システム２０の構成を示すブロック図である。 潜在変数学習装置２００の構成を示すブロック図である。 モデル学習部２２０の構成を示すブロック図である。 モデル学習部２２０の動作を示すフローチャートである。 モデル学習部２３０の構成を示すブロック図である。 モデル学習部２３０の動作を示すフローチャートである。
　以下、図面を参照して、この発明の一実施形態である第１実施形態について説明する。
＜技術的背景＞
　以下、秘密性を高めた合意形成アルゴリズムについて説明する。この合意形成アルゴリズムは、従来のPDMMを変形したものである。
　まず、以降の説明で用いる記号の定義について説明する。
　Vを２以上の所定の正の整数とし、~V={1,…,V}とする。
　Bを所定の正の整数とし、b=1,…,Bとし、~B={1,…,B}とする。
　ノード部iにつながっているノード部の集合を~N(i)とする。
　ノード部iにおけるノード部jに対する双対変数λi|jを構成するb個目のベクトルをλi|j,bとし、t+1回目の更新後の双対変数λi|j,bをλi|j,b (t+1)とする。
　機械学習で用いられるノード部iに対応するコスト関数をfiとする。
　双対変数λi|jの補助変数として双対補助変数zi|jを導入し、それを構成するb個目のベクトルをzi|j,bとし、t+1回目の更新後の双対補助変数zi|j,bをzi|j,b (t+1)とする。なお、zi|jの基本的な性質は、λi|jと同じである。
　双対変数λi|jの補助変数として双対補助変数yi|jを導入し、それを構成するb個目のベクトルをyi|j,bとし、t+1回目の更新後の双対補助変数yi|j,bをyi|j,b (t+1)とする。なお、yi|jの基本的な性質は、λi|jと同じである。
　ノード部iの主変数wi,bのb個目の要素をwiとし、wi,bの最適解のb個目の要素をwi,b *とする。
　Ai|jは以下の式により定義されるとする。
Figure JPOXMLDOC01-appb-M000076
　Iを単位行列とし、Oを零行列とし、σ1を所定の正の数とする。Tは更新の総回数であり、正の整数であるが、オンラインの学習を想定した場合には、定数ではない。
　解くべき問題は従来のPDMMと同じであるので、再掲する。
Figure JPOXMLDOC01-appb-M000077
　また、この問題をオペレータ分割法で解くという点についても従来のPDMMと同様である。以後、オペレータ分割法の一つであるP-R分割を用いた例について説明する。双対変数λbの補助変数として２種類の双対補助変数yb,zbをを以後用いる。
　P-R分割に基づいて、変数群(主変数，双対変数，双対補助変数)を最適化するステップは以下で書ける。
Figure JPOXMLDOC01-appb-M000078
　上記の式において、「∈」の記号は、集合の要素を表すのではなく、右辺の演算結果を左辺に代入することを意味する。通常、こうした操作は「＝」を用いて表現することが多いが、コスト関数に不連続な閉真凸関数を用いた場合に、非可逆な変換が行われることがある(1対1対応しない演算をすることがあり得る)。「＝」は通常、1対1対応するような変換(関数)に用いられる記号であるため、それと区別するために「∈」の記号を用いることとする。
　ここで、Cn (n=1,2)はケーリー演算子(Cayley operator)である。
Figure JPOXMLDOC01-appb-M000079
　Rn (n=1,2)は リゾルヴェント演算子(Resolvent operator)である。
Figure JPOXMLDOC01-appb-M000080
　Tn(n=1,2)はモノトーン演算子(Monotone operator)である。問題を構成するf*やδ(I-P)とも真凸閉関数であるので、その双対変数に関する偏微分はモノトーン演算子になる。
Figure JPOXMLDOC01-appb-M000081
　理論背景については詳細をここに記述しないが、P-R分割は高速な収束を保証する最適化方式である。P-R分割による最適化zb∈C2C1zbを分解表現すると以下になる。
Figure JPOXMLDOC01-appb-M000082
　なお、２番目のケーリー演算子C2が順序入れ替え行列Pに対応するということについては、非特許文献２にその証明が掲載されている。一番上の双対変数をリゾルヴェント演算子を使った更新は、以下のように変形できる。
Figure JPOXMLDOC01-appb-M000083
　この式に含まれるf*を双対変数に関する閉凸真関数として導出したい。それがノード間で交換する情報量を削減につながるから。その過程について以下説明する。まず、f*の定義を再掲する。
Figure JPOXMLDOC01-appb-M000084
なお、一つの事例として、最小二乗問題をコストとして扱う場合には、以下となる。
Figure JPOXMLDOC01-appb-M000085
以後は、説明を分かりやすくするために、最小二乗問題をコストとして扱った場合の更新式について導出する。
　括弧内を微分すると、wの最適解は以下で得られる。このように、最小二乗問題をコストとして扱った場合のwの最適解w*は、双対変数の式で表される。
Figure JPOXMLDOC01-appb-M000086
　このw*をf*に代入することで、f*をλの関数として表せる。ここで、Q=XXTである。
Figure JPOXMLDOC01-appb-M000087
　ここで、Q=XXTである。
　P-R分割に含まれる双対変数の更新式を再掲する。
Figure JPOXMLDOC01-appb-M000088
　最小二乗問題をコストとして扱った場合、括弧内を双対変数に関して微分すると、以下のようになる。
Figure JPOXMLDOC01-appb-M000089
　だから、最小二乗問題をコストとして扱った場合の双対変数に関する最適化は以下で得られる。
Figure JPOXMLDOC01-appb-M000090
　この工夫は、双対変数λを最適化する中で、暗に主変数wも最適化されることを意味している。そして、双対補助変数yをノード間で交換するだけで、P-R分割ベースの分散最適化処理が実現できる。この時点で以下のようにアルゴリズムを書き換えられる。ここでは一般形式で記述する。 
　T回更新するとして、t∈{0,…,T-1}に対して、以下の(1)から(5)の処理を行う。(2)主変数更新の処理は、行われなくてもよい。なぜならば、wの最適解であるw*はλの式で表されるため、λの最適化過程において、wの更新を必要としないためである。（λが最適化されればwも暗に最適化されたことを意味する）
(1)双対変数更新（ここでは、最小二乗問題に限定せず、コストを一般形式として記述する。）
Figure JPOXMLDOC01-appb-M000091
(2)主変数更新（ここでは、最小二乗問題に限定せず、コストを一般形式として記述する。）
Figure JPOXMLDOC01-appb-M000092
(3)双対補助変数更新
Figure JPOXMLDOC01-appb-M000093
(4) 毎回である必要はないし、エッジごとに独立(非同期)でよいが、双対補助変数をノード間で更新する。ここで、「・」を任意の情報として、Nodej←Nodei(・)は、ｉ番目のノード部iがノード部jに情報「・」を送信することを意味する。
Figure JPOXMLDOC01-appb-M000094
(5) 交換して得た情報を使って双対補助変数更新
Figure JPOXMLDOC01-appb-M000095
　なお、最後の(5)のステップについては、以下の演算と置き換えることで、収束性を低くする代わりに、収束過程において高い安定性を見込めるDouglas Rachford (D-R)分割になる。通常βは1/2が使われる。
Figure JPOXMLDOC01-appb-M000096
　なお、上記の主変数、双対変数の更新は、一般形式のコスト関数を用いている。以下のコスト関数を用いた場合には、合意形成アルゴリズムは以下のようになる。
Figure JPOXMLDOC01-appb-M000097
　T回更新するとして、t∈{0,…,T-1}に対して、以下の(1)から(5)の処理を行う。なお、(2)主変数更新の処理は、行われなくてもよい。なぜならば、wの最適解であるw*はλの式で表されるため、λの最適化過程において、wの更新を必要としないためである。（λが最適化されればwも暗に最適化されたことを意味する。）
(1)双対変数更新
Figure JPOXMLDOC01-appb-M000098
(2)主変数更新
Figure JPOXMLDOC01-appb-M000099
(3)双対補助変数更新
Figure JPOXMLDOC01-appb-M000100
(4) 毎回である必要はないし、エッジごとに独立(非同期)でよいが、双対補助変数をノード間で更新する。
Figure JPOXMLDOC01-appb-M000101
(5) 交換して得た情報を使って双対補助変数更新
Figure JPOXMLDOC01-appb-M000102
　なお、最後の(5)のステップについては、以下の演算と置き換えることで、収束性を低くする代わりに、収束過程において高い安定性を見込めるDouglas Rachford (D-R)分割になる。通常βは1/2が使われる。
Figure JPOXMLDOC01-appb-M000103
　双対補助変数yをノード間で交換しているが、変数の性質は双対変数λと同等と言ってよい。その双対変数は以下のように算出される。
Figure JPOXMLDOC01-appb-M000104
　主変数wには、データの統計的性質が濃く反映されることが多いが、双対変数の統計的性質は、そのルジャンドル変換後のデータに左右される。ルジャンドル変換は関数の構造を知っていないと主変数には戻せないため、双対変数やその双対補助変数をノード間で伝送するのは、秘密性の高いデータ通信と言える。
＜第１実施形態＞
　図５に示すように、機械学習システムは、複数のノード部1,…,V、複数のセンサ部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγ、インターネット0N、LAN 1N,…,VNを例えば備えている。複数のノード部1,…,Vのそれぞれは、サーバ、PC等の情報処理機器である。ノード部1,…,Vのそれぞれには、図６で示すように、学習部１０と送受信部１１が設けられており、学習部１０内には記憶部１２が設けられている。記憶部１２には、以下に説明する処理及び計算に必要なデータが記憶されているとする。
　センサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγは、様々な環境(例えば、家、工場、野外及びビル)に、分散して配置された多数のセンサー(例えば、マイク、カメラ、温度計)である。図５の例では、センサー部は1S1,…,1Sαはノード部1に対応するセンサーである。すなわち、センサー部は1S1,…,1Sαはノード部1の学習部１０での機械学習で用いられるデータを取得するセンサーであり、センサー部は1S1,…,1Sγのそれぞれはノード部1とLAN 1Nで接続されている。その他のセンサー部についても同様である。それらのセンサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγを通じて得られたデータは、複数のノード部1,…,V(例えば、サーバ、PC)に蓄積される。なお、データは、センサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγから得られるものに限らず、入力装置やWeb等から得られる文字データ等でも構わない。また、図５の例ではセンサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγはLAN1N,…,VNでノード部1,…,Vに接続されているが、センサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγはインターネット0Nを介してノード部1,…,Vに接続されていてもよいし、その他の接続手段で接続されていてもよいし、要するに、センサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγが得たデータをノード部1,…,Vが用いるようにされていればよい。
　図５の例ではノード部1,…,Vはインターネット0Nを介して接続されているが、ノード部1,…,V間は、全結合ではなく疎に結合されていてもよく、何らかのデータを交換できる関係にあればよい。エッジの連結構造についての制約はなく、木構造、循環／円構造でもなんでもよい。要するに、全てのノード部1,…,Vが直接又は間接的につながっている。すなわち、エッジの連結構造は、分割された構造ではない。
　複数のノード部1,…,Vは、送受信部１１からデータの受信、送受信部１１からのデータの送信、記憶部１２からデータの読み込み、記憶部１２に対するデータの書き込みを適宜行いながら、以下に説明する機械学習処理を行う。機械学習処理は、複数のノード部1,…,Vが図７のステップＳ１からステップＳ８の処理を行うことにより例えば実現される。
　ノード部1,…,Vは、t=0とする（ステップＳ１）。
　ノード部i（より詳細には、ノード部iの学習部１０）は、ノード部iに対応するセンサー部により得られたデータを用いて、以下の式に基づいて双対変数の更新を行う（ステップＳ２）。すなわち、ノード部iは、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式により定義されるλi|j,b (t+1)の計算を行う。
Figure JPOXMLDOC01-appb-M000105
　ノード部i（より詳細には、ノード部iの学習部１０）は、以下の式に基づいて主変数の更新を行う（ステップＳ３）。すなわち、ノード部iは、i∈~V,b∈~Bのそれぞれに対して、以下の式により定義されるwi,b (t+1)の計算を行う。なお、ステップＳ３の処理は、主変数が必要な場合に行われる。言い換えれば、ステップＳ３の処理は、毎回行われなくてもよい。
Figure JPOXMLDOC01-appb-M000106
　ノード部i（より詳細には、ノード部iの学習部１０）は、以下の式に基づいて双対補助変数の更新を行う（ステップＳ４）。すなわち、ノード部iは、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式により定義されるyi|j,b (t+1)の計算を行う。なお、このステップＳ４の処理は、ステップＳ５において双対補助変数yi|j,b (t+1)を送信する場合以外は行わなくてもよい。
Figure JPOXMLDOC01-appb-M000107
　ノード部i（より詳細には、ノード部iの送受信部１１）は、双対補助変数yi|j,b (t+1)を別のノード部jに対して送信する処理と、別のノード部jが送信した双対補助変数yj|i,b (t+1)を受信する処理と、の少なくとも何れかを行う、すなわち、以下の式に示すようにノード部の間で情報交換を行う（ステップＳ５）。例えば、ノード部iは、ノード部iの学習部１０が得た双対補助変数yi|j,b (t+1)をノード部iの送受信部１１がノード部ｊに対して送信し、ノード部iの送受信部１１がノード部ｊから受信した双対補助変数をノード部iの学習部１０に双対補助変数yj|i,b (t+1)として入力するように動作する。なお、ステップＳ５の処理は毎回行わなくてよいし、ノード間で非同期でよい。例えば、tが偶数のときにのみ、全てのノード部iが、ノード部iが得た双対補助変数yi|j,b (t+1)を別のノード部jに対して送信する処理と、別のノード部jが出力した双対補助変数yj|i,b (t+1)を受信する処理と、の両方を行い、tが奇数のときには何れのノード部iも双対補助変数の送信も受信もしないようにしてもよい。また、全てのノード部i,jではなく、一部のノード部iのみが一部のノード部jに対してのみに以下の式に示す処理を行ってもよい。言い換えれば、i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jに双対補助変数yi|j,b (t+1)を送信し、ノード部jが出力した双対補助変数yj|i,b (t+1)を受信する。
Figure JPOXMLDOC01-appb-M000108
　ノード部i（より詳細には、ノード部iの学習部１０）は、以下の式に基づいて、双対補助変数の更新を行う（ステップＳ６）。すなわち、i∈~V, j∈~N(i), b∈~Bとして、ノード部iが、zi|j,b (t+1)=yj|i,b (t+1)とする処理を行う。なお、ステップＳ６の処理は、ステップＳ５において双対補助変数yj|i,b (t+1)を受信した場合以外は行わなくてよい。すなわち、ステップＳ６の処理は、双対補助変数yj|i,b (t+1)を受信したノード部iのみが行えばよい。
Figure JPOXMLDOC01-appb-M000109
　ノード部1,…,Vは、t=t+1とする（ステップＳ７）。すなわち、ノード部1,…,Vは、tを１だけインクリメントする。
　ノード部1,…,Vは、t=Tであるか判定し（ステップＳ８）、t=Tであれば処理を終了する。t=Tでない場合には、ステップＳ２の処理に戻る。
　このように、それぞれ入力データが記憶されており、情報を互いに送受信しながら、教師データ及び入力データに基づいて主変数wを用いた写像を機械学習する複数のノード部を含む機械学習システムにおいて、複数のノード部iは、機械学習において用いられる双対変数を最適化すれば、主変数も最適化されるように、かつ、主変数ではなく、双対変数を互いに送受信しながら、機械学習を行う。これにより、ノード部iの間で主変数が送受信されないため、従来よりも秘密性が高い機械学習を行うことができる。
《変形例》
［変形例１］
　一般形式のコスト関数ではなく、以下のコスト関数を用いた場合には、
Figure JPOXMLDOC01-appb-M000110
ステップＳ２において、ノード部iは、以下の式に基づいて双対変数の更新を行う。
Figure JPOXMLDOC01-appb-M000111
また、ステップＳ３において、ノード部iは、以下の式に基づいて主変数の更新を行う。
Figure JPOXMLDOC01-appb-M000112
［変形例２］
　i=1,…,Vとして、ノード部iにDi個のデータが蓄積されているが、Diは時間によって変化してもよい。オンラインの最適化にも対応可能である。このとき、コスト関数は、以下のよう書ける
Figure JPOXMLDOC01-appb-M000113
［変形例３］
　ステップＳ５において、ノード部iは、双対補助変数yi|j,b (t+1)ではなく、双対変数λi|j,b (t+1)を送受信してもよい。
　この場合、ステップＳ６の処理は行われない。ステップＳ６以外のステップの処理は上記と同様に行われる。
［変形例４］
　以下では、伝送容量を圧縮するための工夫について説明する。
　最適化処理が収束するにつれて、更新差分が0に近づく。その性質を利用して、非可逆な圧縮処理をすれば、更に伝送容量を低く抑えられるはずである。
　情報圧縮の方法については様々考えられるが、更新差分を伝送しあうというアイデアを基軸に、(i) フロアリングベースの圧縮処理と、(ii) エントロピー符号化ベースの圧縮処理がある。
　まず、参照データがときどき更新されるとし、そのデータとの差分データを変数vとおく。ここで、vi|j,b (t+1)は、更新差分情報である。vi|j,b (t+1)は、収束するほど、0に近い数字に偏る傾向がある。vi|j,b (t+1)は、本来、ノード間で交換したい情報である。mi|j,b (export)は、既に得ている参照情報である。
Figure JPOXMLDOC01-appb-M000114
　そのvに圧縮処理Cを適用する。
Figure JPOXMLDOC01-appb-M000115
　(i) フロアリングベースの圧縮処理の場合には、vを構成するそれぞれの要素と閾値thrを比較し、閾値以下であれば0にするような処理をする。thrは、所定の0より大きな所定の数であり、例えば1×10-5等の非常に小さな数である。
Figure JPOXMLDOC01-appb-M000116
　(ii) エントロピー符号化ベースの圧縮処理の場合には、出現確率に応じてシンボルを割り当てるような処理をしてuを生成する。例えば、出現確率が値に対して、短いシンボルを割り当てることによりuを生成する。
　このとき、コスト関数を一般形式で記述した場合の合意形成アルゴリズムは以下のようになる。
　T回更新するとして、t∈{0,…,T-1}に対して、以下の(1)から(10)の処理を行う。(2)主変数更新の処理は、行われなくてもよい。なぜならば、wの最適解であるw*はλの式で表されるため、λの最適化過程において、wの更新を必要としないためである。（λが最適化されればwも暗に最適化されたことを意味する）
(1)双対変数更新（ここでは、最小二乗問題に限定せず、コストを一般形式として記述する。）
Figure JPOXMLDOC01-appb-M000117
(2)主変数更新（ここでは、最小二乗問題に限定せず、コストを一般形式として記述する。）
Figure JPOXMLDOC01-appb-M000118
(3)双対補助変数更新
Figure JPOXMLDOC01-appb-M000119
　mod (t, Tinterval)=0である場合には、以下の(4)から(6)の処理を行う。すなわち、たまに参照データを更新する。ここで、Tintervalは、所定の正の整数である。
(4) 参照データの更新
Figure JPOXMLDOC01-appb-M000120
(5) ノード間で情報交換 (エッジごとに独立（非同期）でよい。)
Figure JPOXMLDOC01-appb-M000121
(6)交換して得た情報を使って双対補助変数更新
Figure JPOXMLDOC01-appb-M000122
　mod (t, Tinterval)=0でない場合には、以下の(7)から(10)の処理を行う。すなわち、ほとんどの時刻で更新差分を伝送しあう。
(7) 更新差分を計算
Figure JPOXMLDOC01-appb-M000123
(8) データを圧縮する
Figure JPOXMLDOC01-appb-M000124
(9) 圧縮されたデータをノード間で交換
Figure JPOXMLDOC01-appb-M000125
(10) 交換して得た情報を使って双対補助変数更新
Figure JPOXMLDOC01-appb-M000126
　このような伝送容量の削減を行うために、上記の実施形態において、ノード部iは、ステップＳ５からステップＳ６の処理に代えて、以下に説明するステップＳ９からステップＳ１６の処理を行えばよい。他の処理は、上記の実施形態と同様であるため、ここでは重複説明を省略する。図８に、伝送容量の削減を行った機械学習方法の例の流れ図を示す。
　ノード部1,…,Vは、mod (t, Tinterval)=0であるか判定する（ステップＳ９）。
　mod (t, Tinterval)=0である場合には、ノード部i（より詳細には、ノード部iの学習部１０）は、以下の式に基づいて参照データの更新を行う（ステップＳ１０）。すなわち、ノード部iは、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式に基づいて参照データの更新を行う（ステップＳ１０）。
Figure JPOXMLDOC01-appb-M000127
　ノード部i（より詳細には、ノード部iの送受信部１１）は、mi|j,b (export)を別のノード部jに対して送信する処理と、別のノード部jが送信したmj|i,b (import)を受信する処理と、の少なくとも何れかを行う、すなわち、以下の式に示すようにノード部の間で情報交換を行う（ステップＳ１１）。例えば、ノード部iは、ノード部iの学習部１０が得たmi|j,b (export)をノード部iの送受信部１１がノード部ｊに対して送信し、ノード部iの送受信部１１がノード部ｊから受信したmj|i,b (import)をノード部iの学習部１０に入力するように動作する。また、全てのノード部i,jではなく、一部のノード部iのみが一部のノード部jに対してのみに以下の式に示す処理を行ってもよい。言い換えれば、i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jにmi|j,b (export)を送信し、ノード部jが出力したmj|i,b (import)を受信する（ステップＳ１１）。
Figure JPOXMLDOC01-appb-M000128
　ノード部i（より詳細には、ノード部iの学習部１０）は、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式に示すように、交換して得た情報を使って双対補助変数zi|j,b (t+1)の更新を行う（ステップＳ１２）。
Figure JPOXMLDOC01-appb-M000129
　mod (t, Tinterval)=0でない場合には、ノード部i（より詳細には、ノード部iの学習部１０）は、以下の式に基づいて更新差分を計算する（ステップＳ１３）。すなわち、ノード部iは、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式により定義されるvi|j,b (t+1)の計算を行う。
Figure JPOXMLDOC01-appb-M000130
　ノード部i（より詳細には、ノード部iの学習部１０）は、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式に基づいて、データを圧縮することにより符号をui|j,b (t+1)生成する（ステップＳ１４）。このデータの圧縮は、非可逆であってもよい。ここで、Cは、フロアリングベースの圧縮処理、エントロピー符号化ベースの圧縮処理等の所定の圧縮処理を意味する。
Figure JPOXMLDOC01-appb-M000131
　ノード部i（より詳細には、ノード部iの送受信部１１）は、ui|j,b (t+1)を別のノード部jに対して送信する処理と、別のノード部jが送信したuj|i,b (t+1)を受信する処理と、の少なくとも何れかを行う、すなわち、以下の式に基づいて、圧縮されたデータをノード部間で交換する（ステップＳ１５）。例えば、ノード部iは、ノード部iの学習部１０が得たui|j,b (t+1)をノード部iの送受信部１１がノード部ｊに対して送信し、ノード部iの送受信部１１がノード部ｊから受信したuj|i,b (t+1)をノード部iの学習部１０に入力するように動作する。また、全てのノード部i,jではなく、一部のノード部iのみが一部のノード部jに対してのみに以下の式に示す処理を行ってもよい。言い換えれば、i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jに符号ui|j,b (t+1)を送信し、ノード部jが出力した符号uj|i,b (t+1)を受信する（ステップＳ１５）。
Figure JPOXMLDOC01-appb-M000132
　ノード部i（より詳細には、ノード部iの学習部１０）は、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式に基づいて、双対補助変数zi|j,b (t+1)の更新を行う（ステップＳ１６）。
Figure JPOXMLDOC01-appb-M000133
　なお、ステップ１２において、ノード部iは、以下に例示するD-R分割ベースの更新を行ってもよい。通常βは1/2が使われる。
Figure JPOXMLDOC01-appb-M000134
　また、ステップＳ１６において、ノード部iは、以下に例示するD-R分割ベースの更新を行ってもよい。通常βは1/2が使われる。
Figure JPOXMLDOC01-appb-M000135
　その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
《プログラム及び記録媒体》
　機械学習システムを、１つのコンピュータによって実現してもよい。この場合、機械学習システムの各部が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、機械学習システムの処理がコンピュータ上で実現される。
　この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
　また、各部の処理は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理の少なくとも一部をハードウェア的に実現することとしてもよい。
　以下、図面を参照して、この発明の一実施形態である第２実施形態について説明する。
＜技術的背景＞
　以下、非凸関数に対する最適化にも適用できる合意形成アルゴリズムについて説明する。
　まず、以降の説明で用いる記号の定義について説明する。
　Vを２以上の所定の正の整数とし、~V={1,…,V}とする。
　Bを所定の正の整数とし、b=1,…,Bとし、~B={1,…,B}とする。
　ノード部iにつながっているノード部の集合を~N(i)とする。
　ノード部iにおけるノード部jに対する双対変数λi|jを構成するb個目のベクトルをλi|j,bとし、t+1回目の更新後の双対変数λi|j,bをλi|j,b (t+1)とする。
　双対変数λi|jの補助変数として双対補助変数zi|jを導入し、それを構成するb個目のベクトルをzi|j,bとし、t+1回目の更新後の双対補助変数zi|j,bをzi|j,b (t+1)とする。なお、zi|jの基本的な性質は、λi|jと同じである。
　双対変数λi|jの補助変数として双対補助変数yi|jを導入し、それを構成するb個目のベクトルをyi|j,bとし、t+1回目の更新後の双対補助変数yi|j,bをyi|j,b (t+1)とする。なお、yi|jの基本的な性質は、λi|jと同じである。
　ノード部iの主変数wiのb個目の要素をwi,bとし、t回目の更新後の双対補助変数wi,bをwi,b (t)とする。
　機械学習で用いられるノード部iに対応するコスト関数をfiとし、コスト関数fiのwi,b (t)に関する一次勾配を∇fi(wi,b (t))とする。
　Ai|jは以下の式により定義されるとする。
Figure JPOXMLDOC01-appb-M000136
　Iを単位行列とし、Oを零行列とし、σ1を所定の正の数とする。Tは更新の総回数であり、正の整数であるが、オンラインの学習を想定した場合には、定数ではない。ηを正の数とする。
　基本的なアイデアは、非凸関数を凸関数によって置き換えることである。この操作は、非特許文献３の15.3節にある近接勾配法の考え方に基づく。関数fの勾配が以下のようにリプシッツ連続であると仮定する。ここで、fは非凸の関数であってもよい。
Figure JPOXMLDOC01-appb-M000137
　ここで、ηは、fiの勾配の平滑さを表しており、ηを十分小さい値にすれば、多くの場合で満たされる仮定である。例えば、h=0.001とする。上記の式を満たすとき、fiは1/η平滑関数と呼ばれる。
　fiが1/η平滑関数であるとき、以下の不等式関係が成り立つ。
Figure JPOXMLDOC01-appb-M000138
　ここから以下を導ける。ここで、x,yを任意のベクトルとして、<x,y>はxとyの内積を表す。なお、ηが小さいほど、右辺の凸関数の勾配が大きい(鋭い関数になる)ので、コストの上界であるという条件を満たす。このため、ηは、小さい数であってもよい。ただし、ηが小さすぎると、更新のステップが小さくなるので、最適解にたどり着くまでに時間がかかるという特徴がある。
Figure JPOXMLDOC01-appb-M000139
　この式は、コスト関数fiの上界となる凸関数(右辺)を導出したことを示している。たとえ、fiが非凸関数であったとしても、その代わりに上界となる代理凸関数(右辺)を最小化するという手段をとれば、PDMMの合意型エッジコンピューティングの考え方を非凸関数にも取り入れられるはずである。
　ここで、補足説明として、コスト関数fiの代わりにその上界となる代理凸関数を最小化するとはどういうことかについて説明する。
　図４において、実線は元々のコスト関数fiを表す。図４では、コスト関数fiを非凸関数として書いている。図４において、一点鎖線は、上界となる代理凸関数giを表す。
Figure JPOXMLDOC01-appb-M000140
　ここで、fi(wi,b (t))は、更新時刻tにおける関数出力であり、計算可能である。また、∇fi(wi,b (t))は、更新時刻tにおける関数の勾配であり、DNNを想定した場合、確率的最適化の枠組みで計算可能である。
　このため、fiに関する一次勾配さえ計算できるのであれば、上記の代理凸関数giは計算できる。DNNはそれに該当する。
　なお、代理関数は、上記以外の別のものでもよい。先に示した代理凸関数giは、元のコストの上界を表現しており、コスト関数の一次勾配さえ求まればよいという利点があった。それは非凸関数にも適用できるというメリットでもある。
　しかし、もし、コスト関数の二次勾配が求まるのであれば、以下のような代理関数を使ってもよい。以下の式の下線部分を代理関数とする。
Figure JPOXMLDOC01-appb-M000141
　これは、二次のテーラー展開を用いて表現した(上界ではなく)近似関数である。この代理関数を用いると、元のコスト関数に対する近似精度が高いので、元のコストを小さくすることとのギャップがより小さくなることが見込める。
　代理凸関数の概念としては、元のコスト関数を最小化することと相反しない凸関数であり、上界や近似といった考え方で実装できる。具体的には、元のコスト関数の主変数に関する一次、場合によっては二次の勾配を使って計算できる凸関数である。
　以下では、コスト関数を代理凸関数giとした場合のPDMMアルゴリズムの導出について説明する。
Figure JPOXMLDOC01-appb-M000142
　この時、双対問題は以下で書ける。
Figure JPOXMLDOC01-appb-M000143
　変数の定義は以下の通りである。なお、以下のfは一例であり、他のfを用いてもよい。
Figure JPOXMLDOC01-appb-M000144
　主変数及び双対変数のそれぞれで合意形成するという条件は以下で書ける。
Figure JPOXMLDOC01-appb-M000145
　関数gの凸共役関数g*を解くことで、wの最適解を導く。
Figure JPOXMLDOC01-appb-M000146
　括弧内を最大化するwは、以下である。
Figure JPOXMLDOC01-appb-M000147
　このプロセスは各ノードごとに分割して書くことができる。
Figure JPOXMLDOC01-appb-M000148
　これを双対関数に代入することで、以下の式を得る。このように、双対変数λに関する真凸閉関数にする。
Figure JPOXMLDOC01-appb-M000149
　元の双対問題は以下で書ける。
Figure JPOXMLDOC01-appb-M000150
　この問題を解くために、PDMMと同様に以下のようなコストを設計する。
Figure JPOXMLDOC01-appb-M000151
　この問題をP-R分割で解く場合には、以下の演算で構成されることは従来法で説明した。
Figure JPOXMLDOC01-appb-M000152
　上記の式において、「∈」の記号は、集合の要素を表すのではなく、右辺の演算結果を左辺に代入することを意味する。通常、こうした操作は「＝」を用いて表現することが多いが、コスト関数に不連続な閉真凸関数を用いた場合に、非可逆な変換が行われることがある(1対1対応しない演算をすることがあり得る)。「＝」は通常、1対1対応するような変換(関数)に用いられる記号であるため、それと区別するために「∈」の記号を用いることとする。
　このうち、一番上の演算は、以下に対応している。
Figure JPOXMLDOC01-appb-M000153
　g*を再掲する。
Figure JPOXMLDOC01-appb-M000154
　括弧内を最大化するw(主変数の最適解)を求める。すなわち、上記式の括弧内を微分した値を０とするwb *を求めると以下のようになる。
Figure JPOXMLDOC01-appb-M000155
　次に、P-R分割の一番上の演算を満たす双対変数の最適解を導く。
Figure JPOXMLDOC01-appb-M000156
　括弧内を双対変数に関して微分し、途中計算を省略するが以下の式が得られる。
Figure JPOXMLDOC01-appb-M000157
　ノードごとの演算に分割すると、P-R分割ベースで代理凸関数を用いて変数最適化アルゴリズムが得られる。このアルゴリズムのことを、Quadratic PDMMとも呼ぶ。Quadratic PDMMは、以下のようになる。
　T回更新するとして、t∈{0,…,T-1}に対して、以下の(1)から(5)の処理を行う。
(1)双対変数更新
Figure JPOXMLDOC01-appb-M000158
(2)主変数更新
Figure JPOXMLDOC01-appb-M000159
(3)双対補助変数更新
Figure JPOXMLDOC01-appb-M000160
(4) 毎回である必要はないし、エッジごとに独立(非同期)でよいが、双対補助変数をノード間で更新する。
Figure JPOXMLDOC01-appb-M000161
(5) 交換して得た情報を使って双対補助変数更新
Figure JPOXMLDOC01-appb-M000162
　なお、最後の(5)のステップについては、以下の演算と置き換えることで、収束性を低くする代わりに、収束過程において高い安定性を見込めるDouglas Rachford (D-R)分割になる。通常βは1/2が使われる。
Figure JPOXMLDOC01-appb-M000163
　Quadratic-PDMMアルゴリズムでは、代理凸関数が更新時刻ごとに変わっている点で秘密性は高いと言える。
　Quadratic-PDMMアルゴリズムがノード間で異質なデータセットを持っている場合にも、収束することを示すために、収束率を導出する。問題は、以下のように２種類の凸関数で構成されたコストの最小化問題であった。
Figure JPOXMLDOC01-appb-M000164
　まず、gは、1/η-強凸関数であることを示す。
　もし、g(wb)-(1/(2η))||wb||2が凸関数であれば、gが 1/η-強凸関数であることと等価である（例えば、非特許文献３の2.2.5節参照。）。
Figure JPOXMLDOC01-appb-M000165
　ここで、ηが十分に小さいことが仮定されていることから、cosθは負値になるだろう。
Figure JPOXMLDOC01-appb-M000166
　そのとき、g(wb)-(1/(2η))||wb||2は凸関数になるから、gは1/η-強凸関数であろう。
　次に、非特許文献３の2.2.5節より、gが1/η-強凸関数であるとき、g*はη-平滑関数になることが知られている。そのとき、以下の性質を満たす。
Figure JPOXMLDOC01-appb-M000167
　近接写像関数を以下のように定義する。
Figure JPOXMLDOC01-appb-M000168
　近接写像の定義より、以下の関係を得られる。
Figure JPOXMLDOC01-appb-M000169
　そのとき、
Figure JPOXMLDOC01-appb-M000170
　g*がη-平滑関数であるから、以下の関係を満たす。
Figure JPOXMLDOC01-appb-M000171
　そのとき、以下の関係を満たす。
Figure JPOXMLDOC01-appb-M000172
Figure JPOXMLDOC01-appb-M000173
と代入すると、以下の関係を得られる。
Figure JPOXMLDOC01-appb-M000174
　Gは、η-平滑関数であるg*と凸性の非常に強い指示関数δで構成される。指示関数がGに含まれているので、Gは強い凸性の関数であると言える。Gをξ-強凸関数であると仮定すると、以下を満たす。
Figure JPOXMLDOC01-appb-M000175
　そのとき、以下を満たす。
Figure JPOXMLDOC01-appb-M000176
　よって以下になる。
Figure JPOXMLDOC01-appb-M000177
　式変形をすると、収束率が求まる。
Figure JPOXMLDOC01-appb-M000178
　ξは十分値が大きく、ηは十分小さな値であることを仮定しているので、収束率は高い。また、この中にデータセットの異質性に依存する変数が存在しないことから、データセットの統計的性質に依存しないで、収束することが想定される。
＜第２実施形態＞
　図５に示すように、機械学習システムは、複数のノード部1,…,V、複数のセンサ部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγ、インターネット0N、LAN 1N,…,VNを例えば備えている。複数のノード部1,…,Vのそれぞれは、サーバ、PC等の情報処理機器である。ノード部1,…,Vのそれぞれには、図６で示すように、学習部１０と送受信部１１が設けられており、学習部１０内には記憶部１２が設けられている。記憶部１２には、以下に説明する処理及び計算に必要なデータが記憶されているとする。
　センサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγは、様々な環境(例えば、家、工場、野外及びビル)に、分散して配置された多数のセンサー(例えば、マイク、カメラ、温度計)である。図５の例では、センサー部は1S1,…,1Sαはノード部1に対応するセンサーである。すなわち、センサー部は1S1,…,1Sαはノード部1の学習部１０での機械学習で用いられるデータを取得するセンサーであり、センサー部は1S1,…,1Sγのそれぞれはノード部1とLAN 1Nで接続されている。その他のセンサー部についても同様である。それらのセンサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγを通じて得られたデータは、複数のノード部1,…,V(例えば、サーバ、PC)に蓄積される。なお、データは、センサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγから得られるものに限らず、入力装置やWeb等から得られる文字データ等でも構わない。また、図５の例ではセンサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγはLAN1N,…,VNでノード部1,…,Vに接続されているが、センサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγはインターネット0Nを介してノード部1,…,Vに接続されていてもよいし、その他の接続手段で接続されていてもよいし、要するに、センサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγが得たデータをノード部1,…,Vが用いるようにされていればよい。
　図５の例ではノード部1,…,Vはインターネット0Nを介して接続されているが、ノード部1,…,V間は、全結合ではなく疎に結合されていてもよく、何らかのデータを交換できる関係にあればよい。エッジの連結構造についての制約はなく、木構造、循環／円構造でもなんでもよい。要するに、全てのノード部1,…,Vが直接又は間接的につながっている。すなわち、エッジの連結構造は、分割された構造ではない。
　複数のノード部1,…,Vは、送受信部１１からデータの受信、送受信部１１からのデータの送信、記憶部１２からデータの読み込み、記憶部１２に対するデータの書き込みを適宜行いながら、以下に説明する機械学習処理を行う。機械学習処理は、複数のノード部1,…,Vが図７のステップＳ１からステップＳ８の処理を行うことにより例えば実現される。
　ノード部1,…,Vは、t=0とする（ステップＳ１）。
　ノード部i（より詳細には、ノード部iの学習部１０）は、ノード部iに対応するセンサー部により得られたデータを用いて、以下の式に基づいて双対変数の更新を行う（ステップＳ２）。すなわち、ノード部iは、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式により定義されるλi|j,b (t+1)の計算を行う。
Figure JPOXMLDOC01-appb-M000179
　ノード部i（より詳細には、ノード部iの学習部１０）は、以下の式に基づいて主変数の更新を行う（ステップＳ３）。すなわち、ノード部iは、i∈~V,b∈~Bのそれぞれに対して、以下の式により定義されるwi,b (t+1)の計算を行う。
Figure JPOXMLDOC01-appb-M000180
　ノード部i（より詳細には、ノード部iの学習部１０）は、以下の式に基づいて双対補助変数の更新を行う（ステップＳ４）。すなわち、ノード部iは、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式により定義されるyi|j,b (t+1)の計算を行う。なお、このステップＳ４の処理は、ステップＳ５において双対補助変数yi|j,b (t+1)を送信する場合以外は行わなくてもよい。
Figure JPOXMLDOC01-appb-M000181
　ノード部i（より詳細には、ノード部iの送受信部１１）は、双対補助変数yi|j,b (t+1)を別のノード部jに対して送信する処理と、別のノード部jが送信した双対補助変数yj|i,b (t+1)を受信する処理と、の少なくとも何れかを行う、すなわち、以下の式に示すようにノード部の間で情報交換を行う（ステップＳ５）。例えば、ノード部iは、ノード部iの学習部１０が得た双対補助変数yi|j,b (t+1)をノード部iの送受信部１１がノード部ｊに対して送信し、ノード部iの送受信部１１がノード部ｊから受信した双対補助変数をノード部iの学習部１０に双対補助変数yj|i,b (t+1)として入力するように動作する。なお、ステップＳ５の処理は毎回行わなくてよいし、ノード間で非同期でよい。例えば、tが偶数のときにのみ、全てのノード部iが、ノード部iが得た双対補助変数yi|j,b (t+1)を別のノード部jに対して送信する処理と、別のノード部jが出力した双対補助変数yj|i,b (t+1)を受信する処理と、の両方を行い、tが奇数のときには何れのノード部iも双対補助変数の送信も受信もしないようにしてもよい。また、全てのノード部i,jではなく、一部のノード部iのみが一部のノード部jに対してのみに以下の式に示す処理を行ってもよい。言い換えれば、i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jに双対補助変数yi|j,b (t+1)を送信し、ノード部jが出力した双対補助変数yj|i,b (t+1)を受信する。
Figure JPOXMLDOC01-appb-M000182
　ノード部i（より詳細には、ノード部iの学習部１０）は、以下の式に基づいて、双対補助変数の更新を行う（ステップＳ６）。すなわち、i∈~V, j∈~N(i), b∈~Bとして、ノード部iが、zi|j,b (t+1)=yj|i,b (t+1)とする処理を行う。なお、ステップＳ６の処理は、ステップＳ５において双対補助変数yj|i,b (t+1)を受信した場合以外は行わなくてよい。すなわち、ステップＳ６の処理は、双対補助変数yj|i,b (t+1)を受信したノード部iのみが行えばよい。
Figure JPOXMLDOC01-appb-M000183
　ノード部1,…,Vは、t=t+1とする（ステップＳ７）。すなわち、ノード部1,…,Vは、tを１だけインクリメントする。
　ノード部1,…,Vは、t=Tであるか判定し（ステップＳ８）、t=Tであれば処理を終了する。t=Tでない場合には、ステップＳ２の処理に戻る。
　このように、それぞれ入力データが記憶されており、情報を互いに送受信しながら、教師データ及び上記入力データに基づいて主変数を用いた写像を機械学習する複数のノード部を含む機械学習システムにおいて、機械学習で用いられるコスト関数に代えて、コスト関数の上界となる代理凸関数を最小化するように機械学習が行われる。言い換えれば、複数のノード部が、情報を互いに送受信しながら、それぞれの入力データに基づいて共通するある１つの主変数を用いた写像を機械学習するステップを含む機械学習方法において、
　複数のノード部は、機械学習に本来対応する非凸関数のコスト関数に代えて、コスト関数の上界となる代理凸関数を最小化するように機械学習が行われる。
　また、代理凸関数は、コスト関数の主変数に関する一次勾配の式、又は、コスト関数の主変数に関する一次勾配の式及び二次勾配の式で表されている。
　コスト関数に代えてコスト関数の上界となる代理凸関数を用いることで、コスト関数が凸関数でない場合にも機械学習を行うことができる。また、ノード部iの間で主変数が送受信されないため、従来よりも秘密性が高い機械学習を行うことができる。
《変形例》
［変形例１］
　i=1,…,Vとして、ノード部iにDi個のデータが蓄積されているが、Diは時間によって変化してもよい。オンラインの最適化にも対応可能である。このとき、コスト関数は、以下のよう書ける
Figure JPOXMLDOC01-appb-M000184
［変形例２］
　ステップＳ５において、ノード部iは、双対補助変数yi|j,b (t+1)ではなく、双対変数λi|j,b (t+1)を送受信してもよい。
　この場合、ステップＳ６の処理は行われない。ステップＳ６以外のステップの処理は上記と同様に行われる。
［変形例３］
　以下では、伝送容量を圧縮するための工夫について説明する。
　最適化処理が収束するにつれて、更新差分が0に近づく。その性質を利用して、非可逆な圧縮処理をすれば、更に伝送容量を低く抑えられるはずである。
　情報圧縮の方法については様々考えられるが、更新差分を伝送しあうというアイデアを基軸に、(i) フロアリングベースの圧縮処理と、(ii) エントロピー符号化ベースの圧縮処理がある。
　まず、参照データがときどき更新されるとし、そのデータとの差分データを変数vとおく。ここで、vi|j,b (t+1)は、更新差分情報である。vi|j,b (t+1)は、収束するほど、0に近い数字に偏る傾向がある。vi|j,b (t+1)は、本来、ノード間で交換したい情報である。mi|j,b (export)は、既に得ている参照情報である。
Figure JPOXMLDOC01-appb-M000185
　そのvに圧縮処理Cを適用する。
Figure JPOXMLDOC01-appb-M000186
　(i) フロアリングベースの圧縮処理の場合には、vを構成するそれぞれの要素と閾値thrを比較し、閾値以下であれば0にするような処理をする。thrは、所定の0より大きな所定の数であり、例えば1×10-5等の非常に小さな数である。
Figure JPOXMLDOC01-appb-M000187
　(ii) エントロピー符号化ベースの圧縮処理の場合には、出現確率に応じてシンボルを割り当てるような処理をしてuを生成する。例えば、出現確率が値に対して、短いシンボルを割り当てることによりuを生成する。
　このとき、コスト関数を一般形式で記述した場合の合意形成アルゴリズムは以下のようになる。
　T回更新するとして、t∈{0,…,T-1}に対して、以下の(1)から(10)の処理を行う。
(1)双対変数更新
Figure JPOXMLDOC01-appb-M000188
(2)主変数更新
Figure JPOXMLDOC01-appb-M000189
(3)双対補助変数更新
Figure JPOXMLDOC01-appb-M000190
　mod (t, Tinterval)=0である場合には、以下の(4)から(6)の処理を行う。すなわち、たまに参照データを更新する。ここで、Tintervalは、所定の正の整数である。
 (4) 参照データの更新
Figure JPOXMLDOC01-appb-M000191
(5) ノード間で情報交換 (エッジごとに独立（非同期）でよい。)
Figure JPOXMLDOC01-appb-M000192
(6)交換して得た情報を使って双対補助変数更新
Figure JPOXMLDOC01-appb-M000193
　mod (t, Tinterval)=0でない場合には、以下の(7)から(10)の処理を行う。すなわち、ほとんどの時刻で更新差分を伝送しあう。
(7) 更新差分を計算
Figure JPOXMLDOC01-appb-M000194
(8) データを圧縮する
Figure JPOXMLDOC01-appb-M000195
(9) 圧縮されたデータをノード間で交換
Figure JPOXMLDOC01-appb-M000196
(10) 交換して得た情報を使って双対補助変数更新
Figure JPOXMLDOC01-appb-M000197
　このような伝送容量の削減を行うために、上記の実施形態において、ノード部iは、ステップＳ５からステップＳ６の処理に代えて、以下に説明するステップＳ９からステップＳ１６の処理を行えばよい。他の処理は、上記の実施形態と同様であるため、ここでは重複説明を省略する。図８に、伝送容量の削減を行った機械学習方法の例の流れ図を示す。
　ノード部1,…,Vは、mod (t, Tinterval)=0であるか判定する（ステップＳ９）。
　mod (t, Tinterval)=0である場合には、ノード部i（より詳細には、ノード部iの学習部１０）は、以下の式に基づいて参照データの更新を行う（ステップＳ１０）。すなわち、ノード部iは、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式に基づいて参照データの更新を行う（ステップＳ１０）。
Figure JPOXMLDOC01-appb-M000198
　ノード部i（より詳細には、ノード部iの送受信部１１）は、mi|j,b (export)を別のノード部jに対して送信する処理と、別のノード部jが送信したmj|i,b (import)を受信する処理と、の少なくとも何れかを行う、すなわち、以下の式に示すようにノード部の間で情報交換を行う（ステップＳ１１）。例えば、ノード部iは、ノード部iの学習部１０が得たmi|j,b (export)をノード部iの送受信部１１がノード部ｊに対して送信し、ノード部iの送受信部１１がノード部ｊから受信したmj|i,b (import)をノード部iの学習部１０に入力するように動作する。また、全てのノード部i,jではなく、一部のノード部iのみが一部のノード部jに対してのみに以下の式に示す処理を行ってもよい。言い換えれば、i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jにmi|j,b (export)を送信し、ノード部jが出力したmj|i,b (import)を受信する（ステップＳ１１）。
Figure JPOXMLDOC01-appb-M000199
　ノード部i（より詳細には、ノード部iの学習部１０）は、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式に示すように、交換して得た情報を使って双対補助変数zi|j,b (t+1)の更新を行う（ステップＳ１２）。
Figure JPOXMLDOC01-appb-M000200
　mod (t, Tinterval)=0でない場合には、ノード部i（より詳細には、ノード部iの学習部１０）は、以下の式に基づいて更新差分を計算する（ステップＳ１３）。すなわち、ノード部iは、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式により定義されるvi|j,b (t+1)の計算を行う。
Figure JPOXMLDOC01-appb-M000201
　ノード部i（より詳細には、ノード部iの学習部１０）は、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式に基づいて、データを圧縮することにより符号をui|j,b (t+1)生成する（ステップＳ１４）。このデータの圧縮は、非可逆であってもよい。ここで、Cは、フロアリングベースの圧縮処理、エントロピー符号化ベースの圧縮処理等の所定の圧縮処理を意味する。
Figure JPOXMLDOC01-appb-M000202
　ノード部i（より詳細には、ノード部iの送受信部１１）は、ui|j,b (t+1)を別のノード部jに対して送信する処理と、別のノード部jが送信したuj|i,b (t+1)を受信する処理と、の少なくとも何れかを行う、すなわち、以下の式に基づいて、圧縮されたデータをノード部間で交換する（ステップＳ１５）。例えば、ノード部iは、ノード部iの学習部１０が得たui|j,b (t+1)をノード部iの送受信部１１がノード部ｊに対して送信し、ノード部iの送受信部１１がノード部ｊから受信したuj|i,b (t+1)をノード部iの学習部１０に入力するように動作する。また、全てのノード部i,jではなく、一部のノード部iのみが一部のノード部jに対してのみに以下の式に示す処理を行ってもよい。言い換えれば、i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jに符号ui|j,b (t+1)を送信し、ノード部jが出力した符号uj|i,b (t+1)を受信する（ステップＳ１５）。
Figure JPOXMLDOC01-appb-M000203
　ノード部i（より詳細には、ノード部iの学習部１０）は、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式に基づいて、双対補助変数zi|j,b (t+1)の更新を行う（ステップＳ１６）。
Figure JPOXMLDOC01-appb-M000204
　なお、ステップ１２において、ノード部iは、以下に例示するD-R分割ベースの更新を行ってもよい。通常βは1/2が使われる。
Figure JPOXMLDOC01-appb-M000205
　また、ステップＳ１６において、ノード部iは、以下に例示するD-R分割ベースの更新を行ってもよい。通常βは1/2が使われる。
Figure JPOXMLDOC01-appb-M000206
　その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
《プログラム及び記録媒体》
　機械学習システムを、１つのコンピュータによって実現してもよい。この場合、機械学習システムの各部が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、機械学習システムの処理がコンピュータ上で実現される。
　この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
　また、各部の処理は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理の少なくとも一部をハードウェア的に実現することとしてもよい。
　以下、本発明の実施形態である第３実施形態及び第４実施形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
　各実施形態の説明に先立って、この明細書における表記方法について説明する。
　_（アンダースコア）は下付き添字を表す。例えば、xy_zはyzがxに対する上付き添字であり、xy_zはyzがxに対する下付き添字であることを表す。
＜技術的背景＞
　本願では、リゾルヴェント作用素やケーリー作用素を用いる代わりに、ブレグマンリゾルヴェント作用素やブレグマンケーリー作用素を用いる。つまり、ブレグマンリゾルヴェント作用素やブレグマンケーリー作用素を用いた単調作用素分割に基づき、変数更新則を構成する。以下、詳細に説明する。
《1：ブレグマンレゾルヴェント作用素とブレグマンケーリー作用素の定義》
　まず、ブレグマンダイバージェンスBについて説明する。ブレグマンダイバージェンスBは連続で微分可能な狭義凸関数Dを用いて以下のように定義される（以後、連続で微分可能な狭義凸関数のことを単に狭義凸関数という）。
Figure JPOXMLDOC01-appb-M000207
　関数Dとして任意の狭義凸関数を用いることができる。なお、ユークリッド距離もブレグマンダイバージェンスの一種である。また、ブレグマンダイバージェンスBが関数Dを用いて定義されることを明示するために、ブレグマンダイバージェンスBDと書くこともある。
　狭義凸関数Dは、ある種の連続性を有する関数である。具体的には、狭義凸関数Dは、強凸(SC: strong convex)とリプシッツ平滑(LS: Lipschitz smooth)という性質を有する。これらの性質は以下のように表現できる。
（性質1）2次のテーラー展開を用いると、関数Dに対して、点wの周りにおいて以下の近似式が成り立つ。
Figure JPOXMLDOC01-appb-M000208
　ここで、ヘシアン行列HD(w) (HD(w)∈Rm×m)は、正定値行列である。
Figure JPOXMLDOC01-appb-M000209
　なお、行列A,Bに対して、次式は行列B-Aが正定値であることを表す。
Figure JPOXMLDOC01-appb-M000210
（性質2)関数DのLS（上界）とSC（下界）は、任意のベクトルh∈Rmを用いて、以下のように表現できる。
Figure JPOXMLDOC01-appb-M000211
　ここで、ヘシアン行列KD, MD (KD∈Rm×m, MD∈Rm×m)は、正定値行列である。また、ヘシアン行列HD(w)との間に以下の関係が成り立つ。
Figure JPOXMLDOC01-appb-M000212
　次に、ブレグマンダイバージェンスを用いて、リゾルヴェント作用素、ケーリー作用素を一般化する。一般化したリゾルヴェント作用素、ケーリー作用素をそれぞれブレグマンリゾルヴェント作用素、ブレグマンケーリー作用素という。なお、ブレグマンリゾルヴェント作用素については参考非特許文献２に記載がある。
（参考非特許文献２：H. H. Bauschke, J. M. Borwein, and P. L. Combettes, “Bregman Monotone Optimization Algorithms”, SIAM Journal on Control and Optimization, Vol.42, Issue 2, pp.596-636, 2003.）
　ブレグマンリゾルヴェント作用素Rnとブレグマンケーリー作用素Cnは、次式で与えられる。
Figure JPOXMLDOC01-appb-M000213
　なお、以下のように関数Dを二乗したL2ノルムを用いて定義すると、ブレグマンダイバージェンスBはユークリッド距離に対応し、ブレグマンリゾルヴェント作用素Rnとブレグマンケーリー作用素Cnはそれぞれリゾルヴェント作用素Ωn、ケーリー作用素Ψnに対応する。具体的に説明する。関数Dの劣微分は以下のようになる。
Figure JPOXMLDOC01-appb-M000214
　関数Dの劣微分をブレグマンリゾルヴェント作用素Rnとブレグマンケーリー作用素Cnにそれぞれ代入すると、リゾルヴェント作用素Ωn、ケーリー作用素Ψnが得られる。
Figure JPOXMLDOC01-appb-M000215
《２：ブレグマンレゾルヴェント作用素とブレグマンケーリー作用素の収束率》
　ここでは、ブレグマンリゾルヴェント作用素、ブレグマンケーリー作用素の収束率に関して、2つのケースについて説明する。
［ケース1］：関数G1は、狭義凸関数である、すなわち、強凸(SC)かつリプシッツ平滑(LS)である。
　このとき、先述した通り、以下の性質が成り立つ。
（性質1）2次のテーラー展開を用いると、関数G1に対して、点wの周りにおいて以下の近似式が成り立つ。
Figure JPOXMLDOC01-appb-M000216
（性質2)関数G1のLS（上界）とSC（下界）は、任意のベクトルh∈Rmを用いて、以下のように表現できる。
Figure JPOXMLDOC01-appb-M000217
　ここで、ヘシアン行列HG_1(w), KG_1, MG_1は、以下の関係をもつ。
Figure JPOXMLDOC01-appb-M000218
　この2つの性質を用いて、以下の定理1と定理2が証明できる。
（定理1）関数G1がSCかつLSである場合、ブレグマンレゾルヴェント作用素R1は以下の収束率をもつ。
Figure JPOXMLDOC01-appb-M000219
　式(4-8)に含まれる係数σmax,1, σmin,1は次式で与えられる。ここで、Λmaxは最大固有値、 Λminは最小固有値を表す。
Figure JPOXMLDOC01-appb-M000220
　なお、狭義凸関数Dとして、以下の条件を満たすものを用いる。
Figure JPOXMLDOC01-appb-M000221
（定理2）関数G1がSCかつLSである場合、ブレグマンケーリー作用素C1は以下の収束率をもつ。
Figure JPOXMLDOC01-appb-M000222
　式(4-12)に含まれる係数η1は次式で与えられる。
Figure JPOXMLDOC01-appb-M000223
　係数σmax,1, σmin,1は式(4-9)、式(4-10)で与えられるものである。
［ケース2］：関数G1, G2は、いずれも狭義凸関数である、すなわち、いずれも強凸(SC)かつリプシッツ平滑(LS)である。
　関数G1については、式(4-5)～(4-7)で表される性質1及び性質2が成り立つ。同様に、関数G2については、式(4-14)～(4-16)で表される性質1及び性質2が成り立つ。
（性質1）2次のテーラー展開を用いると、関数G2に対して、点wの周りにおいて以下の近似式が成り立つ。
Figure JPOXMLDOC01-appb-M000224
（性質2)関数G2のLS（上界）とSC（下界）は、任意のベクトルh∈Rmを用いて、以下のように表現できる。
Figure JPOXMLDOC01-appb-M000225
　ここで、ヘシアン行列HG_2(w), KG_2, MG_2は、以下の関係をもつ。
Figure JPOXMLDOC01-appb-M000226
　関数G1について成り立つ定理1、定理2と同様の定理が、関数G2についても成り立つ。
（定理3）関数G2がSCかつLSである場合、ブレグマンレゾルヴェント作用素R2は以下の収束率をもつ。
Figure JPOXMLDOC01-appb-M000227
　式(4-17)に含まれる係数σmax,2, σmin,2は次式で与えられる。
Figure JPOXMLDOC01-appb-M000228
　なお、狭義凸関数Dとして、以下の条件を満たすものを用いる。
Figure JPOXMLDOC01-appb-M000229
（定理4）関数G2がSCかつLSである場合、ブレグマンケーリー作用素C2は以下の収束率をもつ。
Figure JPOXMLDOC01-appb-M000230
　式(4-20)に含まれる係数η2は次式で与えられる。
Figure JPOXMLDOC01-appb-M000231
　係数σmax,2, σmin,2は式(4-18)、式(4-19)で与えられるものである。
《３：一般化P-R型単調作用素分割、一般化D-R型単調作用素分割の変数更新則と収束率》
　ブレグマンリゾルヴェント作用素、ブレグマンケーリー作用素を用いて、式(1-2)を変形することにより、P-R型の単調作用素分割とD-R型の単調作用素分割を導出する。ここで説明するP-R型の単調作用素分割とD-R型の単調作用素分割は、ブレグマンダイバージェンスを用いたP-R型の単調作用素分割、D-R型の単調作用素分割の一般化に相当する。以下、それぞれ一般化P-R型単調作用素分割、一般化D-R型単調作用素分割ということにする。
［一般化P-R型単調作用素分割］
　式(1-2)を以下のように変形していく。
Figure JPOXMLDOC01-appb-M000232
　ここで、以下の関係を持つ、w(w∈Rm)の補助変数z(z∈Rm)を導入する。
Figure JPOXMLDOC01-appb-M000233
　変数zを用いてさらに変形していく。
Figure JPOXMLDOC01-appb-M000234
　これより、以下の通り、一般化P-R型単調作用素分割が得られる。
Figure JPOXMLDOC01-appb-M000235
　式(4-22)と式(3-1)から、式(3-1)のケーリー作用素をブレグマンケーリー作用素に置き換えたものが式(4-22)になっていることがわかる。
　一般化P-R型単調作用素分割の変数更新則は、w(∈Rm)の補助変数x, y, z(x∈Rm, y∈Rm, z∈Rm)を用いて式(4-22)を分解することにより得られる。
Figure JPOXMLDOC01-appb-M000236
　式(4-23)の演算を具体化する。つまり、以下のように変形する。
Figure JPOXMLDOC01-appb-M000237
　さらに積分形にすることにより、以下を得る。
Figure JPOXMLDOC01-appb-M000238
　式(4-25)の演算についても同様に具体化すると、以下が得られる。
Figure JPOXMLDOC01-appb-M000239
　次に、一般化P-R型単調作用素分割の収束率について説明する。ケース1、ケース2に場合分けして、収束率を導出する。まず、ケース1について説明する。ケース1については、ブレグマンケーリー作用素C1の非拡大性しか仮定できない（つまり、定理2は成り立つが、定理4は成り立たない）。したがって、式(4-23)～(4-26)より、ztの収束率は以下の不等式で表される。
Figure JPOXMLDOC01-appb-M000240
　式(4-29)より、ztとzの停留点z*との誤差は以下のように評価できる。
Figure JPOXMLDOC01-appb-M000241
　同様に、zt+1とzの停留点z*との誤差は以下のように評価できる。
Figure JPOXMLDOC01-appb-M000242
　式(4-30)と式(4-31)より、以下の関係を得る。
Figure JPOXMLDOC01-appb-M000243
　よって、t回の更新を経たときの誤差（収束率）は以下で表される。
Figure JPOXMLDOC01-appb-M000244
　次に、ケース2について説明する。ケース2については、ブレグマンケーリー作用素C1,C2の非拡大性を担保できる（つまり、定理2、定理4のいずれも成り立つ）。したがって、式(4-23)～(4-26)より、ztの収束率は以下の不等式で表される。
Figure JPOXMLDOC01-appb-M000245
　ケース1と同様にして、以下の関係を得る。
Figure JPOXMLDOC01-appb-M000246
　式(4-33)、式(4-36)からわかるように、ケース1、ケース2いずれの場合も、ηiを小さくすることができれば、収束率を高くすることができる。
［一般化D-R型単調作用素分割］
　一般化D-R型単調作用素分割は式(4-22)に平均化作用素を加えることで得られる。
Figure JPOXMLDOC01-appb-M000247
　式(4-37)と式(3-2)から、式(3-2)のケーリー作用素をブレグマンケーリー作用素に置き換えたものが式(4-37)になっていることがわかる。
　一般化D-R型単調作用素分割の変数更新則は、w(∈Rm)の補助変数x, y, z(x∈Rm, y∈Rm, z∈Rm)を用いて式(4-37)を分解することにより得られる。
Figure JPOXMLDOC01-appb-M000248
　次に、一般化D-R型単調作用素分割の収束率について説明する。ケース1、ケース2に場合分けして、収束率を導出する。まず、ケース1について説明する。ケース1については、ブレグマンケーリー作用素C1の非拡大性しか仮定できない（つまり、定理2は成り立つが、定理4は成り立たない）。したがって、式(4-38)～(4-41)より、ztの収束率は以下の不等式で表される。
Figure JPOXMLDOC01-appb-M000249
　よって、t回の更新を経たときの誤差（収束率）は以下で表される。
Figure JPOXMLDOC01-appb-M000250
　次に、ケース2について説明する。ケース2については、ブレグマンケーリー作用素C1,C2の非拡大性を担保できる（つまり、定理2、定理4のいずれも成り立つ）。したがって、式(4-38)～(4-41)より、ztの収束率は以下の不等式で表される。
Figure JPOXMLDOC01-appb-M000251
　式(4-43)及び式(4-45)からわかるように、ケース1、ケース2いずれの場合も、ηiを小さくすることができれば、αを1に近づけていくことにより、収束率を高くすることができる。なお、αを1に近づけていくということは、一般化D-R型単調作用素分割を一般化P-R型単調作用素分割に近づけていくことを意味する。
《４：高収束率を得るためのブレグマンダイバージェンス設計》
　一般化P-R型単調作用素分割や一般化D-R型単調作用素分割による変数更新則を用いることにより、最適解を求めることができる。ここでは、より高速に最適解を求めることができるような、ブレグマンダイバージェンスの設計（関数Dの設計）について説明する。具体的には、2つの設計方法について説明する。
　まず、これまでの議論で得られた結果についてまとめる。ケース1、ケース2いずれの場合も、式(4-13)で与えられるη1、式(4-21)で与えられるη2を0に近づけることにより、一般化P-R型単調作用素分割の変数更新則、一般化D-R型単調作用素分割の変数更新則いずれであっても高い収束率で最適解に収束する。
Figure JPOXMLDOC01-appb-M000252
　このηiを0に近づけることは、式(4-9)、式(4-10)、式(4-18)、式(4-19)で与えられる固有値σmax,i, σmin,iを1に近づけることで実現できる。最大固有値σmax,i、最小固有値σmin,iとも1に近づけることは、固有値分布が平滑になることに対応する。
Figure JPOXMLDOC01-appb-M000253
　固有値を1に近づけるためには、関数Dのヘシアン行列HDの逆行列が関数Giのヘシアン行列HG_iの逆行列となるように設計するとよい。
Figure JPOXMLDOC01-appb-M000254
　関数Giは式(4-5)、式(4-14)の近似式により表現されることから、関数Dを次式のような2次式で表現し、ヘシアン行列HDを適切に設計することで、式(4-47)を実現できる。
Figure JPOXMLDOC01-appb-M000255
　式(4-48)をブレグマンダイバージェンスの定義式である式(4-1)に代入すると以下を得る。
Figure JPOXMLDOC01-appb-M000256
［ニュートン法に従うブレグマンダイバージェンス設計］
　式(4-49)に従いブレグマンダイバージェンスを設計する際、式(4-47)を最も忠実に満たすようにするには、ヘシアン行列HDを式(4-50)に従うように設計するとよい。なお、この設計は、二次収束性の最適化法としてよく知られているニュートン法に通じるものである。式(4-50)の代わりに、BFGS法などのヘシアン行列の近似計算法を用いてもよい。
Figure JPOXMLDOC01-appb-M000257
　なお、実数ε>0は学習のステップサイズを決めるパラメータに相当し、ヘシアン行列HD (2GD)の固有値が0より大きく1以下に収まるように選ぶ必要がある。
　また、式(4-50)では、(case2)において相加平均を用いたが、相加平均の代わりに、相乗平均を用いてもよい。
Figure JPOXMLDOC01-appb-M000258
　式(4-50)（式(4-50’)）は、ケース1、ケース2に分けてヘシアン行列HDを設計していることを示している。ケース2の場合、関数G1、G2の双方に対して、式(4-47)を満たすようにすることが理想的であるが、実際、このことを担保するのは難しい。そこで、ケース2について、式(4-50)（式(4-50’)）のように設計することにした。この設計が好ましい理由は、ヘシアン行列に関して、以下の数学的性質が成り立つためである。具体的に説明する。まず、ヘシアン行列HDの逆行列を計算する。
Figure JPOXMLDOC01-appb-M000259
　ここで、式(4-47)式のようにHD -1とHG_iを掛け合わせると、以下のようになる。
Figure JPOXMLDOC01-appb-M000260
　これらの2つの式は、HG_1とHG_2が近いほど、式(4-47)を満たすようになることを示している。
［加速勾配法に従うブレグマンダイバージェンス設計］
　ニュートン法に従うブレグマンダイバージェンス設計を用いた場合、実際の変数更新則では、ヘシアン行列HDの逆行列を計算する必要があるが、この計算には非常に大きなコストがかかる。この計算コストの問題を克服するために、式(4-47)の再現性を多少犠牲にして、ヘシアン行列HDの逆行列の計算コストを下げることにする。このような設計として、加速勾配法に従うブレグマンダイバージェンス設計を説明する。この設計は簡単に説明すると、ヘシアン行列HDを対角行列に制約したうえで、式(4-47)をできるだけ満たすようにヘシアン行列HDを設計するものである。なお、この設計は、超一次収束として知られている加速勾配法に通じるものである。
　加速勾配法を実現するための方法は様々提案されている。例えば、モメンタム法、AdaGrad法、Adam法、RMSProp法などがある。ここでは、RMSProp法を用いた設計について説明する。
Figure JPOXMLDOC01-appb-M000261
　なお、実数ε>0は学習のステップサイズを決めるパラメータに相当し、ヘシアン行列HD (AGD)の固有値が0より大きく1以下に収まるように選ぶ必要がある。
　また、式(4-51)では、(case2)において相加平均を用いたが、相加平均の代わりに、相乗平均を用いてもよい。
Figure JPOXMLDOC01-appb-M000262
　また、LG_1とLG_2は基本的には対角行列となることを想定された行列であり、RMSProp法では以下のように設計する。
Figure JPOXMLDOC01-appb-M000263
　ただし、ヘシアン行列HDの逆行列の計算コストを多少犠牲にしてもよい場合、LG_1, LG_2は必ずしも対角行列である必要はない。非対角成分も用いる場合のRMSProp法では以下のように設計する。
Figure JPOXMLDOC01-appb-M000264
《５：エッジコンピューティングにおける合意形成問題への適用》
　ここでは、エッジコンピューティングにおける合意形成問題を例として、ブレグマンダイバージェンスを用いて一般化された単調作用素分割を用いた再帰的な変数更新則である変数更新アルゴリズムについて説明する。
　式(3-3)～式(3-6)に対応する再帰的な変数更新則は以下のようになる。
Figure JPOXMLDOC01-appb-M000265
　式(4-54)が一般化P-R型単調作用素分割に、式(4-55)が一般化D-R型単調作用素分割に対応する。
　なお、変数更新則の導出に際して、ブレグマンケーリー作用素C2が以下の式を満たすことを用いた。その証明については省略するが、非特許文献４に示された証明戦略をブレグマンケーリー作用素に適用すれば得られる結果である。
Figure JPOXMLDOC01-appb-M000266
　また、式(4-48)を用いる際の関数Dの劣微分とその逆作用素は以下のようになる。
Figure JPOXMLDOC01-appb-M000267
　ここで、ヘシアン行列HD(z)とその逆行列HD -1(z)は、いずれも以下のようなブロック対角化行列となる。
Figure JPOXMLDOC01-appb-M000268
　以下、式(4-52)～式(4-55)の再帰的な変数更新則をノードごとに非同期で変数を更新できるようにしたアルゴリズムについて説明する。式(4-52)には潜在変数pと双対変数wの更新が含まれており、潜在変数pと双対変数wの取り扱いに関して以下説明する2つの方法が考えられる。
［方法1］
　この方法は、従来法と同様、罰則項を用いてpの最適化を行った後、wの最適化を行う。
　まず、罰則項を用いて、pの最適化を行う。
Figure JPOXMLDOC01-appb-M000269
　次にwの最適化を行う。
Figure JPOXMLDOC01-appb-M000270
　式(4-61’)の結果を式(4-53)に代入すると、以下の双対変数λの更新則を得る。
Figure JPOXMLDOC01-appb-M000271
　この式は双対変数wを用いなくても双対変数λが得られることを示している。
　式(4-52)～(4-55)の変数更新則を具体的に表わすと以下のようになる。
Figure JPOXMLDOC01-appb-M000272
　なお、式(4-54)、式(4-55)については、式(4-63)、式(4-64)、式(4-65)に分けた。これは、ノードごとに非同期で変数を更新できるようにするためである。
　この更新則をノードごとに変数を更新できるようにすると、図１２に示すアルゴリズムが得られる。なお、このアルゴリズムにおけるヘシアン行列HDは、式(4-50)や式(4-51)を用いて設計するのが好ましい。
［方法2］
　この方法は、双対変数wの更新を行い、必要に応じて潜在変数pの更新を行う。
　式(4-52)を解くため、pをwの関数として表現して最適化する。2次のテーラー展開を用いて、関数F1を以下のように近似表現する。
Figure JPOXMLDOC01-appb-M000273
　これを関数F1 *に代入すると、以下のようにpをwの関数とした場合の最適値p(w)が得られる。
Figure JPOXMLDOC01-appb-M000274
　右辺の括弧内をpに関して微分し、それが0となる点（つまり、最適点）を探すと、以下のようになる。
Figure JPOXMLDOC01-appb-M000275
　これを式(4-52)に代入すると、wの更新式を得る。
Figure JPOXMLDOC01-appb-M000276
　右辺の括弧内をwに関して微分し、それが0となる点（つまり、最適点）を探すと、以下のようになる。
Figure JPOXMLDOC01-appb-M000277
　式(4-66)より、pはwの関数として表現されているので、pの更新式は以下のようになる。
Figure JPOXMLDOC01-appb-M000278
　式(4-53)に式(4-67)を代入することにより、以下の更新式を得る。
Figure JPOXMLDOC01-appb-M000279
　式(4-68)、式(4-69)、式(4-54)、式(4-55)より変数更新則を具体的に表わすと以下のようになる。
Figure JPOXMLDOC01-appb-M000280
　この更新則をノードごとに変数を更新できるようにすると、図１３に示すアルゴリズムが得られる。なお、このアルゴリズムにおけるヘシアン行列HDは、式(4-50)や式(4-51)を用いて設計するのが好ましい。
　図１２のアルゴリズムと図１３のアルゴリズムを比較すると、ノード間で交換される変数に違いがある。つまり、図１２のアルゴリズムでは、潜在変数と双対変数の変形を交換しているのに対して、図１３のアルゴリズムでは双対変数の変形のみ交換している。双対変数の変形のみ交換すればよくなったことにより、図１３のアルゴリズムの方が情報の秘匿化/暗号化という点において図１２のアルゴリズムよりも優れていると言える。
《６：実験及びその結果》
　以上説明した変数更新則の効果について確認するため、収束率に関する実験を行った。実験では、図１４のような2種類のグラフ構成をもった分散計算器（エッジコンピューティングシステム）を用いた。分散計算器の各ノードにはランダムに生成した異なるデータセットを配置し、潜在変数の収束率を計測した。
　コスト関数F1には、以下のものを用いた。
Figure JPOXMLDOC01-appb-M000281
　ここで、vi,uとsi,uはノードiにおける入力データと教師データの組、piはノードiにおける潜在変数である。
　また、潜在変数の誤差を測定する尺度には以下のものを用いた。
Figure JPOXMLDOC01-appb-M000282
　ここで、p*は潜在変数pの最適値、pi tはt回の更新で得られたノードiにおける潜在変数の値、m=p’Vである。
　図１５に実験結果を示す。B-MOS(GD)は従来の方法（図１１のアルゴリズム）、B-MOS(AGD)は加速勾配法(AGD)によりヘシアン行列を設計した場合の本願の方法（図１３のアルゴリズム）、B-MOS(2GD)はニュートン法によりヘシアン行列を設計した場合の本願の方法（図１３のアルゴリズム）を示す。なお、D-ADMMはB-MOS(GD)とは異なる別の従来の方法を示す。この図からわかるように、いずれのグラフ構造においても、本願の方法の方が、従来の方法と比較して収束率が高くなる。特に、ニュートン法に従ってヘシアン行列を設計した場合に、最も高い収束率が得られる。
《７：微分を用いた表現》
　《1：ブレグマンレゾルヴェント作用素とブレグマンケーリー作用素の定義》の冒頭部において、関数Dは微分可能な狭義凸関数であると仮定したことから、関数Dの劣微分を関数Dの微分としても《1：ブレグマンレゾルヴェント作用素とブレグマンケーリー作用素の定義》から《５：エッジコンピューティングにおける合意形成問題への適用》までの議論は成り立つ。具体的には、《1：ブレグマンレゾルヴェント作用素とブレグマンケーリー作用素の定義》から《５：エッジコンピューティングにおける合意形成問題への適用》までの説明における“関数Dの劣微分”との記載を“関数Dの微分”とした説明が成り立つ。以下、主たる式に関して劣微分を微分で置き換えた式を示す。
　関数Dの微分を用いた場合、ブレグマンダイバージェンスBは、以下のように定義される。
Figure JPOXMLDOC01-appb-M000283
　ここで、∇は関数を微分する演算を表す。
　また、狭義凸関数Dの（性質1）、（性質2）は、以下のように表現できる。
（性質1）2次のテーラー展開を用いると、関数Dに対して、点wの周りにおいて以下の近似式が成り立つ。
Figure JPOXMLDOC01-appb-M000284
（性質2)関数DのLS（上界）とSC（下界）は、任意のベクトルh∈Rmを用いて、以下のように表現できる。
Figure JPOXMLDOC01-appb-M000285
　ブレグマンリゾルヴェント作用素Rnとブレグマンケーリー作用素Cnは、次式で与えられる。
Figure JPOXMLDOC01-appb-M000286
　関数DをL2ノルムの二乗を用いて定義する場合、関数Dと関数Dの微分は以下のようになる。
Figure JPOXMLDOC01-appb-M000287
　この場合、ブレグマンリゾルヴェント作用素Rnとブレグマンケーリー作用素Cnは、劣微分を用いた場合と同様、リゾルヴェント作用素Ωn、ケーリー作用素Ψnとなる。
Figure JPOXMLDOC01-appb-M000288
　一般化P-R型単調作用素分割は、劣微分の場合と同様、次式のようになる。
Figure JPOXMLDOC01-appb-M000289
　そして、一般化P-R型単調作用素分割の変数更新則は、w(∈Rm)の補助変数x, y, z(x∈Rm, y∈Rm, z∈Rm)を用いて式(4-22)*を分解することにより得られる。
Figure JPOXMLDOC01-appb-M000290
　また、式(4-23)*を変形すると、次式が得られる。
Figure JPOXMLDOC01-appb-M000291
　式(4-25)*も同様に変形すると、次式が得られる。
Figure JPOXMLDOC01-appb-M000292
　一般化D-R型単調作用素分割も、劣微分の場合と同様、次式のようになる。
Figure JPOXMLDOC01-appb-M000293
　そして、一般化D-R型単調作用素分割の変数更新則は、w(∈Rm)の補助変数x, y, z(x∈Rm, y∈Rm, z∈Rm)を用いて式(4-37)*を分解することにより得られる。
Figure JPOXMLDOC01-appb-M000294
　劣微分の場合と同様、関数Dを式(4-48)の2次式で表現し、ブレグマンダイバージェンスの定義式である式(4-1)*に代入することにより、以下を得る。
Figure JPOXMLDOC01-appb-M000295
　ただし、式(4-48)における関数Dの更新は、毎ステップ行われるわけではない。具体的には、関数Dが強凸性であることを満たすため、以下の式で表される条件を満たす場合に限り、任意のタイミングで関数Dの微分∇Dの更新が行われる。したがって、当該条件が満たされない場合には、関数Dの微分∇Dの更新は行わない。
Figure JPOXMLDOC01-appb-M000296
　エッジコンピューティングにおける合意形成問題へ適用した場合における、式(3-3)～式(3-6)に対応する再帰的な変数更新則は以下のようになる。
Figure JPOXMLDOC01-appb-M000297
　なお、変数更新則の導出に際して、ブレグマンケーリー作用素C2が以下の式を満たすことを用いた。
Figure JPOXMLDOC01-appb-M000298
　また、式(4-48)を用いる際の関数Dの微分とその逆作用素は以下のようになる。
Figure JPOXMLDOC01-appb-M000299
《８：高次凸性を用いたブレグマンダイバージェンス設計》
　《４：高収束率を得るためのブレグマンダイバージェンス設計》で説明した２つのブレグマンダイバージェンス設計手法では、ブレグマンダイバージェンスの計量を決める関数Dを２次式に限定したときにどのように設計すればよいのかについて論じた。ここでは、２次以上の高次凸性を用いて、更なる高速収束を可能にする関数Dの設計について説明する。なお、以下では関数Dの微分∇Dの設計について説明するが、変数更新の際に使用するのは∇Dであるので、∇Dの設計に関して説明しても一般性を失うことはない。
　式(4-48)及び式(4-49)*において暗に仮定されていたことであるが、関数Dの設計により停留点を変更しないようにするために、関数Dは∇D(0)=0を満たすこと、かつ、関数Dは微分可能な狭義凸関数であることの２点に着目する。関数Giは微分可能であると仮定する。つまり、関数Giの微分∇Giは存在するものと仮定する。なお、関数Giそのものが微分可能でなくても、例えば平滑化などの処理により関数Giを微分可能な関数とすることができるため、関数Giは微分可能であると仮定しても問題ない。
　このとき、次式で表される条件のもと、∇Dを更新することにより、関数Giが２次以上の凸性を含む場合に高速収束が見込める。
Figure JPOXMLDOC01-appb-M000300
　ただし、∇Dの更新は、関数Dが強凸性であることを満たすため、以下の式で表される条件を満たす場合に限り、任意のタイミングで行われる。したがって、当該条件が満たされない場合には、∇Dの更新は行わない。
Figure JPOXMLDOC01-appb-M000301
　実用上、複数の高次（３次以上）の凸性の和として関数Giを表現する場合（例えば、高次のテーラー展開を用いて関数Giを狭義凸関数として表現する場合）には、解析的にwの最適解を得ることが難しいことが多い。このような場合には、和を用いる代わりに、単一の高次項のみを用いて関数Dを表現するのが一つの有用な実装法となる。この場合、次式により関数Dを表現すればよい。
Figure JPOXMLDOC01-appb-M000302
＜第３実施形態＞
　以下、図１６～図１７を参照して潜在変数学習装置１００を説明する。図１６は、潜在変数学習装置１００の構成を示すブロック図である。図１７は、潜在変数学習装置１００の動作を示すフローチャートである。図１６に示すように潜在変数学習装置１００は、モデル学習部１２０と、記録部１９０を含む。
　潜在変数学習装置１００は、学習データを用いて、機械学習の対象となるモデルの潜在変数w∈Rm（mは1以上の整数）を学習する。ここで、モデルとは、入力データを入力とし、出力データを出力とする関数のことであり、学習データとは、モデルの潜在変数の学習に用いる入力データ、または、モデルの潜在変数の学習に用いる入力データと出力データの組のことをいう。なお、入力データと出力データの組を学習データとする場合、出力データのことを教師データということもある。
　図１７に従い潜在変数学習装置１００の動作について説明する。
　Ｓ１２０において、モデル学習部１２０は、学習データを用いて、所定の手順により潜在変数wを学習する。以下、その手順について、具体的に説明する。
（手順１）
　ここでは、ブレグマンダイバージェンスを用いた学習手順について説明する。
　まず、モデル学習部１２０は、学習データを用いて、潜在変数wを学習する際に用いるセットアップデータを計算する。例えば、学習データを用いて計算される、潜在変数wを最適化するためのコスト関数G(w):Rm→R（ただし、G(w)=ΣiGi(w)、関数Gi(w)（Nを2以上の整数とし、iは1≦i≦Nを満たす整数とする（つまり、iはインデックスである））は閉真凸関数）がその一例である。
　次に、関数D（ただし、D:Rm→Rは狭義凸関数）を用いて定義されるブレグマンダイバージェンスBD(w1||w2)=D(w1)-D(w2)-<∂D(w2),w1- w2>（w1, w2∈Rm）を用いて、モデル学習部１２０は、コスト関数G(w)を最小化するwの停留点w*∈RmとのブレグマンダイバージェンスBD（BD(w||w*)またはBD(w*||w)）が0に近づくように、潜在変数wを学習する。なお、関数Dは、任意に設計可能な狭義凸関数である。また、停留点w*のことを不動点w*ともいう。
（手順２）
　ここでは、＜技術的背景＞で説明したように、単調作用素分割を用いて構成される潜在変数の更新規則を用いた学習手順について説明する。＜技術的背景＞では、N=2の場合について詳細に説明したが、単調作用素分割を用いて潜在変数の更新規則を構成できる任意のNについて、以下説明するような学習手順を構成することができる。例えば、N=3の場合についても、N=2の場合と同様、単調作用素分割の変形が可能であることが数学的に証明できるので、同様の学習手順を構成することができる。
　まず、モデル学習部１２０は、学習データを用いて、潜在変数wを学習する際に用いるセットアップデータを計算する。例えば、上述のコスト関数G(w)の他、関数Dと関数Giを用いて定義されるブレグマンリゾルヴェント作用素Ri(1≦i≦N)、ブレグマンリゾルヴェント作用素Riを用いて定義されるブレグマンケーリー作用素Ci(1≦i≦N)をセットアップデータとして計算する。
　次に、ブレグマンリゾルヴェント作用素Ri(1≦i≦N)とブレグマンケーリー作用素Ci(1≦i≦N)を用いて、潜在変数wの値を再帰的に計算する。具体的には、更新回数のカウントに用いる変数（以下、カウンタともいう）をtとし、モデル学習部１２０は、ブレグマンリゾルヴェント作用素Ri(1≦i≦N)とブレグマンケーリー作用素Ci(1≦i≦N)を用いて、潜在変数wのt+1回目の更新結果であるwt+1を再帰的に計算する。
　なお、カウンタtは、0以上の整数値をとることになる。
　N=2の場合における、一般化P-R型単調作用素分割及び一般化D-R型単調作用素分割を用いて構成される潜在変数の更新規則を用いた学習手順を実行するモデル学習部１２０について説明する。以下、図１８～図１９を参照してモデル学習部１２０について説明する。図１８は、モデル学習部１２０の構成を示すブロック図である。図１９は、モデル学習部１２０の動作を示すフローチャートである。図１８に示すようにモデル学習部１２０は、初期化部１２１と、潜在変数計算部１２２と、第１補助変数計算部１２３と、第２補助変数計算部１２４と、第３補助変数計算部１２５と、カウンタ更新部１２６と、終了条件判定部１２７を含む。
　図１９に従いモデル学習部１２０の動作について説明する。ここでは、潜在変数wの補助変数x, y, z∈Rmを用いる。
　Ｓ１２１において、初期化部１２１は、カウンタtを初期化する。具体的には、t=0とする。また、初期化部１２１は、セットアップデータを計算する。
　Ｓ１２２において、潜在変数計算部１２２は、式(5-1)により、補助変数zのt回目の更新結果であるztから潜在変数wのt+1回目の更新結果であるwt+1を計算する。
　Ｓ１２３において、第１補助変数計算部１２３は、式(5-2)により、Ｓ１２２で用いたztとＳ１２２で計算したwt+1から補助変数xのt+1回目の更新結果であるxt+1を計算する。
　Ｓ１２４において、第２補助変数計算部１２４は、式(5-3)により、Ｓ１２３で計算したxt+1から補助変数yのt+1回目の更新結果であるyt+1を計算する。
　Ｓ１２５において、第３補助変数計算部１２５は、補助変数zのt+1回目の更新結果であるzt+1を計算する。具体的に説明する。一般化P-R型単調作用素分割を用いる場合、第３補助変数計算部１２５は、式(5-4)により、Ｓ１２３で計算したxt+1とＳ１２４で計算したyt+1から補助変数zのt+1回目の更新結果であるzt+1を計算する。また、一般化D-R型単調作用素分割を用いる場合、第３補助変数計算部１２５は、式(5-5)により、Ｓ１２２で用いたztとＳ１２３で計算したxt+1とＳ１２４で計算したyt+1から補助変数zのt+1回目の更新結果であるzt+1を計算する（ただし、αは0<α<1を満たす実数である）。
　Ｓ１２６において、カウンタ更新部１２６は、カウンタtを1だけインクリメントする。具体的には、t←t+1とする。
　Ｓ１２７において、終了条件判定部１２７は、カウンタtが所定の更新回数τ（τは1以上の整数とする）に達した場合（つまり、t=τとなり、終了条件が満たされた場合）は、そのときの潜在変数wの値wτを出力して、処理を終了する。それ以外の場合、Ｓ１２２の処理に戻る。つまり、モデル学習部１２０は、Ｓ１２２～Ｓ１２５の計算を繰り返す。なお、Ｓ１２５で計算したzt+1は、次の繰り返し計算におけるＳ１２２とＳ１２３で用いられる。
Figure JPOXMLDOC01-appb-M000303
《高収束率を実現するための関数Dの条件》
　コスト関数G(w)を最小化するwの停留点w*への収束率を高くするためには、関数Dを以下の条件を満たす関数にすればよい。
（条件）関数Dは、そのヘシアン行列が関数Gi(w)のヘシアン行列の逆行列に近くなるような関数である。
　なお、上記条件は、“関数Dは、そのヘシアン行列の逆行列と関数Gi(w)のヘシアン行列の積が単位行列に近くなるような関数である”ということもできる。
　N=2の場合、＜技術的背景＞で説明したように、ニュートン法や加速勾配法に従って、関数Dのヘシアン行列を以下のように計算すればよい。
［ケース1］：関数G1は、狭義凸関数である、すなわち、強凸(SC)かつリプシッツ平滑(LS)である場合。
Figure JPOXMLDOC01-appb-M000304
（ただし、ε>0は実数）
　なお、実数εは、ヘシアン行列HDの固有値が0より大きく1以下に収まるように選ばれる。
［ケース2］：関数G1, G2は、いずれも狭義凸関数である、すなわち、いずれも強凸(SC)かつリプシッツ平滑(LS)である場合。
Figure JPOXMLDOC01-appb-M000305
（ただし、ε>0は実数）
　なお、実数εは、ヘシアン行列HDの固有値が0より大きく1以下に収まるように選ばれる。
　式(5-6)及び式(5-8)がニュートン法に従った場合であり、式(5-7)及び式(5-9)が加速勾配法に従った場合である。なお、行列LG_1, LG_2は式(5-10)及び式(5-11)により与えられる行列である。
Figure JPOXMLDOC01-appb-M000306
　または、行列LG_1, LG_2は式(5-12)及び式(5-13)により与えられる行列である。
Figure JPOXMLDOC01-appb-M000307
　式(5-10)及び式(5-12)の行列LG_1は、関数G1(w)の勾配を用いて計算される行列である。また、式(5-11)及び式(5-13)の行列LG_2は、関数G2(w)の勾配を用いて計算される行列である。
　なお、［ケース2］における式(5-8)及び式(5-9)の代わりに、次式のような相乗平均を用いてもよい。
Figure JPOXMLDOC01-appb-M000308
　なお、先のケース1やケース2の説明では、関数G1(w)や関数G2(w)は狭義凸関数であるとしたが、必ずしも数学的に厳密に狭義凸関数である必要はない。つまり、関数G1(w)や関数G2(w)を狭義凸関数であるとみなして扱ってよい場合についても、式(5-6)～式(5-9)により関数Dのヘシアン行列を計算することができる。より詳しく言えば、次のようになる。
［ケース1］：関数G1が、狭義凸関数である（強凸(SC)かつリプシッツ平滑(LS)である）、または、狭義凸関数である（強凸(SC)かつリプシッツ平滑(LS)である）と仮定できる場合。
　この場合は、式(5-6)や式(5-7)により、関数Dのヘシアン行列を計算することができる。
［ケース2］：関数G1, G2のそれぞれが、狭義凸関数である（強凸(SC)かつリプシッツ平滑(LS)である）、または、狭義凸関数である（強凸(SC)かつリプシッツ平滑(LS)である）と仮定できる場合。
　この場合は、式(5-8)や式(5-9)により、関数Dのヘシアン行列を計算することができる。
　上記第３実施形態の説明では、劣微分を用いて説明したが、＜技術的背景＞で説明したように劣微分の代わりに微分を用いてもよい。この場合、式(5-1)～式(5-5)の代わりに次式を用いればよい。
Figure JPOXMLDOC01-appb-M000309
　また、微分を用いる場合は、次式で表される条件のもと、∇Dを更新するようにしてもよい。
Figure JPOXMLDOC01-appb-M000310
　ただし、∇Dの更新は、以下の式で表される条件を満たす場合に限り、任意のタイミングで行うものとする。
Figure JPOXMLDOC01-appb-M000311
　本実施形態の発明によれば、機械学習の対象となるモデルの潜在変数を高速に学習することができる。本実施形態の発明によれば、ブレグマンリゾルヴェント作用素やブレグマンケーリー作用素を用いた単調作用素分割に基づき、変数更新則を構成することにより、停留点（最適解）への収束が高速になるように、潜在変数を更新することができる。また、ブレグマンダイバージェンスの定義に用いる凸関数を適切に構成することにより、停留点への収束が高速になるような、ブレグマンリゾルヴェント作用素やブレグマンケーリー作用素を用いた単調作用素分割に基づく変数更新則を構成することができる。
＜第４実施形態＞
　ここでは、＜技術的背景＞の《５：エッジコンピューティングにおける合意形成問題への適用》で説明した2つの変数更新アルゴリズム（図１２及び図１３のアルゴリズム）に対応する実施形態について説明する。
　以下、図２０を参照して潜在変数学習システム２０を説明する。図２０は、潜在変数学習システム２０の構成を示すブロック図である。図２０に示すように潜在変数学習システム２０は、V個（Vは1以上の整数）の潜在変数学習装置２００1, …, ２００Vを含む。潜在変数学習装置２００i(i∈v={1,…,V}）は、先のエッジコンピューティングにおける合意形成問題に関する説明におけるノードに対応するものである。
　また、各潜在変数学習装置２００iはネットワーク９００に接続しており、必要に応じて潜在変数学習装置２００j(j≠i)と通信する。ネットワーク９００には、例えば、インターネットを用いることができる。
　以下、図２１を参照して潜在変数学習装置２００を説明する。図２１は、潜在変数学習装置２００の構成を示すブロック図である。図２１に示すように潜在変数学習装置２００は、モデル学習部２２０と、通信部２８０と、記録部２９０を含む。
　潜在変数学習装置２００iは、学習データを用いて、機械学習の対象となるモデルの潜在変数pi∈Rp’（p’は1以上の整数）を学習する。学習データは、すべての潜在変数学習装置２００iに共通であってもよいし、潜在変数学習装置２００iごとに異なるものであってもよい。
　次に、図２２～図２３を参照してモデル学習部２２０を説明する。図２２は、モデル学習部２２０の構成を示すブロック図である。図２３は、モデル学習部２２０の動作を示すフローチャートである。図２２に示すようにモデル学習部２２０は、初期化部２２１と、潜在変数計算部２２２と、第１双対変数計算部２２３と、同期用変数更新部２２４と、第２双対変数計算部２２５と、カウンタ更新部２２６と、終了条件判定部２２７を含む。
　図２３に従いモデル学習部２２０の動作について説明する。具体的な説明に入る前に、いくつか記号について説明する。これらの記号は、これまでの議論で用いてきたものであり、以下の説明は、そのまとめに相当するものである。
　v={1,…,V}は、潜在変数学習装置２００群のインデックスの集合を表す。また、N(i)は、潜在変数学習装置２００iと通信をする潜在変数学習装置２００群のインデックスの集合を表す。
　潜在変数pi, pj（ただし、j∈N(i)）に対して、λi|j∈Rp’を潜在変数学習装置２００iに帰属する双対変数、λj|i∈Rp’を潜在変数学習装置２００jに帰属する双対変数とする。また、同様に、潜在変数pi, pj（ただし、j∈N(i)）に対して、zi|j∈Rp’を潜在変数学習装置２００iに帰属する双対変数、zj|i∈Rp’を潜在変数学習装置２００jに帰属する双対変数とする。
　関数F1,i(pi):Rp’→Rを、学習データを用いて計算される、潜在変数piを最適化するためのコスト関数（ただし、F1,i(pi)は閉真凸関数）とする。
　Ai|j∈Rp’×p’を次式により与えられるp’×p’の実数行列とする。
Figure JPOXMLDOC01-appb-M000312
　関数Di|j:Rp’→R（ただし、j∈N(i)）を潜在変数学習装置２００iに帰属する狭義凸関数とする。
　なお、ξi|j, ζiを潜在変数学習装置２００j（ただし、j∈N(i)）から送信されたデータを格納するための潜在変数学習装置２００iの変数とする。以下、ξi|j, ζiのことを同期用変数ともいう。また、tを変数の更新回数をカウントするための変数（以下、カウンタともいう）、τ（τは1以上の整数）を所定の更新回数とする。このτは、後述するＳ２２２～Ｓ２２５の繰り返し計算の回数の上限を表す。
　以降の説明では、Si(i∈v={1,…,V}）は、V個の潜在変数学習装置２００1, …, ２００Vを示すものとする。したがって、潜在変数学習システム２０は、潜在変数学習装置Si(i∈v）を含み、潜在変数学習装置Si(i∈v）は、学習データを用いて、所定の手順により潜在変数piを学習する。以下、図２３を参照してその手順について説明する。
　Ｓ２２１において、初期化部２２１は、カウンタtを初期化する。具体的には、t=0とする。また、初期化部２２１は、セットアップデータを計算する。例えば、コスト関数F1,i(pi)がその一例である。
　Ｓ２２２において、潜在変数計算部２２２は、次式により、双対変数zi|jのt回目の更新結果であるzi|j tと変数ζiのt回目の更新結果であるζi tから潜在変数piのt+1回目の更新結果であるpi t+1を計算する。
Figure JPOXMLDOC01-appb-M000313
　ただし、zi|j 0及びζi 0には適当な初期値が設定されているものとする。また、γ（γ>0）は所定の実数とする。
　Ｓ２２３において、第１双対変数計算部２２３は、j∈N(i)について、次式により、Ｓ２２２で用いたzi|j tとＳ２２２で計算したpi t+1から双対変数λi|j（j∈N(i)）のt+1回目の更新結果であるλi|j t+1を計算する。
Figure JPOXMLDOC01-appb-M000314
　ここで、HD_i|jは関数Di|jのヘシアン行列を表す。つまり、HD_i|j -1はその逆行列である。
　Ｓ２２４において、同期用変数更新部２２４は、通信部２８０を用いて、次式により、潜在変数学習装置Sj(j∈N(i)）の学習により得られる値を変数ξi|j, ζi（j∈N(i)）のt+1回目の更新結果であるξi|j t+1, ζi t+1として受信し、変数ξi|j, ζiを更新する。
Figure JPOXMLDOC01-appb-M000315
　Ｓ２２５において、第２双対変数計算部２２５は、j∈N(i)について、次式により、双対変数zi|j（j∈N(i)）のt+1回目の更新結果であるzi|j t+1を計算する。
Figure JPOXMLDOC01-appb-M000316
　ここで、αは0<α<1を満たす実数である。
　なお、式(6-1)は一般化P-R型単調作用素分割を用いる場合、式(6-2)は一般化D-R型単調作用素分割を用いる場合に対応する。
　Ｓ２２６において、カウンタ更新部２２６は、カウンタtを1だけインクリメントする。具体的には、t←t+1とする。
　Ｓ２２７において、終了条件判定部２２７は、カウンタtが所定の更新回数τに達した場合（つまり、t=τとなり、終了条件が満たされた場合）は、そのときの潜在変数piの値pi τを出力して、処理を終了する。それ以外の場合、Ｓ２２２の処理に戻る。つまり、モデル学習部２２０は、Ｓ２２２～Ｓ２２５の計算を繰り返す。なお、Ｓ２２５で計算したzi|j t+1は、次の繰り返し計算におけるＳ２２２とＳ２２３で用いられる。
　なお、ヘシアン行列HD_i|jは、式(5-6)～式(5-9)を用いて設計するのが好ましい。
（変形例１）
　上述の手順は、図１２のアルゴリズムに対応するものである。ここでは、図１３のアルゴリズムに対応する手順について説明する。当該手順では、潜在変数を交換する必要がないため、変数ζiを用いない。
　潜在変数学習装置２００は、図２１に示すように、モデル学習部２２０の代わりに、モデル学習部２３０を含む。以下、図２４～図２５を参照してモデル学習部２３０を説明する。図２４は、モデル学習部２３０の構成を示すブロック図である。図２５は、モデル学習部２３０の動作を示すフローチャートである。図２４に示すようにモデル学習部２３０は、初期化部２３１と、第１双対変数計算部２３２と、潜在変数計算部２３３と、同期用変数更新部２３４と、第２双対変数計算部２３５と、カウンタ更新部２３６と、終了条件判定部２３７を含む。
　図２５に従いモデル学習部２３０の動作について説明する。
　Ｓ２３１において、初期化部２３１は、カウンタtを初期化する。具体的には、t=0とする。また、初期化部２３１は、セットアップデータを計算する。
　Ｓ２３２において、第１双対変数計算部２３２は、j∈N(i)について、次式により、双対変数zi|jのt回目の更新結果であるzi|j tと潜在変数piのt回目の更新結果であるpi tから双対変数λi|j（j∈N(i)）のt+1回目の更新結果であるλi|j t+1を計算する。
Figure JPOXMLDOC01-appb-M000317
　ただし、zi|j 0及びpi 0には適当な初期値が設定されているものとする。また、HD_i|jは関数Di|jのヘシアン行列、HF_1,iは関数F1,iのヘシアン行列を表す。つまり、HD_i|j -1及びHF_1,i -1はそれらの逆行列である。∂F1,iは関数F1,iの劣微分を表す。
　Ｓ２３３において、潜在変数計算部２３３は、次式により、潜在変数piのt+1回目の更新結果であるpi t+1を計算する。
Figure JPOXMLDOC01-appb-M000318
　ここで、wi|j tは双対変数wi|jのt回目の更新結果を表す。
　Ｓ２３４において、同期用変数更新部２３４は、通信部２８０を用いて、次式により、潜在変数学習装置Sj(j∈N(i)）の学習により得られる値を変数ξi|j（j∈N(i)）のt+1回目の更新結果であるξi|j t+1として受信し、変数ξi|jを更新する。
Figure JPOXMLDOC01-appb-M000319
　Ｓ２２５において、第２双対変数計算部２２５は、j∈N(i)について、次式により、双対変数zi|j（j∈N(i)）のt+1回目の更新結果であるzi|j t+1を計算する。
Figure JPOXMLDOC01-appb-M000320
　ここで、αは0<α<1を満たす実数である。
　なお、式(6-1)は一般化P-R型単調作用素分割を用いる場合、式(6-2)は一般化D-R型単調作用素分割を用いる場合に対応する。
　Ｓ２３６において、カウンタ更新部２３６は、カウンタtを1だけインクリメントする。具体的には、t←t+1とする。
　Ｓ２３７において、終了条件判定部２３７は、カウンタtが所定の更新回数τに達した場合（つまり、t=τとなり、終了条件が満たされた場合）は、そのときの潜在変数piの値pi τを出力して、処理を終了する。それ以外の場合、Ｓ２３２の処理に戻る。つまり、モデル学習部２３０は、Ｓ２３２～Ｓ２３５の計算を繰り返す。なお、Ｓ２３５で計算したzi|j t+1は、次の繰り返し計算におけるＳ２３２とＳ２３３で用いられる。
　なお、ヘシアン行列HD_i|jは、式(5-6)～式(5-9)を用いて設計するのが好ましい。
　本実施形態の発明によれば、機械学習の対象となるモデルの潜在変数を高速に学習することができる。本実施形態の発明によれば、ブレグマンリゾルヴェント作用素やブレグマンケーリー作用素を用いた単調作用素分割に基づき、変数更新則を構成することにより、停留点（最適解）への収束が高速になるように、潜在変数を更新することができる。また、ブレグマンダイバージェンスの定義に用いる凸関数を適切に構成することにより、停留点への収束が高速になるような、ブレグマンリゾルヴェント作用素やブレグマンケーリー作用素を用いた単調作用素分割に基づく変数更新則を構成することができる。
＜補記＞
　本発明の装置は、例えば単一のハードウェアエンティティとして、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（Central Processing Unit、キャッシュメモリやレジスタなどを備えていてもよい）、メモリであるＲＡＭやＲＯＭ、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、ＣＤ－ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けることとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
　ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくこととしてもよい）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。
　ハードウェアエンティティでは、外部記憶装置（あるいはＲＯＭなど）に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にＣＰＵで解釈実行・処理される。その結果、ＣＰＵが所定の機能（上記、…部、…手段などと表した各構成要件）を実現する。
　本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
　既述のように、上記実施形態において説明したハードウェアエンティティ（本発明の装置）における処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
　この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ－ＲＡＭ（Random Access Memory）、ＣＤ－ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ－Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ－ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
　また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ－ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
　このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
　また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
　上述の本発明の実施形態の記載は、例証と記載の目的で提示されたものである。網羅的であるという意思はなく、開示された厳密な形式に発明を限定する意思もない。変形やバリエーションは上述の教示から可能である。実施形態は、本発明の原理の最も良い例証を提供するために、そして、この分野の当業者が、熟考された実際の使用に適するように本発明を色々な実施形態で、また、色々な変形を付加して利用できるようにするために、選ばれて表現されたものである。すべてのそのような変形やバリエーションは、公正に合法的に公平に与えられる幅にしたがって解釈された添付の請求項によって定められた本発明のスコープ内である。

Claims (12)

  1. 　情報を互いに送受信しながら、それぞれの入力データに基づいて共通するある１つの主変数を用いた写像を機械学習する複数のノード部を含む機械学習システムにおいて、
    　上記機械学習に本来対応する非凸関数のコスト関数に代えて、上記コスト関数の上界となる代理凸関数を最小化するように上記機械学習が行われ、
    　上記代理凸関数は、上記コスト関数の主変数に関する一次勾配の式、又は、上記コスト関数の主変数に関する一次勾配の式及び二次勾配の式で表されている、
    　機械学習システム。
  2. 　請求項１に記載の機械学習システムにおいて、
    　Vを２以上の所定の正の整数とし、上記複数のノード部はノード部1,…,Vであるとし、~V={1,…,V}とし、Bを所定の正の整数とし、b=1,…,Bとし、~B={1,…,B}とし、ノード部iにつながっているノード部の集合を~N(i)とし、ノード部iにおけるノード部jに対する双対変数λi|jを構成するb個目のベクトルをλi|j,bとし、t+1回目の更新後の双対変数λi|j,bをλi|j,b (t+1)とし、双対変数λi|jの双対補助変数zi|jを構成するb個目のベクトルをzi|j,bとし、t+1回目の更新後の双対補助変数zi|j,bをzi|j,b (t+1)とし、双対変数λi|jの双対補助変数yi|jを構成するb個目のベクトルをyi|j,bとし、t+1回目の更新後の双対補助変数yi|j,bをyi|j,b (t+1)とし、ノード部iの主変数wiのb個目の要素をwi,bとし、t回目の更新後の双対補助変数wi,bをwi,b (t)とし、上記機械学習で用いられるノード部iに対応するコスト関数をfiとし、コスト関数fiのwi,b (t)に関する一次勾配を∇fi(wi,b (t))とし、Ai|jは以下の式により定義されるとし、Iを単位行列とし、Oを零行列とし、σ1を所定の正の数とし、ηを正の数とし、Tを正の整数として、
    Figure JPOXMLDOC01-appb-M000001
    　t=0,…,T-1に対して、(a) ノード部iが、以下の式に基づいて双対変数の更新を行う処理と、
    Figure JPOXMLDOC01-appb-M000002
    (b) ノード部iが、以下の式に基づいて、主変数の更新を行う処理と、
    Figure JPOXMLDOC01-appb-M000003
    が行われ、t=0,…,T-1の一部又は全部に対しては、上記(a)及び上記(b)の処理に加えて、
    (c) i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jに双対補助変数yi|j,b (t+1)を送信する処理と、 
    (d) i∈~V, j∈~N(i), b∈~Bとして、双対補助変数yj|i,b (t+1)を受信したノード部iが、zi|j,b (t+1)=yj|i,b (t+1)とする処理と、
    が行われる、
    　機械学習システム。
  3. 　複数のノード部が、情報を互いに送受信しながら、それぞれの入力データに基づいて共通するある１つの主変数を用いた写像を機械学習するステップを含む機械学習方法において、
    　上記複数のノード部は、上記機械学習に本来対応する非凸関数のコスト関数に代えて、上記コスト関数の上界となる代理凸関数を最小化するように上記機械学習を行い、
    　上記代理凸関数は、上記コスト関数の主変数に関する一次勾配の式、又は、上記コスト関数の主変数に関する一次勾配の式及び二次勾配の式で表されている、
    　機械学習方法。
  4. 　請求項３に記載の機械学習方法において、
    　Vを２以上の所定の正の整数とし、上記複数のノード部はノード部1,…,Vであるとし、~V={1,…,V}とし、Bを所定の正の整数とし、b=1,…,Bとし、~B={1,…,B}とし、ノード部iにつながっているノード部の集合を~N(i)とし、ノード部iにおけるノード部jに対する双対変数λi|jを構成するb個目のベクトルをλi|j,bとし、t+1回目の更新後の双対変数λi|j,bをλi|j,b (t+1)とし、双対変数λi|jの双対補助変数zi|jを構成するb個目のベクトルをzi|j,bとし、t+1回目の更新後の双対補助変数zi|j,bをzi|j,b (t+1)とし、双対変数λi|jの双対補助変数yi|jを構成するb個目のベクトルをyi|j,bとし、t+1回目の更新後の双対補助変数yi|j,bをyi|j,b (t+1)とし、ノード部iの主変数wiのb個目の要素をwi,bとし、t回目の更新後の双対補助変数wi,bをwi,b (t)とし、上記機械学習で用いられるノード部iに対応するコスト関数をfiとし、コスト関数fiのwi,b (t)に関する一次勾配を∇fi(wi,b (t))とし、Ai|jは以下の式により定義されるとし、Iを単位行列とし、Oを零行列とし、σ1を所定の正の数とし、ηを正の数とし、Tを正の整数として、
    Figure JPOXMLDOC01-appb-M000004
    　t=0,…,T-1に対して、(a) ノード部iが、以下の式に基づいて双対変数の更新を行うステップと、
    Figure JPOXMLDOC01-appb-M000005
    (b) ノード部iが、以下の式に基づいて、主変数の更新を行うステップと、
    Figure JPOXMLDOC01-appb-M000006
    が行われ、t=0,…,T-1の一部又は全部に対しては、上記(a)及び上記(b)のステップに加えて、
    (c) i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jに双対補助変数yi|j,b (t+1)を送信するステップと、 
    (d) i∈~V, j∈~N(i), b∈~Bとして、双対補助変数yj|i,b (t+1)を受信したノード部iが、zi|j,b (t+1)=yj|i,b (t+1)とするステップと、
    が行われる、
    　機械学習方法。
  5. 　請求項１または２に記載の機械学習システムの各部として、コンピュータを機能させるためのプログラム。
  6. 共通するある１つの主変数についての学習結果を得るための機械学習をする複数のノード部を含む機械学習システムにおいて、
    　上記複数のノード部のそれぞれは、
    該ノード部に入力された入力データを用いて、該ノード部の双対変数を、双対変数を最適化すれば、主変数も最適化されるように、更新する学習部と、
    上記主変数ではなく、該ノード部の学習部が得た上記双対変数又は上記双対変数の補助変数である双対補助変数を該ノード部以外のノード部に対して送信する送信処理と、
    上記主変数ではなく、該ノード部以外のノード部が学習部で得た上記双対変数又は上記双対変数の補助変数である双対補助変数を受信する受信処理と、を行う送受信部と、
    を含み、
    　上記学習部は、
    上記送受信部が上記受信処理をした場合には、受信した上記双対変数又は上記双対変数の補助変数である双対補助変数を用いて上記双対変数を更新する
    　機械学習システム。
  7. 　請求項６に記載の機械学習システムにおいて、
    　上記学習部における上記双対変数の更新処理は、
    　上記主変数の最適化の更新式が、上記主変数の更新前の項を含まず上記双対変数を含む式で表されることにより、行われる、
    　機械学習システム。
  8. 　請求項６に記載の機械学習システムにおいて、
    　Vを２以上の所定の正の整数とし、上記複数のノード部はノード部1,…,Vであるとし、~V={1,…,V}とし、Bを所定の正の整数とし、b=1,…,Bとし、~B={1,…,B}とし、ノード部iにつながっているノード部の集合を~N(i)とし、ノード部iにおけるノード部jに対する双対変数λi|jを構成するb個目のベクトルをλi|j,bとし、t+1回目の更新後の双対変数λi|j,bをλi|j,b (t+1)とし、上記機械学習で用いられるノード部iに対応するコスト関数をfiとし、双対変数λi|jの双対補助変数zi|jを構成するb個目のベクトルをzi|j,bとし、t+1回目の更新後の双対補助変数zi|j,bをzi|j,b (t+1)とし、双対変数λi|jの双対補助変数yi|jを構成するb個目のベクトルをyi|j,bとし、t+1回目の更新後の双対補助変数yi|j,bをyi|j,b (t+1)とし、ノード部iの主変数wi,bのb個目の要素をwiとし、wi,bの最適解のb個目の要素をwi,b *とし、Ai|jは以下の式により定義されるとし、Iを単位行列とし、Oを零行列とし、σ1を所定の正の数とし、Tを正の整数として、
    Figure JPOXMLDOC01-appb-M000007
    　t=0,…,T-1に対して、(a) ノード部iが、以下の式に基づいて双対変数の更新を行う処理と、
    Figure JPOXMLDOC01-appb-M000008
    (b) ノード部iが、以下の式に基づいて、双対補助変数の更新を行う処理と、
    Figure JPOXMLDOC01-appb-M000009
    が行われ、t=0,…,T-1の一部又は全部に対しては、上記(a)及び上記(b)の処理に加えて、
    (c) i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jに双対補助変数yi|j,b (t+1)を送信する処理と、 
    (d) i∈~V, j∈~N(i), b∈~Bとして、双対補助変数yj|i,b (t+1)を受信したノード部iが、zi|j,b (t+1)=yj|i,b (t+1)とする処理と、
    が行われる、
    　機械学習システム。
  9. 　複数のノード部が、共通するある１つの主変数についての学習結果を得るための機械学習をする機械学習方法において、
    上記機械学習方法は、
    上記複数のノード部のそれぞれの学習部が、該ノード部に入力された入力データを用いて、該ノード部の双対変数を、双対変数を最適化すれば、主変数も最適化されるように、更新する学習ステップと、
    該ノード部の送受信部が、上記主変数ではなく、該ノード部の学習部が得た上記双対変数又は上記双対変数の補助変数である双対補助変数を該ノード部以外のノード部に対して送信する送信処理と、
    上記主変数ではなく、該ノード部以外のノード部が学習部で得た上記双対変数又は上記双対変数の補助変数である双対補助変数を受信する受信処理と、を行う送受信ステップと、
    を含み、
    　上記学習ステップは、
    上記送受信ステップが上記受信処理をした場合には、受信した上記双対変数又は上記双対変数の補助変数である双対補助変数を用いて上記双対変数を更新する
    　機械学習方法。
  10. 　請求項９に記載の機械学習方法において、
    　上記学習ステップにおける上記双対変数の更新処理は、
    　上記主変数の最適化の更新式が、上記主変数の更新前の項を含まず上記双対変数を含む式で表されることにより、行われる、
    　機械学習方法。
  11. 　請求項９に記載の機械学習方法において、
    　Vを２以上の所定の正の整数とし、上記複数のノード部はノード部1,…,Vであるとし、~V={1,…,V}とし、Bを所定の正の整数とし、b=1,…,Bとし、~B={1,…,B}とし、ノード部iにつながっているノード部の集合を~N(i)とし、ノード部iにおけるノード部jに対する双対変数λi|jを構成するb個目のベクトルをλi|j,bとし、t+1回目の更新後の双対変数λi|j,bをλi|j,b (t+1)とし、上記機械学習で用いられるノード部iに対応するコスト関数をfiとし、双対変数λi|jの双対補助変数zi|jを構成するb個目のベクトルをzi|j,bとし、t+1回目の更新後の双対補助変数zi|j,bをzi|j,b (t+1)とし、双対変数λi|jの双対補助変数yi|jを構成するb個目のベクトルをyi|j,bとし、t+1回目の更新後の双対補助変数yi|j,bをyi|j,b (t+1)とし、ノード部iの主変数wi,bのb個目の要素をwiとし、wi,bの最適解のb個目の要素をwi,b *とし、Ai|jは以下の式により定義されるとし、Iを単位行列とし、Oを零行列とし、σ1を所定の正の数とし、Tを正の整数として、
    Figure JPOXMLDOC01-appb-M000010
    　t=0,…,T-1に対して、(a) ノード部iが、以下の式に基づいて双対変数の更新を行うステップと、
    Figure JPOXMLDOC01-appb-M000011
    (b) ノード部iが、以下の式に基づいて、双対補助変数の更新を行うステップと、
    Figure JPOXMLDOC01-appb-M000012
    が行われ、t=0,…,T-1の一部又は全部に対しては、上記(a)及び上記(b)のステップ加えて、
    (c) i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jに双対補助変数yi|j,b (t+1)を送信するステップ、 
    (d) i∈~V, j∈~N(i), b∈~Bとして、双対補助変数yj|i,b (t+1)を受信したノード部iが、zi|j,b (t+1)=yj|i,b (t+1)とするステップと、
    が行われる、
    　機械学習方法。
  12. 　請求項６ないし８のいずれか１項に記載の機械学習システムの各部として、コンピュータを機能させるためのプログラム。
PCT/JP2019/015973 2018-04-12 2019-04-12 機械学習システム、機械学習方法、プログラム Ceased WO2019198815A1 (ja)

Priority Applications (3)

Application Number Priority Date Filing Date Title
US17/047,028 US12450524B2 (en) 2018-04-12 2019-04-12 Machine learning system, machine learning method, and program
JP2020513461A JP7091446B2 (ja) 2018-04-12 2019-04-12 機械学習システム、機械学習方法、プログラム
JP2022037711A JP7309004B2 (ja) 2018-04-12 2022-03-11 潜在変数学習装置、潜在変数学習方法、プログラム

Applications Claiming Priority (10)

Application Number Priority Date Filing Date Title
JP2018076815 2018-04-12
JP2018-076817 2018-04-12
JP2018076816 2018-04-12
JP2018076817 2018-04-12
JP2018-076815 2018-04-12
JP2018-076814 2018-04-12
JP2018076814 2018-04-12
JP2018-076816 2018-04-12
JP2018-202397 2018-10-29
JP2018202397 2018-10-29

Publications (1)

Publication Number Publication Date
WO2019198815A1 true WO2019198815A1 (ja) 2019-10-17

Family

ID=68164056

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2019/015973 Ceased WO2019198815A1 (ja) 2018-04-12 2019-04-12 機械学習システム、機械学習方法、プログラム

Country Status (3)

Country Link
US (1) US12450524B2 (ja)
JP (2) JP7091446B2 (ja)
WO (1) WO2019198815A1 (ja)

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPWO2022249436A1 (ja) * 2021-05-28 2022-12-01
JP2022184274A (ja) * 2021-06-01 2022-12-13 日本電信電話株式会社 変数最適化システム
WO2022269680A1 (ja) * 2021-06-21 2022-12-29 日本電信電話株式会社 変数最適化システム
JPWO2023228317A1 (ja) * 2022-05-25 2023-11-30

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US11132514B1 (en) * 2020-03-16 2021-09-28 Hong Kong Applied Science and Technology Research Institute Company Limited Apparatus and method for applying image encoding recognition in natural language processing

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20140279771A1 (en) * 2013-03-12 2014-09-18 Oracle International Corporation Novel Quadratic Regularization For Neural Network With Skip-Layer Connections

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP2723231A4 (en) 2011-06-23 2015-02-25 Sync Rx Ltd LUMINAL BACKGROUND CLEANING
US20150302317A1 (en) 2014-04-22 2015-10-22 Microsoft Corporation Non-greedy machine learning for high accuracy

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20140279771A1 (en) * 2013-03-12 2014-09-18 Oracle International Corporation Novel Quadratic Regularization For Neural Network With Skip-Layer Connections

Non-Patent Citations (7)

* Cited by examiner, † Cited by third party
Title
CHANG, T. H. ET AL.: "Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method", IEEE TRANSACTIONS ON AUTOMATIC CONTROL, vol. 59, no. 6, 26 February 2014 (2014-02-26), pages 1524 - 1538, XP011548974, ISSN: 0018-9286, DOI: 10.1109/TAC.2014.2308612 *
DUCHI, J. C. ET AL.: "Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling", IEEE TRANSACTIONS ON AUTOMATIC CONTROL, vol. 57, no. 3, 30 June 2011 (2011-06-30), pages 592 - 606, XP011428520, ISSN: 0018-9286, DOI: 10.1109/TAC.2011.2161027 *
FEINBERG, V.: "Non-convex First Order Methods", 20 June 2017 (2017-06-20), XP055645593, Retrieved from the Internet <URL:https://vlad17.github.io/2017/06/20/nonconvex-first-order-methods.html> [retrieved on 20190619] *
MU LI ET AL.: "Scaling Distributed Machine Learning with the Parameter Server", PROCEEDINGS OF THE 11TH USENIX SYMPOSIUM ON OPERATING SYSTEMS DESIGN AND IMPLEMENTATION (OSDI'14), 8 October 2014 (2014-10-08), pages 583 - 598, XP061024674, ISBN: 978-1-931971-16-4, Retrieved from the Internet <URL:https://www.usenix.org/system/files/conference/osdi14/osdi14-paper-li_mu.pdf> [retrieved on 20190311] *
RICHTARIK, P. ET AL.: "Modern Convex Optimization Methods for Large-Scale Empirical Risk Minimization (Part I: Primal Methods)", INTERNATIONAL CONFERENCE ON MACHINE LEARNING (ICML 2015), 6 July 2015 (2015-07-06), pages 1, 4, 8, 13, 20, 22, 28, 30, 36, 39, 41, 44, 46, 47, 51 , 54 , 57 - 63 , 68, Retrieved from the Internet <URL:https://icml.cc/2015/tutorials/2015_ICML_ConvexOptimization_I.pdf> [retrieved on 20190620] *
SHERSON, T. ET AL.: "Derivation and Analysis of the Primal-Dual Method of Multipliers Based on Monotone Operator Theory", TRANSACTIONS ON SIGNAL AND INFORMATION PROCESSING OVER NETWORKS, 6 November 2017 (2017-11-06), pages 1 - 13, XP081281630, Retrieved from the Internet <URL:https://arxiv.org/pdf/1706.02654v3.pdf> [retrieved on 20190618] *
TSIANOS, K. I. ET AL.: "Consensus-Based Distributed Optimization: Practical Issues and Applications in Large-Scale Machine Learning", PROCEEDINGS OF THE 50TH ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING (ALLERTON 2012, 5 October 2012 (2012-10-05), pages 1543 - 1550, XP032345182, ISBN: 978-1-4673-4539-2, DOI: 10.1109/Allerton.2012.6483403 *

Cited By (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPWO2022249436A1 (ja) * 2021-05-28 2022-12-01
JP7548425B2 (ja) 2021-05-28 2024-09-10 日本電信電話株式会社 変数最適化システム
JP2022184274A (ja) * 2021-06-01 2022-12-13 日本電信電話株式会社 変数最適化システム
JP7522076B2 (ja) 2021-06-01 2024-07-24 日本電信電話株式会社 変数最適化システム
WO2022269680A1 (ja) * 2021-06-21 2022-12-29 日本電信電話株式会社 変数最適化システム
JPWO2022269680A1 (ja) * 2021-06-21 2022-12-29
JP7533788B2 (ja) 2021-06-21 2024-08-14 日本電信電話株式会社 変数最適化システム
JPWO2023228317A1 (ja) * 2022-05-25 2023-11-30
JP7732591B2 (ja) 2022-05-25 2025-09-02 Ｎｔｔ株式会社 連合学習システム、モデル学習装置、連合学習方法、モデル学習プログラム

Also Published As

Publication number Publication date
JPWO2019198815A1 (ja) 2021-06-17
JP7091446B2 (ja) 2022-06-27
JP7309004B2 (ja) 2023-07-14
JP2022066553A (ja) 2022-04-28
US20210158226A1 (en) 2021-05-27
US12450524B2 (en) 2025-10-21

Similar Documents

Publication Publication Date Title
JP7091446B2 (ja) 機械学習システム、機械学習方法、プログラム
CN113241126B (zh) 用于训练确定分子结合力的预测模型的方法和装置
JP7179835B2 (ja) モデル生成装置、モデル生成方法、プログラム
Li et al. Robust stochastic configuration networks with maximum correntropy criterion for uncertain data regression
De Bie Clifford algebras, Fourier transforms, and quantum mechanics
Jiang et al. Modeling and prediction of the transmission dynamics of COVID-19 based on the SINDy-LM method
CN114830152A (zh) 用于工业规模的结构数字孪生的基于组件的降阶建模方法和系统
Zhang et al. Design and analysis of recurrent neural network models with non‐linear activation functions for solving time‐varying quadratic programming problems
Köfinger et al. Empirical optimization of molecular simulation force fields by Bayesian inference
CN113254716B (zh) 视频片段检索方法、装置、电子设备和可读存储介质
Bayer et al. Sorting-free Hill-based stability analysis of periodic solutions through Koopman analysis
Pan Distributed optimization and statistical learning for large-scale penalized expectile regression
CN113239799B (zh) 训练方法、识别方法、装置、电子设备和可读存储介质
Calleja et al. Constructive approaches to QP-time-dependent KAM theory for Lagrangian tori in Hamiltonian systems
Rebala et al. Principal component analysis
Xu Dynamics of some coupled nonlinear Schrödinger systems in
Bevanda et al. Koopman-equivariant gaussian processes
WO2022269680A1 (ja) 変数最適化システム
CN116830114A (zh) 一种用于自注意力神经网络的归一化方案
JP7655446B2 (ja) 解析装置及びプログラム
Liang et al. A learning-based approach to event-triggered guaranteed cost control for completely unknown nonlinear systems
JP2022184274A (ja) 変数最適化システム
Channark et al. Generalized and optimal sequence of weights on a progressive‐iterative approximation method with memory for least square fitting
WO2022249436A1 (ja) 変数最適化システム
Li et al. Subspace identification of closed-loop EIV system based on instrumental variables using orthoprojection

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 19786073

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2020513461

Country of ref document: JP

Kind code of ref document: A

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 19786073

Country of ref document: EP

Kind code of ref document: A1

WWG Wipo information: grant in national office

Ref document number: 17047028

Country of ref document: US