JP7548440B2 - OPTIMIZATION METHOD, OPTIMIZATION DEVICE, AND PROGRAM - Google Patents

Description

The present invention relates to an optimization method, an optimization device, and a program.

Black-box optimization is a technique for finding the input value that maximizes (or minimizes) the output value of a function. In black-box optimization, the shape of the function is unknown (i.e., the objective function is a black-box function), and it often takes time to evaluate the output value for a given input value.

Bayesian optimization is known as a representative method used in black-box optimization (Non-Patent Document 1). Bayesian optimization uses a stochastic process called a Gaussian process, but in order to model complex functions, a kernel based on a neural network is required (Non-Patent Document 2).

Snoek, J., Larochelle, H., & Adams, R. P. (2012). Practical Bayesian Optimization of Machine Learning Algorithms. Advances in Neural Information Processing Systems. Wilson, A. G., Hu, Z., Salakhutdinov, R., & Xing, E. P. (2016, May). Deep kernel learning. In Artificial intelligence and statistics (pp. 370-378). PMLR.

However, a problem with training neural networks is that a large amount of training data is generally required.

One embodiment of the present invention has been made in consideration of the above points, and aims to solve an optimization problem in which the objective function is a black-box function using a small amount of data.

In order to achieve the above object, an optimization method according to one embodiment is an optimization method for calculating a solution to a black-box optimization problem whose objective function is a black-box function, in which a computer executes the following steps: a learning procedure, using a data set consisting of input values and output values of a plurality of second black-box optimization problems related to a first black-box optimization problem for which a solution is to be calculated, to learn model parameters for determining an input value to be evaluated next from a set of input values for the black-box optimization problem when the set of input values for the black-box optimization problem is given; a determination procedure, using the model parameters learned by the learning procedure, to determine an input value to be evaluated next from the set of input values for the first black-box optimization problem; and an evaluation procedure, using the input value determined by the determination procedure to evaluate an output value for the first black-box optimization problem.

Optimization problems whose objective function is a black-box function can be solved with a small amount of data.

FIG. 2 is a diagram illustrating an example of a hardware configuration of an optimization device according to the present embodiment. FIG. 2 is a diagram illustrating an example of a functional configuration of an optimization device according to the present embodiment. FIG. 13 is a diagram showing an example of a comparison result with a conventional method.

An embodiment of the present invention will be described below. In this embodiment, an optimization device 10 will be described that is capable of solving a target optimization problem with a smaller data set when a data set of multiple optimization problems related to the target optimization problem is given, with the optimization problem being targeted for an optimization problem whose objective function is a black-box function. Note that an optimization problem whose objective function is a black-box function is also called a black-box optimization problem.

Here, an optimization problem being related to another optimization problem means, for example, optimization problems that are solved for the same or similar purpose in the same or similar field. For example, when considering an optimization problem that determines manufacturing conditions that result in a product with desired characteristics from the manufacturing conditions and the characteristics of the product at that time, an optimization problem for product A and an optimization problem for product B that is functionally similar to product A can be said to be mutually related optimization problems.

The optimization device 10 of this embodiment has a learning period for learning specific parameters and an inference period (test period) for solving the target optimization problem using the learned parameters.

During learning, a data set group { _Ds |s=1,...,S} of S optimization problems related to the target optimization problem is given. Here, _Ds ={( _xsn , _ysn )|n=1,..., _Ns } is a data set of the sth optimization problem, _xsn∈X is the nth input vector of the sth optimization problem, _ysn = _fs ( _xsn ) is the output value at that time, _fs (.) is the black box function of the sth optimization problem, and _Ns is the number of cases (number of data) of the sth optimization problem. Also, X is an input vector set, and for example, when the input vector is a manufacturing condition, it represents a set of vector values that can be taken as the manufacturing condition.

At the time of inference (test), a set of input vectors D _* = {x _*n |n = 1, ..., N _* } for the target optimization problem is given. Here, x _*n ∈ X is the n-th input vector for the target optimization problem, and N _* is the number of input vectors for the target optimization problem. N _* is assumed to be a very small value compared _{to ΣsNs} (for example, a value equal to or smaller than a certain _Ns ). At this time, the objective is to solve the target optimization problem with as few evaluations as possible. Note that evaluation means obtaining an output value of the optimization problem for the input vector.

In the following, the black-box function of the target optimization problem is denoted as f _* (.), and the output value for an input vector x _*n is denoted as y _*n =f _* (x _*n ).

If there is a mechanism for evaluating the objective function (black box function) of the optimization problem, the dataset group { _Ds |s=1,...,S} during learning and the input vector set D _* during inference do not need to be given. In this case, the present embodiment can be similarly applied by generating input vectors and evaluating their output values.

In the following, a maximization problem is considered as the optimization problem. When a minimization problem is considered as the optimization problem, this embodiment can be similarly applied by multiplying the output value by a negative number.

<Hardware Configuration of Optimization Device 10>
The hardware configuration of an optimization device 10 according to this embodiment is shown in Fig. 1. As shown in Fig. 1, the optimization device 10 according to this embodiment is realized by the hardware configuration of a general computer or computer system, and has an input device 101, a display device 102, an external I/F 103, a communication I/F 104, a processor 105, and a memory device 106. Each of these pieces of hardware are connected to each other via a bus 107 so as to be able to communicate with each other.

The input device 101 is, for example, a keyboard, a mouse, a touch panel, various physical buttons, etc. The display device 102 is, for example, a display, a display panel, etc. Note that the optimization device 10 does not have to have at least one of the input device 101 and the display device 102, for example.

The external I/F 103 is an interface with an external device such as a recording medium 103a. The optimization device 10 can read and write data from and to the recording medium 103a via the external I/F 103. Examples of the recording medium 103a include a CD (Compact Disc), a DVD (Digital Versatile Disk), a SD memory card (Secure Digital memory card), and a USB (Universal Serial Bus) memory card.

The communication I/F 104 is an interface for connecting the optimization device 10 to a communication network. The processor 105 is, for example, various arithmetic devices such as a CPU (Central Processing Unit) or a GPU (Graphics Processing Unit). The memory device 106 is, for example, various storage devices such as a HDD (Hard Disk Drive), an SSD (Solid State Drive), a flash memory, a RAM (Random Access Memory), a ROM (Read Only Memory), etc.

The optimization device 10 according to this embodiment has the hardware configuration shown in Fig. 1 and is therefore capable of implementing various processes described below. Note that the hardware configuration shown in Fig. 1 is merely an example, and the optimization device 10 may have, for example, multiple processors 105 or multiple memory devices 106. Furthermore, the optimization device 10 may have various other hardware in addition to the hardware shown in Fig. 1.

<Functional configuration of optimization device 10>
The functional configuration of the optimization device 10 according to this embodiment is shown in Fig. 2. As shown in Fig. 2, the optimization device 10 according to this embodiment has a model unit 201, a meta-learning unit 202, and an evaluation unit 203. Each of these units is realized, for example, by a process in which one or more programs installed in the optimization device 10 are executed by the processor 105.

The optimization device 10 according to this embodiment also has a memory unit 204. The memory unit 204 is realized, for example, by an auxiliary storage device such as an HDD or SSD. Note that the memory unit 204 may also be realized, for example, by a storage device connected to the optimization device 10 via a communication network.

<Model unit 201>
The model unit 201 uses pairs of input vectors and output values to calculate the next input vector to be evaluated.

First, the model unit 201 estimates the objective function of the optimization problem. This can be estimated, for example, using a Gaussian process that uses a kernel based on a neural network (see Non-Patent Document 2). In a Gaussian process, it is assumed that the objective function follows a Gaussian distribution, and the objective function is estimated from an input vector in the form of a probability distribution. At this time, the output value for the input vector x follows a Gaussian distribution, and its mean and variance are

と推定される。ここで、Ｎ_ｓｔはｓ番目の最適化問題においてｔ回目までに評価された入力ベクトルの集合、

where _Nst is the set of input vectors evaluated up to the tth time in the sth optimization problem,

は入力ベクトルｘと評価済みの入力ベクトルｘ'との間のカーネル、

is the kernel between the input vector x and the evaluated input vector x',

は評価済みの入力ベクトル同士のカーネル行列、β＞０はハイパーパラメータ、Ψはパラメータ（以下、Ψをモデルパラメータという。）である。また、カーネルは、

is a kernel matrix between evaluated input vectors, β>0 is a hyperparameter, and Ψ is a parameter (hereinafter, Ψ is referred to as a model parameter). The kernel is

で計算できる。ここで、ｇ（・；Θ）はパラメータΘを持つニューラルネットワーク、αとηはカーネルパラメータ、δはクロネッカーのデルタ関数である。

Here, g(·;Θ) is a neural network with parameter Θ, α and η are kernel parameters, and δ is the Kronecker delta function.

In addition, the estimation of the objective function of the optimization problem is not limited to a Gaussian process using a kernel based on a neural network, and any other method having parameters may be used.

Next, the model unit 201 calculates the degree to be evaluated next using an acquisition function used in Bayesian optimization. As the acquisition function, any acquisition function such as Gaussian process mutual information, expected improvement, upper confidence bound, etc. can be used.

When using Gaussian process mutual information, the likelihood that an input vector x should be evaluated next is

と計算できる。ここで、

Here,

であり、ν＞０はハイパーパラメータである。

where v>0 is a hyper-parameter.

<Meta-learning unit 202>
The meta-learning unit 202 learns model parameters Ψ from a dataset group {D _s |s=1, ..., S} of S optimization problems. The model parameters Ψ include, for example, the parameter Θ of the neural network g(·;Θ), the kernel parameters α and η, and the parameters of the acquisition function.

When learning the model parameter Ψ, the meta-learning unit 202 initializes the model parameter Ψ, and then updates the model parameter Ψ by reinforcement learning until a certain termination condition is satisfied, so that the gap is small when S optimization problems are solved by the model unit 201 using the model parameter Ψ. The gap is the difference between the maximum value of each optimization problem and the highest output value evaluated so far. Note that it is not limited to the gap, and other evaluation measures may be used as long as they can evaluate the output value in the optimization problem.

<Evaluation unit 203>
The evaluation unit 203 calculates output values of a target optimization problem for an input vector.

<Storage unit 204>
The storage unit 204 stores a data set group { _Ds |s=1,...,S} of S optimization problems and unlearned model parameters Ψ during learning, while storing an input vector set D _* ={x _*n |n=1,...,N _* } of a target optimization problem and learned model parameters Ψ during inference.

2 shows an example of a functional configuration in which the same optimization device 10 performs the processing during learning and the processing during inference, but for example, different devices may perform the processing during learning and the processing during inference. In this case, for example, a device performing the processing during learning (learning device) may have only to have a model unit 201, a meta-learning unit 202, and a memory unit 204, and a device performing the processing during inference (inference device) may have only to have a model unit 201, an evaluation unit 203, and a memory unit 204.

<Learning process>
During learning, the optimization device 10 executes, for example, the following processes of Step 11 to Step 13.

Step 11: The meta-learning unit 202 initializes the model parameter Ψ. Note that the model parameter Ψ may be initialized by a known method, for example, by initializing to a random value or by initializing to a value sampled from a certain distribution.

Step 12: For each sε{1, . . . , S}, the following Steps 12-1 to 12-5 are repeated using a data set D _s ={(x _sn , y _sn )|n=1, . . . , N _s } of the sth optimization problem.

Step 12-1: The model unit 201 initializes t←0 and N _st ←φ.

Step 12-2: The model unit 201 calculates the next input vector to be evaluated using the model parameter Ψ and each input vector xε{x _sn |n=1, ..., N _s }\N _st . That is, the model unit 201 calculates the degree a(x; N _st , Ψ) shown in the above formula (4) using the above formulas (1) to (3), and the input vector x with the highest value is set as the next input vector to be evaluated. Hereinafter, the input vector to be evaluated next is set as x'.

Step 12-3: The model unit 201 updates t to t+1, and adds the next input vector x' to be evaluated to _Nst .

Step 12-4: The meta-learning unit 202 updates the model parameter Ψ by reinforcement learning so as to reduce the gap. That is, the meta-learning unit 202 updates the model parameter Ψ by reinforcement learning so as to reduce the difference between the maximum value in {y _sn |n=1, ..., N _s } and the maximum value in the output value f _s (x') corresponding to the input vector x' included in N _st . Note that in reinforcement learning, for example, the gap may be set as a negative reward, and the model parameter Ψ may be updated so as to maximize the cumulative reward sum.

Step 12-5: The meta-learning unit 202 determines whether a predetermined first termination condition is satisfied. If it is determined that the first termination condition is not satisfied, the process returns to Step 12-2. On the other hand, if it is determined that the first termination condition is satisfied, the process of Step 12-1 to Step 12-5 for that s is terminated (that is, in this case, the process of Step 12-1 and subsequent steps is executed for the next s). Note that examples of the first termination condition include the model parameter Ψ having converged, or the number of repetitions of Step 12-1 to Step 12-5 for that s having reached a predetermined number.

Step 13: Finally, the meta-learning unit 202 stores the learned model parameters Ψ in the memory unit 204.

<Processing during inference>
During inference, the optimization device 10 executes, for example, the following processes of Step 21 to Step 24. Note that during inference, s=*.

Step 21: The model unit 201 initializes t←0 and N _*t ←φ.

Step 22: The model unit 201 calculates the next input vector to be evaluated using the trained model parameter Ψ and each input vector x∈D _* ={x _*n |n=1,...,N _* }\N _*t . That is, the model unit 201 calculates the degree a(x;N _*t ,Ψ) shown in the above formula (4) using the above formulas (1) to (3), and the input vector x with the highest value is set as the next input vector to be evaluated. Hereinafter, the input vector to be evaluated next is set as x'=x _*n' .

Step 23: The evaluation unit 203 calculates y _*n' =f _* (x')=f _* (x _*n' ).

Step 24: The model unit 201 updates t to t+1, and adds the next input vector x' to be evaluated to N _*t .

Step 25: The evaluation unit 203 judges whether or not a predetermined second termination condition is satisfied. If it is judged that the second termination condition is not satisfied, the process returns to Step 22. As a result, Step 22 to Step 25 are repeated until the second termination condition is satisfied. On the other hand, if it is judged that the second termination condition is satisfied, the maximum value y _max among the output values f _* (x') corresponding to the input vector x' included in N _*t and the input vector x _max ∈N _*t that gives the maximum value are output. Note that, for example, the second termination condition may be that t=N _* .

<Comparison with conventional methods>
The results of comparing the optimization device 10 according to this embodiment with the conventional method are shown in Fig. 3. In Fig. 3, the test gap is used as the evaluation index. The test gap is the gap calculated during testing, as during learning, using a data set D _* = {(x _*n , y _*n ) | n = 1, ..., N _* } of pairs of input vectors and output values.

In Figure 3, the vertical axis indicates the gap value, and the horizontal axis indicates the number of learning iterations. Furthermore, Ours is the optimization device 10 according to this embodiment, DKL is a Gaussian process using deep kernel learning, GP is a Gaussian process using a Gaussian kernel, RL is reinforcement learning using a feedforward neural network as a model, MetaBO is meta-learning Bayesian optimization, and Random is a method of randomly selecting evaluation points.

As shown in Figure 3, it can be seen that the optimization device 10 (Ours) of this embodiment achieves a lower gap compared to conventional methods.

<Summary>
As described above, the optimization device 10 according to the present embodiment targets an optimization problem whose objective function is a black-box function, and by utilizing knowledge of a plurality of optimization problems related to the target optimization problem, the optimization device 10 can solve the solution of the target optimization problem with a smaller data set (in other words, can find an optimal solution more quickly). Therefore, by using the optimization device 10 according to the present embodiment, it is possible to obtain an optimal solution to the target optimization problem even when only a small data set is available for the target optimization problem.

The optimization device 10 according to this embodiment can be applied to various applications in which black-box optimization is generally used. Examples of such applications include tuning hyperparameters of a machine learning model that outputs a predetermined predicted value when determining manufacturing conditions for a product, chemical substance, material, etc. with desired characteristics.

The present invention is not limited to the specifically disclosed embodiments above, and various modifications, variations, and combinations with known technologies are possible without departing from the scope of the claims.

10 Optimization device 101 Input device 102 Display device 103 External I/F
103a Recording medium 104 Communication I/F
105 Processor 106 Memory device 107 Bus 201 Model unit 202 Meta-learning unit 203 Evaluation unit 204 Storage unit

Claims (7)

1. An optimization method for computing a solution to a black-box optimization problem in which an objective function is a black-box function, comprising the steps of:
a learning procedure for learning model parameters for determining a next input value to be evaluated from a set of input values for a black-box optimization problem, when the set of input values for the black-box optimization problem is given, using a data set consisting of input values and output values for a plurality of second black-box optimization problems related to the first black-box optimization problem to be solved;
a determination step of determining a next input value to be evaluated from a set of input values of the first black-box optimization problem using the model parameters learned by the learning step;
an evaluation step for evaluating an output value of the first black-box optimization problem using input values determined by the determination step;
The computer performs the optimization method. The optimization method comprises:
2. The optimization method according to claim 1, further comprising the step of: iterating the determination of input values by the determination procedure and the evaluation of output values by the evaluation procedure to calculate a solution to the first black-box optimization problem. the model parameters include parameters of a neural network included in a kernel used in a Gaussian process, parameters of the kernel, and parameters of an acquisition function used in Bayesian optimization;
The determination procedure includes:
estimating an objective function of the first black-box optimization problem by a Gaussian process using the kernel;
calculating, based on a Gaussian distribution to which the estimated objective function follows, a degree to which an unevaluated input value included in an input value set of the first black-box optimization problem should be evaluated next using the acquisition function;
3. The optimization method according to claim 1, further comprising determining the input value having the highest degree as the next input value to be evaluated. The optimization method of claim 3, wherein the acquisition function is one of Gaussian process mutual information, expected improvement, or upper confidence bound. The learning procedure includes:
5. The optimization method according to claim 1, further comprising: learning the model parameters by reinforcement learning so that, for each of the second black-box optimization problems, a difference between a maximum value of an output value of the second black-box optimization problem and a maximum value of an output value corresponding to an input value determined so far by the determination procedure using the model parameters being trained becomes small. An optimization device for calculating a solution to a black-box optimization problem in which an objective function is a black-box function, comprising:
a learning unit that uses a data set consisting of input values and output values of a plurality of second black-box optimization problems related to the first black-box optimization problem to be solved, to learn model parameters for determining an input value to be evaluated next from a set of input values for a black-box optimization problem when the set of input values for the black-box optimization problem is given; and
a determination unit that determines an input value to be next evaluated from a set of input values of the first black-box optimization problem using the model parameters learned by the learning unit;
an evaluation unit that evaluates an output value of the first black-box optimization problem using the input values determined by the determination unit;
An optimization device having the above configuration. A program for causing a computer to execute the optimization method according to any one of claims 1 to 5.

Images