Patent Publication Number: US-2023138810-A1

Title: Parameter vector value proposal apparatus, parameter vector value proposal method, and parameter optimization method

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is based upon and claims the benefit of priority from Japanese Patent Application No. 2021-178991, filed Nov. 1, 2021, the entire contents of which are incorporated herein by reference. 
     FIELD 
     Embodiments described herein relate generally to a parameter vector value proposal apparatus, a parameter vector value proposal method and a parameter optimization method. 
     BACKGROUND 
     There are various devices, apparatuses, and application software in our society, and they are composed of various parts. These devices, apparatuses, application software and parts are designed, manufactured and utilized. 
     At the time of design, there is a case where the devices, apparatuses, application software and parts have their characteristics designed to satisfy the specifications required. In such a case, a parameter vector having one or more parameters that can be adjusted at the time of design is changed to various values, simulations, experiments and questionnaires are conducted so as to acquire a characteristic value representing the characteristics obtained when the design is performed based on those values of the parameter vector, and a parameter vector value that enables that characteristic value to satisfy the specifications is obtained. For example, the characteristics are specifically the performance, manufacturing cost and customer satisfaction of a device, an apparatus, application software and a part. It is preferable that the performance of the apparatus and part is as good as possible, the manufacturing cost is as low as possible, and the customer satisfaction is as high as possible. Where it is preferable that the characteristic value should be large, a parameter vector value that maximizes the characteristic value should be obtained in a shorter time, with less work, and at a low cost. Where it is preferable that the characteristic value should be as small as possible, a parameter vector value that minimizes the characteristic value should be obtained in a shorter time, with less work, and at a low cost. 
     The act of determining a parameter vector value that maximizes or minimizes the characteristic value is referred to as parameter optimization. A characteristic value that changes in accordance with a parameter vector value is referred to as an objective function. Simulations, experiments, and questionnaires are means for observing the value of the objective function, that is, the characteristic value. The characteristic value relating to each parameter vector value is not known until a characteristic value is observed by executing a simulation, an experiment, and a questionnaire, and the objective function is therefore unknown. In many cases, noise is included when the characteristic value, that is, the value of the objective function, is observed. 
     There is a case where parameter optimization is used at the time of manufacture. For example, there is a case where a parameter vector value that maximizes the yield at the time of manufacture is obtained, or where a parameter vector value that minimizes the failure rate after shipment is obtained. 
     There is also a case where parameter optimization is used at the time of use. For example, at the time of initial setting by the user, a parameter vector value is obtained that enables a device, an apparatus, application software, or part delivered to the user to exert maximum performance in the user&#39;s usage environment. 
     Where the number of parameters to be adjusted is represented by D, the dimension of the parameter vector is D. A certain D-dimensional parameter vector value can be regarded as one point in the D-dimensional space. Therefore, the space in which an optimum D-dimensional parameter vector value is searched for is the D-dimensional space. Where the D-dimensional parameter vector does not have an upper limit value or a lower limit value, the range for searching the optimum D-dimensional parameter vector value is the whole of the D-dimensional space. Where the D-dimensional parameter vector has an upper limit value or a lower limit value, that is, where the D-dimensional parameter vector has a domain, the range for searching for the optimum D-dimensional parameter vector value is that domain in the D-dimensional space. The larger the value of D is, the wider will be the search space and the search range, so that optimization becomes more difficult. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG.  1    is a diagram showing a functional configuration example of a parameter optimization system according to an embodiment. 
         FIG.  2    is a diagram illustrating a flow of a parameter optimization process performed by the parameter optimization system of the embodiment. 
         FIG.  3    is a diagram showing a pseudo program code included in the parameter optimization process shown in  FIG.  2    and performed by a parameter vector value proposal apparatus. 
         FIG.  4    is a diagram illustrating a state in which the value of an objective function is observed at seven observation points in the D-dimensional space of the case where D=2. 
         FIG.  5    is a diagram showing a functional configuration example of a parameter optimization system according to modification 9. 
         FIG.  6    is a diagram showing a pseudo program code which is according to modification 10 and corresponds to the parameter optimization process shown in  FIG.  2   . 
         FIG.  7    is a diagram showing a hardware configuration example of the parameter vector value proposal apparatus. 
     
    
    
     DETAILED DESCRIPTION 
     A parameter vector value proposal apparatus according to an embodiment includes a storage device and processing circuitry. The storage device stores observation data, which is a set of pairs each consisting of a parameter vector value representing a point in a D-dimensional space (D is an integer of 2 or more) and an observation value of an objective function at the point. The processing circuitry determines, as a low-dimensional search space, an R-dimensional affine subspace (R is an integer that is not less than 1 and less than D) that passes through a point represented by a predetermined parameter vector value in the D-dimensional space; extracts, as extracted data, a set of pairs corresponding to one or more points at which similarity to a point included in the low-dimensional search space are equal to or more than a predetermined value, the one or more points being among one or more points in the D-dimensional space represented by one or more parameter vector values included in the observation data stored in the storage device; and proposes a parameter vector value representing a point at which a value of the objective function is to be observed next, based on the extracted data. 
     In the description below, the D-dimensional parameter vector value may be abbreviated simply as a parameter vector value. The description of a domain will be omitted. Even though the description of the domain is omitted, the search range is limited to the domain. 
     A parameter optimization method is disclosed in Non-Patent Document 1 (J. Kirschner, M. Mutny, N. Hiller, R. Ischebeck, and A. Krause, “Adaptive and safe Bayesian optimization in high dimensions via one-dimensional subspaces,” in Proceedings of the 36th International Conference on Machine Learning, vol. 97, pp. 3429-3438, PMLR, 2019). The method disclosed in this document is a Bayesian optimization method adapted for the case where D is an integer of 2 or more, and is known to have good search efficiency where the value of D is large. In this method, the search space is limited to a one-dimensional space in the D-dimensional space, and while the one-dimensional search space is switched from one to another, the proposal of a point where the value of the objective function should be observed next and the observation of the value of the objective function at the proposal point are repeated. As described above, the point is a D-dimensional parameter vector value. The point at which the value of the objective function is observed is referred to as an observation point. 
     In the proposal of an observation point, an acquisition function is generated instead of the unknown objective function, and the point where the value of the acquisition function is maximum is proposed as a candidate point where the value of the objective function may be minimum. The acquisition function is calculated based on Gaussian process regression. In the description below, Gaussian process regression will be abbreviated as GP regression. 
     In GP regression, the value of an objective function at an unobserved point is predicted, using one or more points at which an objective function has been observed and observation values which the objective function takes at the one or more points. At the time, the calculation of an inverse matrix is required. 
     The calculation order of the inverse matrix is O(N 3 ). N represents the number of points at which the value of the objective function has been observed. As the number of repetitions of the proposal and the observation increases and the value of N increases, the computational cost of the inverse matrix increases. 
     On the other hand, in the method of Patent Document 1 (Japanese Patent Application No. 2020-185291), the points which are included among N points where the value of an objective function has already been observed and which are to be used for GP regression are limited those points where the distance to a low-dimensional search space whose space dimension is lower than D is equal to or less than a predetermined threshold. 
     Where the number of points limited is represented by N′, the calculation order of the calculation of the inverse matrix is O(N′ 3 ). This reduces the computational cost of the inverse matrix. 
     However, the method of Patent Document 1 does not show how to determine a threshold value corresponding to the distance to the low-dimensional search space. The accuracy of predicting the value of the objective function at each point in GP regression changes, depending upon which points are to be used from among the N points where the values of objective functions have already been observed. If the points that have a large effect on the prediction accuracy are not utilized, the prediction accuracy will deteriorate. Therefore, if the points to be used for GP regression are determined using a uniform threshold value which is predetermined for the distances to the low-dimensional search space, the prediction accuracy may deteriorate. If the prediction accuracy deteriorates, there is a high possibility that the search efficiency of a parameter vector value will deteriorate. The deterioration of the search efficiency is undesirable even if the calculation cost of the inverse matrix can be reduced. 
     An object to be solved by the present invention is to provide a parameter vector value proposal apparatus, a parameter vector value proposal method and a parameter optimization method that realize both improvement in the search efficiency of a parameter vector value and reduction in the calculation cost. 
     In what follows, a parameter vector value proposal apparatus, a parameter vector value proposal method, a parameter optimization method, and a parameter vector value proposal program according to the present embodiment will be described with reference to the accompanying drawings. 
       FIG.  1    is a diagram showing a functional configuration example of a parameter optimization system  1  according to the present embodiment. As shown in  FIG.  1   , the parameter optimization system  1  is a computer system including a parameter vector value proposal apparatus  100  and an observation apparatus  200 . The parameter vector value proposal apparatus  100  and the observation apparatus  200  are coupled to each other by wire or by wireless. The parameter vector value proposal apparatus  100  is a computer that proposes a parameter vector value (proposal point) at which the value of an objective function is to be observed next. The observation apparatus  200  acquires an observation value of the objective function at the proposal point by observing the value of the objective function at the proposal point. Specifically, the observation is carried out by simulations, experiments, questionnaires, etc., based on parameter values. The parameter optimization system  1  repeats the proposal of a proposal point by the parameter vector value proposal apparatus  100  and the acquisition of the observation value of the objective function at the proposal point by the observation apparatus  200 , and outputs the parameter vector value (observation point) corresponding to the minimum observation value as an optimum point. In the description below, the observation value of the objective function may be abbreviated simply as an observation value. 
     Parameter optimization is performed either for the maximization of the value of the objective function or for the minimization of the value of the objective function. The maximization becomes equivalent to the minimization by multiplying the value of the objective function by −1. For the sake of simplicity, a description will be given of the case where a parameter vector value that minimizes the value of the objective function is calculated. It should be noted, however, that the parameter optimization of the present embodiment is not limited to the minimization. The parameter optimization of the present embodiment can also be applied to the maximization of the value of the objective function. 
     As shown in  FIG.  1   , the parameter vector value proposal apparatus  100  includes a storage unit  101 , a search space determination unit  102 , an extraction unit  103 , a proposal unit  104 , and a control unit  105 . 
     The storage unit  101  stores a set of pairs each consisting of a D-dimensional parameter vector value and an observation value of an objective function corresponding to the D-dimensional parameter vector value. The data on the set will be referred to as observation data. The parameter vector value represents a point in the D-dimensional space (D is a natural number of 2 or more). The observation value is obtained by the observation apparatus  200  by using a simulation, an experiment, a questionnaire, or the like, based on the corresponding D-dimensional parameter vector value. 
     The search space determination unit  102  determines an R-dimensional affine subspace (R is an integer not less than 1 and less than D) passing through a point represented by a predetermined parameter vector value in the D-dimensional space, and outputs the determined R-dimensional affine subspace as a low-dimensional search space. As the predetermined parameter vector value, the observation value included among the observation data stored in the storage unit  101  and considered to be the best one is adopted; for example, the parameter vector value corresponding the minimum value is adopted. That observation value is referred to as the best observation value. 
     The extraction unit  103  refers to one or more points in the D-dimensional space represented by the one or more parameter vector values included in the observation data stored in the storage unit  101 , and extracts, as extracted data, a set of pairs corresponding to one or more points at which degrees of similarity to a point included in the low-dimensional search space are equal to or more than a predetermined value. 
     Based on the extracted data, the proposal unit  104  proposes a parameter vector value representing a point (parameter vector value) at which the value of the objective function is to be observed next. That point will be referred to as a proposal point. The value of the objective function at the proposal point is observed by the observation apparatus  200 , and the observation value corresponding to the proposal point is acquired. The pair consisting of the proposal point (parameter vector value) and the observation value corresponding to the proposal point is stored in the storage unit  101 . 
     The control unit  105  comprehensively controls the parameter vector value proposal apparatus  100 . Specifically, the control unit  105  controls the storage of observation data in the storage unit  101 , the determination of a search space made by the search space determination unit  102 , the extraction of extracted data performed by the extraction unit  103 , and the proposal of a proposal point by the proposal unit  104 , in accordance with the acquisition of an observation value performed by the observation apparatus  200  and until the end condition is satisfied. In order to perform control in accordance with the acquisition of an observation value by the observation apparatus  200 , the control unit  105  has a function of monitoring how the storage unit  101  accepts an observation value and a function of monitoring how the proposal unit  104  transmits the observation value to a device external of the parameter vector value proposal apparatus  100 . The optimum point (parameter vector value) at the end of the iteration will be referred to as an optimum point. The optimum point is provided to an external device different from the parameter vector value proposal apparatus  100  under the control of the control unit  105 . 
       FIG.  2    is a diagram illustrating a flow of a parameter optimization process performed by the parameter optimization system  1  of the present embodiment.  FIG.  3    is a diagram showing a pseudo program code included in the parameter optimization process shown in  FIG.  2    and performed by the parameter vector value proposal apparatus. The parameter optimization shown in  FIGS.  2  and  3    is executed under the control of the control unit  105  that controls the storage unit  101 , the search space determination unit  102 , the extraction unit  103  and the proposal unit  104 . 
     As shown in  FIG.  2   , the control unit  105  first executes initialization of the parameter vector value proposal apparatus  100  (S 201 ). The control unit  105  sets the time t to 0 at the start of S 201 , as shown in S 301  of  FIG.  3   , and sets the time t to 1 at the end of S 201 . The time t is a time used for the parameter optimization process, and indicates the number of times the process included in the process loop of  FIG.  2    is performed. 
     In S 201 , the control unit  105  initializes the storage unit  101  and sends observation data described later to the extraction unit  103 . For initialization, at least one pair consisting of a D-dimensional parameter vector value and an observation value of the objective function corresponding to that D-dimensional parameter vector value is stored in the storage unit  101 . 
     Not only in step S 201  but also in the other steps, the number of pairs stored in the storage unit  101  as a result of storing data in the storage unit  101  at the time t will be represented by N t . From this definition, the number of pairs stored in the storage unit  101  after one or more pairs are stored in S 201  at the time  0  is N 0 , which is an integer of 1 or more. 
     The N 0  D-dimensional parameter vector values stored in the storage unit  101  at the time  0  are represented by x n  (n=0, 1, . . . , N 0 −1), and the observation value of the objective function corresponding to x n  is represented by y n  (n=0, 1, . . . , N 0 −1). The D-dimensional parameter vector value x n  is a vector, and the observation value y n  is a scalar. The observation value y of the objective function with respect to the D-dimensional parameter vector value x is represented by y=f(x)+ε. It should be noted that f represents an objective function, and ε represents a noise component when the value of the objective function is observed. The noise component ε describes, for example, a Gaussian distribution having a mean of 0 and a standard deviation of σ. Where there is no noise component, σ may be regarded as 0. 
     Not only in S 201  but also in the other steps, the set D t  of N t  pairs stored in the storage unit  101  at the time t is represented by the formula (1) set forth below. 
     D t  is referred to as observation data at the time t. 
         D   t ={( x   n   , y   n )∥ n= 0,1, . . . ,  N   t −1}  (1)
 
     The observation data D 0  stored in the storage unit  101  after the initialization in S 201  at the time  0  is represented by the formula (2) set forth below, as shown in S 302  of  FIG.  3   . In S 301 , the observation data D 0  is supplied from the storage unit  101  to the extraction unit  103 . 
         D   0 ={( x   n   , y   n )| n= 0,1, . . . ,  N   0 −1}  (2)
 
     The observation data D 0  may be composed of only the data observed before S 201 ; alternatively, each x n  (n=0, 1, . . . , N 0 −1) is determined at random within the domain for S 201 , and y n  corresponding to each x n  may be observed by the observation apparatus  200 . The observation data may be a combination of these. 
     As shown in S 303  of  FIG.  3   , subsequent steps S 202  to S 207  are repeated at the time t=1, 2, . . . , T. T is a predetermined upper limit of the time t. 
     After S 201  is performed, the search space determination unit  102  determines a search space (S 202 ). Specifically, in S 202 , the search space determination unit  102  determines a low-dimensional search space S t  and supplies it to the extraction unit  103 . The number of dimensions of the low-dimensional search space S t  is represented by R t . R t  is an integer having a number of dimensions of 1 or more and less than D, and is an integer satisfying 1≤R t &lt;D. The value of R t  may be changed according to the time t, or may be made constant regardless of the time t. The value of R t  may be a predetermined value or a randomly determined value. 
     In order to determine the low-dimensional search space S t , the search space determination unit  102  acquires the best observation point from the storage unit  101 . The best observation point is an observation point which is among the set {y n |n=0, 1, . . . , N t−1 −1} of observation values included in the observation data D t−1  stored in the storage unit  101  and which corresponds to the smallest observation value. This smallest observation value is represented by y bt−1 , and the best observation point corresponding to y bt−1  is represented by x bt−1 . As shown in S 304  of  FIG.  3   , b t−1  is an index represented by the following formula (3). 
     
       
         
           
             
               
                 
                   
                     b 
                     
                       t 
                       - 
                       1 
                     
                   
                   = 
                   
                     
                       argmin 
                       
                         
                           n 
                           = 
                           0 
                         
                         , 
                         1 
                         , 
                         … 
                             
                         , 
                         
                           
                             N 
                             
                               t 
                               - 
                               1 
                             
                           
                           - 
                           1 
                         
                       
                     
                     ⁢ 
                     
                       y 
                       n 
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
     In S 202 , the search space determination unit  102  determines a low-dimensional search space S t  passing through the best observation point x bt−1 , as shown in S 306  of  FIG.  3   . The low-dimensional search space S t  is an R t -dimensional affine subspace. S t  is expressed by the formula (4) set forth below. x bt−1  is a position vector of S t . U t  is an R t -dimensional linear subspace associated with the R t -dimensional affine subspace S t . 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           S 
                           t 
                         
                         = 
                           
                         
                           
                             x 
                             
                               b 
                               
                                 t 
                                 - 
                                 1 
                               
                             
                           
                           + 
                           
                             U 
                             t 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         
                           { 
                           
                             
                               
                                 x 
                                 
                                   b 
                                   
                                     t 
                                     - 
                                     1 
                                   
                                 
                               
                               + 
                               
                                 u 
                                 t 
                               
                             
                             ❘ 
                             
                               
                                 u 
                                 t 
                               
                               ∈ 
                               
                                 U 
                                 t 
                               
                             
                           
                           } 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
     The low-dimensional search space S t , that is, the R t -dimensional affine subspace S t , changes according to the time t shown in the loop of  FIG.  2   . As x bt−1  or U t  changes according to the time t, S t  also changes. As will be described later, since an element is added to the observation data each time the time advances, the best observation point x bt−1  may also change according to the time t. Ut changes when R t  changes according to the time t. Even where R t  is a constant value that does not depend on the time t, U t  changes by changing the direction of the linear subspace according to the time t. 
     After S 202  is performed, the extraction unit  103  executes the extraction process (S 203 ). In S 203 , the extraction unit  103  searches the storage unit  101  for the set {x n |n=0, 1, . . . , N t−1 −1} of observation points included in the observation data D t−1  received from the storage unit  101  at the time t, and extracts from the storage unit  101  those pairs corresponding to one or more points at which a similarity to a predetermined point x′ included in the low-dimensional search space S t  is equal to or more than a predetermined value T t . The extracted pairs are supplied to the proposal unit  104 . The query used when the extraction unit  103  makes an inquiry to the storage unit  101  is not shown in  FIG.  1   . 
     As the predetermined point x′ included in the low-dimensional search space S t , for example, the same point in S t  is adopted regardless of the observation points x n  (n=0, 1, . . . , N t−1 −1). The similarity to the observation point x n  to a predetermined point x′ is calculated by k(x n ,x′). It should be noted that k(⋅, ⋅) is a kernel function that evaluates the similarity between two points. As a kernel function, linear kernel, squared exponential kernel, exponential kernel, Matern 3/2 kernel, Matern 5/2 kernel, rational luadratic kernel, ARD squared exponential kernel, ARD exponential kernel, ARD Matern 3/2 kernel, ARD Matern 5/2 kernel, ARD Rational Quadratic kernel, etc. are known. One of these may be adopted as the kernel function, or another kernel function different from the above may be adopted. A Kernel function may include a hyperparameter. As the value of the hyperparameter, a predetermined value may be adopted, or a value may be estimated from the observation data or from extracted data described later. 
     As shown in S 307  of  FIG.  3   , at the time t, the extraction unit  103  extracts a set E t  of pairs to be extracted from the observation data D t−1 . E t  is referred to as extracted data. As shown in S 307 , the extracted data E t  is represented by the following formula (5). 
         E   t ={( x   n   , y   n )| k ( x   n   , x ′)≥ T   t   , n= 0,1, . . . ,  N   t−1 −1}  (5)
 
     The number of elements of the extracted data E t  is represented by N′ t . N′ t  changes, depending upon the value of T t , and takes a value which is not less than 0 and not more than N t−1 . A value that permits N′ t  to be 1 or more is adopted as T t . For example, N t−1  k(x n ,x′) (n=0, 1, . . . , N t−1 −1) are calculated, and one of the k(x n ,x′) is set to T t , whereby it is guaranteed that N′ t  is 1 or more. Where N′ t  is equal to N t−1 , E t  is equal to D t−1 . In the description below, it is assumed that N′ t  is not less than 1 and not more than N t−1 . 
     The predetermined point x′ need not be the same point in S t , depending upon the observation point x n  (n=0, 1, . . . , N t−1 −1) , but a different point may be used for each observation point x n . For example, a point obtained by orthographically projecting the observation point x n  onto the low-dimensional search space S t  may be adopted as the predetermined point x′. The predetermined point x′ in this case is represented by the formula (6) set forth below. P St  is a function representing a point obtained by orthographically projecting a point in the D-dimensional space onto the low-dimensional search space S t . 
         x′=P   St ( x   n )   (6)
 
     The function P St  is expressed by the formula (7) set forth below. The I D  represents an identity matrix of D rows and D columns. P Ut  represents an orthographic projection matrix onto the R t -dimensional linear subspace U t . 
         P   S     t   ( x )=( I   D   −P   U     t   ) x   b     t−1     +P   U     t     x    (7)
 
     Even in this case, T t  that permits N′ t  to be 1 or more can be set. In this case, the set E t  of N′ t  observation data extracted from the observation data D t−1  by the extraction unit  103  is represented by the formula (8) set forth below. In this case, E t  shown in S 307  of  FIG.  3    can be replaced with the E t  of the formula (8). 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           E 
                           t 
                         
                         = 
                           
                         
                           { 
                           
                             
                               
                                 ( 
                                 
                                   
                                     x 
                                     n 
                                   
                                   , 
                                   
                                     y 
                                     n 
                                   
                                 
                                 ) 
                               
                               ❘ 
                               
                                 
                                   k 
                                   ⁡ 
                                   ( 
                                   
                                     
                                       x 
                                       n 
                                     
                                     , 
                                     
                                       x 
                                       ′ 
                                     
                                   
                                   ) 
                                 
                                 ≥ 
                                 
                                   T 
                                   t 
                                 
                               
                             
                             , 
                             
                               n 
                               = 
                               0 
                             
                             , 
                             1 
                             , 
                             … 
                                 
                             , 
                             
                               
                                 N 
                                 
                                   t 
                                   - 
                                   1 
                                 
                               
                               - 
                               1 
                             
                           
                           } 
                         
                       
                     
                   
                   
                     
                       
                         = 
                          
                         
                           { 
                           
                             
                               
                                 ( 
                                 
                                   
                                     x 
                                     n 
                                   
                                   , 
                                   
                                     y 
                                     n 
                                   
                                 
                                 ) 
                               
                               ❘ 
                               
                                 
                                   k 
                                   ⁡ 
                                   ( 
                                   
                                     
                                       x 
                                       n 
                                     
                                     , 
                                     
                                       
                                         P 
                                         
                                           S 
                                           t 
                                         
                                       
                                       ( 
                                       
                                         x 
                                         n 
                                       
                                       ) 
                                     
                                   
                                   ) 
                                 
                                 ≥ 
                                 
                                   T 
                                   t 
                                 
                               
                             
                             , 
                             
                               n 
                               = 
                               0 
                             
                             , 
                             1 
                             , 
                             … 
                                 
                             , 
                             
                               
                                 N 
                                 
                                   t 
                                   - 
                                   1 
                                 
                               
                               - 
                               1 
                             
                           
                           } 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
     As the predetermined point x′, the position in the low-dimensional search space S t  need not be defined; it may be defined as a certain point x′ in the low-dimensional search space S t . Even in this case, T t  that permits N′ t  to be 1 or more can be set. That fact that the similarity k(x n ,x′) with respect to the point x′ included in the low-dimensional search space S t  is T t  or more is equivalent to the fact that the maximum value of the similarity k(x n ,x′) with respect to all the points x′ included in the low-dimensional search space S t  is T t  or more, that is, the maximum similarity is T t  or more. Hence, the formula (9) set forth below holds. In this case, E t  shown in S 307  of  FIG.  3    can be replaced with the E t  of the formula (9). That is, the extraction unit  103  refers to one or more points x n  included in the D-dimensional space represented by one or more parameter vector values included in the observation data D t−1  stored in the storage unit  101  and extracts, as extracted data E t , a set of pairs corresponding to one or more points at which a maximum similarity, which is a maximum value of the similarity k(x n ,x′) to all points x′ included in the low-dimensional search space S t , is a predetermined value T t  or more. 
     
       
         
           
             
               
                 
                   
                     E 
                     t 
                   
                   = 
                   
                     
                       { 
                       
                         
                           
                             ( 
                             
                               
                                 x 
                                 n 
                               
                               , 
                               
                                 y 
                                 n 
                               
                             
                             ) 
                           
                           ❘ 
                           
                             
                               
                                   
                                 ∃ 
                               
                               
                                 x 
                                 ′ 
                               
                             
                             ∈ 
                             
                               S 
                               t 
                             
                           
                         
                         , 
                         
                           
                             k 
                             ⁡ 
                             ( 
                             
                               
                                 x 
                                 n 
                               
                               , 
                               
                                 x 
                                 ′ 
                               
                             
                             ) 
                           
                           ≥ 
                           
                             T 
                             t 
                           
                         
                         , 
                         
                           n 
                           = 
                           0 
                         
                         , 
                         1 
                         , 
                         … 
                             
                         , 
                         
                           
                             N 
                             
                               t 
                               - 
                               1 
                             
                           
                           - 
                           1 
                         
                       
                       } 
                     
                     = 
                     
                       { 
                       
                         
                           
                             ( 
                             
                               
                                 x 
                                 n 
                               
                               , 
                               
                                 y 
                                 n 
                               
                             
                             ) 
                           
                           ❘ 
                           
                             
                               
                                 max 
                                 
                                   
                                     x 
                                     ′ 
                                   
                                   ∈ 
                                   
                                     S 
                                     t 
                                   
                                 
                               
                               
                                 k 
                                 ⁡ 
                                 ( 
                                 
                                   
                                     x 
                                     n 
                                   
                                   , 
                                   
                                     x 
                                     ′ 
                                   
                                 
                                 ) 
                               
                             
                             ≥ 
                             
                               T 
                               t 
                             
                           
                         
                         , 
                         
                           n 
                           = 
                           0 
                         
                         , 
                         1 
                         , 
                         … 
                             
                         , 
                         
                           
                             N 
                             
                               t 
                               - 
                               1 
                             
                           
                           - 
                           1 
                         
                       
                       } 
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
       
         
           
             	 
             
               
                 max 
                 
                   
                     x 
                     ′ 
                   
                   ∈ 
                   
                     S 
                     t 
                   
                 
               
               
                 k 
                 ⁡ 
                 ( 
                 
                   
                     x 
                     n 
                   
                   , 
                   
                     x 
                     ′ 
                   
                 
                 ) 
               
               : 
               maximum 
               ⁢ 
                 
               similarity 
             
           
         
       
     
     Where the kernel function to be adopted is a squared exponential kernel function or an ARD squared exponential kernel function, the formula (10) set forth below holds depending upon the kernel function. In this case, E t  shown in S 307  of  FIG.  3    can be replaced with the E t  of the formula (10). 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           E 
                           t 
                         
                         = 
                           
                         
                           { 
                           
                             
                               
                                 ( 
                                 
                                   
                                     x 
                                     n 
                                   
                                   , 
                                   
                                     y 
                                     n 
                                   
                                 
                                 ) 
                               
                               ❘ 
                               
                                 
                                   
                                       
                                     ∃ 
                                   
                                   
                                     x 
                                     ′ 
                                   
                                 
                                 ∈ 
                                 
                                   S 
                                   t 
                                 
                               
                             
                             , 
                             
                               
                                 k 
                                 ⁡ 
                                 ( 
                                 
                                   
                                     x 
                                     n 
                                   
                                   , 
                                   
                                     x 
                                     ′ 
                                   
                                 
                                 ) 
                               
                               ≥ 
                               
                                 T 
                                 t 
                               
                             
                             , 
                             
                               n 
                               = 
                               0 
                             
                             , 
                             1 
                             , 
                             … 
                                 
                             , 
                             
                               
                                 N 
                                 
                                   t 
                                   - 
                                   1 
                                 
                               
                               - 
                               1 
                             
                           
                           } 
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         
                           { 
                           
                             
                               
                                 ( 
                                 
                                   
                                     x 
                                     n 
                                   
                                   , 
                                   
                                     y 
                                     n 
                                   
                                 
                                 ) 
                               
                               ❘ 
                               
                                 
                                   
                                     max 
                                     
                                       
                                         x 
                                         ′ 
                                       
                                       ∈ 
                                       
                                         S 
                                         t 
                                       
                                     
                                   
                                   
                                     k 
                                     ⁡ 
                                     ( 
                                     
                                       
                                         x 
                                         n 
                                       
                                       , 
                                       
                                         x 
                                         ′ 
                                       
                                     
                                     ) 
                                   
                                 
                                 ≥ 
                                 
                                   T 
                                   t 
                                 
                               
                             
                             , 
                             
                               n 
                               = 
                               0 
                             
                             , 
                             1 
                             , 
                             … 
                                 
                             , 
                             
                               
                                 N 
                                 
                                   t 
                                   - 
                                   1 
                                 
                               
                               - 
                               1 
                             
                           
                           } 
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         
                           { 
                           
                             
                               
                                 ( 
                                 
                                   
                                     x 
                                     n 
                                   
                                   , 
                                   
                                     y 
                                     n 
                                   
                                 
                                 ) 
                               
                               ❘ 
                               
                                 
                                   k 
                                   ⁡ 
                                   ( 
                                   
                                     
                                       x 
                                       n 
                                     
                                     , 
                                     
                                       
                                         P 
                                         
                                           S 
                                           t 
                                         
                                       
                                       ( 
                                       
                                         x 
                                         n 
                                       
                                       ) 
                                     
                                   
                                   ) 
                                 
                                 ≥ 
                                 
                                   T 
                                   t 
                                 
                               
                             
                             , 
                             
                               n 
                               = 
                               0 
                             
                             , 
                             1 
                             , 
                             … 
                                 
                             , 
                             
                               
                                 N 
                                 
                                   t 
                                   - 
                                   1 
                                 
                               
                               - 
                               1 
                             
                           
                           } 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
     The squared exponential kernel function k(x i ,x j ) for two points x i  and x j  is expressed by the formula (11) set forth below. θ σ  and θ l  are hyperparameters that are referred to as the signal standard deviation and the length scale, respectively. Each of the values of θ σ  and θ l  has to be larger than 0. 
     
       
         
           
             
               
                 
                   
                     k 
                     ⁡ 
                     ( 
                     
                       
                         x 
                         i 
                       
                       , 
                       
                         x 
                         j 
                       
                     
                     ) 
                   
                   = 
                   
                     
                       θ 
                       σ 
                       2 
                     
                     ⁢ 
                     
                       exp 
                       ⁡ 
                       ( 
                       
                         
                           - 
                           
                             1 
                             2 
                           
                         
                         ⁢ 
                         
                           
                             
                                
                               
                                 
                                   x 
                                   i 
                                 
                                 - 
                                 
                                   x 
                                   j 
                                 
                               
                                
                             
                             2 
                           
                           
                             θ 
                             l 
                             2 
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
     From the definition formula shown in the formula (11), the following formula (12) is established. 
     
       
         
           
             
               
                 
                   
                     
                       max 
                       
                         
                           x 
                           ′ 
                         
                         ∈ 
                         
                           S 
                           t 
                         
                       
                     
                     
                       k 
                       ⁡ 
                       ( 
                       
                         
                           x 
                           n 
                         
                         , 
                         
                           x 
                           ′ 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     k 
                     ⁡ 
                     ( 
                     
                       
                         x 
                         n 
                       
                       , 
                       
                         
                           P 
                           
                             S 
                             t 
                           
                         
                         ( 
                         
                           x 
                           n 
                         
                         ) 
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
     The ARD squared exponential kernel function k(x i ,x j ) for the two points x i  and x j  is expressed by the formula (13) set forth below. θ l  is a hyperparameter and represents a D-dimensional length scale vector having a length scale for each coordinate axis direction of the D-dimensional space as an element. ⋅[d] (d=0, 1, . . . , D−1) represents the d-th element of the vector. 
     
       
         
           
             
               
                 
                   
                     k 
                     ⁡ 
                     ( 
                     
                       
                         x 
                         i 
                       
                       , 
                       
                         x 
                         j 
                       
                     
                     ) 
                   
                   = 
                   
                     
                       θ 
                       σ 
                       2 
                     
                     ⁢ 
                     
                       exp 
                       ⁡ 
                       ( 
                       
                         
                           - 
                           
                             1 
                             2 
                           
                         
                         ⁢ 
                         
                           
                             ∑ 
                             
                               d 
                               = 
                               0 
                             
                             
                               D 
                               - 
                               1 
                             
                           
                           
                             
                               
                                 ( 
                                 
                                   
                                     
                                       ( 
                                       
                                         x 
                                         i 
                                       
                                       ) 
                                     
                                     
                                       [ 
                                       d 
                                       ] 
                                     
                                   
                                   - 
                                   
                                     
                                       ( 
                                       
                                         x 
                                         j 
                                       
                                       ) 
                                     
                                     
                                       [ 
                                       d 
                                       ] 
                                     
                                   
                                 
                                 ) 
                               
                               2 
                             
                             
                               
                                 ( 
                                 
                                   θ 
                                   l 
                                 
                                 ) 
                               
                               
                                 [ 
                                 d 
                                 ] 
                               
                               2 
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
           
         
       
     
     From the definition formula shown in the formula (13), the following formula (14) is established. 
     
       
         
           
             
               
                 
                   
                     
                       max 
                       
                         
                           x 
                           ′ 
                         
                         ∈ 
                         
                           S 
                           t 
                         
                       
                     
                     
                       k 
                       ⁡ 
                       ( 
                       
                         
                           x 
                           n 
                         
                         , 
                         
                           x 
                           ′ 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     k 
                     ⁡ 
                     ( 
                     
                       
                         x 
                         n 
                       
                       , 
                       
                         
                           P 
                           
                             S 
                             t 
                           
                         
                         ( 
                         
                           x 
                           n 
                         
                         ) 
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
           
         
       
     
     After S 203  is performed, the proposal unit  104  executes the proposal process (S 204 ). In S 204  at the time t, the proposal unit  104  utilizes the extracted data E t  received from the extraction unit  103 , proposes a point at which the value of the objective function is to be observed next, sends it to the storage unit  101 , and outputs it to the outside of the parameter vector value proposal apparatus  100 . Since the observation points included in the observation data D t−1  stored in the storage unit  101  in S 203  at the time t are x 0 ,x 1 , . . . , X Nt−1−1 , N t−1  is adopted as the index of a point to be observed next, and the point proposed by the proposal unit  104  is represented as x Nt−1 . This x Nt−1  is referred to as a proposal point. 
     As shown in S 308  of  FIG.  3   , the proposal unit  104  constructs an acquisition function from a surrogate model that expresses the characteristics of an unknown objective function, proposes a point where the value of the acquisition function is largest in the low-dimensional search space S t , and sets that point as a proposal point x Nt−1 . The proposal point x Nt−1  is represented by the formula (15) set forth below. a t (x|E t ) is an acquisition function defined from a surrogate model based on the extracted data E t . 
     
       
         
           
             
               
                 
                   
                     x 
                     
                       N 
                       
                         t 
                         - 
                         1 
                       
                     
                   
                   = 
                   
                     
                       argmax 
                       
                         x 
                         ∈ 
                         
                           S 
                           t 
                         
                       
                     
                     ⁢ 
                     
                       
                         a 
                         t 
                       
                       ( 
                       
                         x 
                         ❘ 
                         
                           E 
                           t 
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
           
         
       
     
     For example, a GP regression model, a random forest model or the like is adopted as the surrogate model. As the acquisition function a t , for example, Lower Confidence Bound (LCB), Expected Improvement (EI), Probability of Improvement (PI), Mutual Information (MI), Predictive Entropy Search (PES), Max-value Entropy Search (MES) or the like is adopted. 
     The point at which the value of the acquisition function is largest in the low-dimensional search space S t  can be obtained, for example, by setting a plurality of points in S t  and selecting a point at which the value of the acquisition function a t  is largest from among those points. Alternatively, such a point can be obtained by using an optimization method, such as the L-BFGS method. 
     After S 204  is performed, the observation apparatus  200  executes the observation process (S 205 ). In S 205  at the time t, the observation apparatus  200  acquires a proposal point x Nt−1  from the proposal unit  104  via the network or the like, and observes an observation value y Nt−1 , based on the proposal point x Nt−1 . The observation value y Nt−1  is supplied to the parameter vector value proposal apparatus  100  via the network. 
     The observation value y Nt−1  is an observation value of the objective function f with respect to the proposal point x Nt−1 . As shown in S 309  of  FIG.  3   , the observation value y Nt−1  is acquired by the storage unit  101 . The observation value y Nt−1  is expressed by the formula (16) set forth below. ε Nt−1  represents a noise component that is included in the observation value y Nt−1  at the time t. 
         y   N     t−1     =f ( x   N     t−1   )+ε N     t−1      (16)
 
     After S 205  is performed, the storage unit  101  executes the update process (S 206 ). In S 206  at the time t, the storage unit  101  stores observation data D t  in which the pair consisting of the observation point x Nt−1  supplied from the proposal unit  104  and the observation value y Nt−1  supplied from the observation apparatus  200  are added to D t−1 . As shown in S 310  of  FIG.  3   , the observation data Dt is represented by the formula (17) set forth below. ∪ represents a union of two sets. 
         D   t   =D   t−1 ∪{( x   N     t−1     , y   N     t−1   )}  (17)
 
     The addition of this pair increases the number of elements in the observation data by one. Therefore, with respect to the number N t  of pairs stored in the storage unit  101  at the time t and the number N t−1  of pairs stored in the storage unit  101  at the time t−1, the following formula (18) is established, as shown in S 311  of  FIG.  3   . 
         N   t   =N   t−1 +1   (18)
 
     After S 206  is performed, the control unit  105  executes the determination process (S 207 ). In S 207  at the time t, the control unit  105  determines whether or not the processes from S 202  to S 206  are repeated a predetermined number of times T. Where the time t is less than T (S 207 : NO), the control unit  105  increments the time t and returns to S 202 . The processes from S 202  to S 207  are repeated until the time t reaches T, as in the “for statements” of S 303  and S 312  in  FIG.  3   . 
     Where the time t reaches T (S 207 : YES), the control unit  105  executes the output process (S 208 ). The time in S 208  is T. In S 207  at the time T, the control unit  105  selects an observation point corresponding to the smallest observation value in the observation data D T  at the time T and outputs that observation point to an external device of the parameter vector value proposal apparatus  100  as an optimum point. The index b T  of the smallest observation value in the D T  is represented by the following formula (19), as shown in S 313  of  FIG.  3   . 
     
       
         
           
             
               
                 
                   
                     b 
                     T 
                   
                   = 
                   
                     
                       argmin 
                       
                         
                           n 
                           = 
                           0 
                         
                         , 
                         1 
                         , 
                         … 
                             
                         , 
                         
                           N 
                           
                             T 
                             - 
                             1 
                           
                         
                       
                     
                     ⁢ 
                     
                       y 
                       n 
                     
                   
                 
               
               
                 
                   ( 
                   19 
                   ) 
                 
               
             
           
         
       
     
     As shown in S 314  of  FIG.  3   , the optimum point to be output to the external device of the parameter vector value proposal apparatus  100  is an observation point x Nt  corresponding to the smallest observation value y bt  in the set D T . 
     After S 208  is performed, the parameter optimization process by the parameter optimization system  1  ends. 
     A description will be given of the advantages of the present embodiment. 
     As a preparation for this, a description will be given as to how GP regression is utilized in the standard Bayesian optimization method and in the method of Non-Patent Document 1. After the observation data D t−1  is utilized and GP regression of the objective function f is performed at a point x, an expected value E of a predicted value is expressed by the formula (20) set forth below. ⋅ T  represents a transpose of a vector or a matrix. K is a matrix of N t−1  rows and N t−1  columns, and its elements K [r,c]  (r, c=0, 1, . . . , N t−1 −1) are expressed as k(x r ,x c ). ⋅[r,c] represents an element of the r-th row and c-th column of the matrix. a represents a standard deviation of the noise component. I represents an identity matrix of N t−1  rows and N t−1  columns. ⋅ −1  represents an inverse matrix of the matrix. y=(y 0 , y 1 , . . . , y Nt−1 −1) T . 
         E [ f ( x )| x, D   t−1 ]=( K+σ   2   I ) −1   y    (20)
 
         k =( k ( x, x   0 ),  k ( x, x   1 ), . . . ,  k ( x, x   N     t−1     −1 )) T    
     After the observation data Dt−1 is utilized and the GP regression of the objective function f at the point x is performed, a variance V of a predicted value is represented by the following formula (21). 
         V [ f ( x )| x, D   t−1 ]= k ( x,x )−k T ( K+σ   2   I ) −1   k    (21)
 
     For example, where LCB is adopted as an acquisition function a t , a t  is expressed by the formula (22) set forth below. κ is a parameter that determines the balance between exploration and exploitation. 
         a   t ( x|D   t−1 )=− E [ f ( x )| x, D   t−1 ]+κ V [ f ( x )| x, D   t−1 ]  (22)
 
     As described above, in the method of Non-Patent Document 1, the acquisition function used to determine a proposal point is defined based on GP regression. Even where an acquisition function other than LCB is adopted as the acquisition function a t , the acquisition function used to determine a proposal point is defined based on GP regression. 
     Even in the method of Non-Patent Document 1, the mathematical formulas related to the acquisition function are the same as those of the standard Bayesian optimization method as long as the types of acquisition functions to be adopted are the same. The Bayesian optimization method of Non-Patent Document 1 differs from the standard Bayesian optimization method in that the range in which the acquisition function a t  obtains a maximum point is not the D-dimensional space but the one-dimensional search space. 
     An expected value E of the predicted value can be transformed as shown in the formula (23) set forth below. ((K+σ 2 I) −1 y) [n]  is a constant determined from the observation data D t−1 , and k(x,x n ) depends on the point x. 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           E 
                           [ 
                           
                             
                               
                                 f 
                                 ⁡ 
                                 ( 
                                 x 
                                 ) 
                               
                               ❘ 
                               x 
                             
                             , 
                             
                               D 
                               
                                 t 
                                 - 
                                 1 
                               
                             
                           
                           ] 
                         
                         = 
                           
                         
                           
                             
                               
                                 k 
                                 T 
                               
                               ( 
                               
                                 K 
                                 + 
                                 
                                   
                                     σ 
                                     2 
                                   
                                   ⁢ 
                                   I 
                                 
                               
                               ) 
                             
                             
                               - 
                               1 
                             
                           
                           ⁢ 
                           y 
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         
                           
                             ∑ 
                             
                               n 
                               = 
                               0 
                             
                             
                               
                                 N 
                                 
                                   t 
                                   - 
                                   1 
                                 
                               
                               - 
                               1 
                             
                           
                           
                             
                               k 
                               ⁡ 
                               ( 
                               
                                 x 
                                 , 
                                 
                                   x 
                                   n 
                                 
                               
                               ) 
                             
                             ⁢ 
                             
                               
                                 ( 
                                 
                                   
                                     
                                       ( 
                                       
                                         K 
                                         + 
                                         
                                           
                                             σ 
                                             2 
                                           
                                           ⁢ 
                                           I 
                                         
                                       
                                       ) 
                                     
                                     
                                       - 
                                       1 
                                     
                                   
                                   ⁢ 
                                   y 
                                 
                                 ) 
                               
                               
                                 [ 
                                 n 
                                 ] 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   23 
                   ) 
                 
               
             
           
         
       
     
     If k(x,x n ) shown in formula (23) is interpreted as a weight of the constant ((K+σ 2 I) −1 y) [n] , it can be seen that the observation point x n  at which the absolute value of k(x,x n ) is small does not have a high degree of contribution to the expected value E. Since k(x,x n ) is a similarity and does not take a negative value, the contribution of the predicted value to the expected value E is small at the observation point x n  having a low similarity k(x,x n ). Further, at the observation point x n  having a low similarity k(x,x n ), the contribution to the variance V shown in the formula (21) is also small. 
     In the present embodiment, the points at which the value of the acquisition function have to be calculated are limited to the points in the low-dimensional search space S t . Therefore, an observation point x n  having a low similarity k(x′,x n ) to a point x′ included in the low-dimensional search space S t  does not much contribute to the expected value E of the predicted value, the variance V of the predicted value, or the acquisition function a t . 
     The extracted data E t  of the present embodiment is obtained by extracting a pair corresponding to x n  having a similarity k (x′,x n ) of T t  or more with respect to a predetermined point x′ from the observation data D t−1 . The extracted data E t  is represented by the following formula (24). 
         E   t ={( {tilde over (x)}   n   ′, {tilde over (y)}   n ′)| n′= 0,1, . . . ,  N′   t −1}  (24)
 
       ( {tilde over (x)}   n   ′,{tilde over (y)}   n ′): Nt ′ elements of Et,  n′= 0,1, . . . ,  N′   t−1 −1
 
     Therefore, the extracted data E t  is a set of pairs corresponding to the observation points having a large contribution of the expected value E of the predicted value, the variance V of the predicted value, and the acquisition function a t . 
     In the present embodiment, the expected value E of the predicted value, the variance V of the predicted value, and the acquisition function a t  are represented by the following formulas (25), (26) and (27), respectively. 
     
       
         
           
             
               
                 
                   
                     
                       
                         E 
                         [ 
                         
                           
                             
                               f 
                               ⁡ 
                               ( 
                               x 
                               ) 
                             
                             ❘ 
                             x 
                           
                           , 
                           
                             
                               D 
                               
                                 t 
                                 - 
                                 1 
                               
                             
                             ≈ 
                               
                             
                               E 
                               [ 
                               
                                 
                                   
                                     f 
                                     ⁡ 
                                     ( 
                                     x 
                                     ) 
                                   
                                   ❘ 
                                   x 
                                 
                                 , 
                                 
                                   E 
                                   t 
                                 
                               
                               ] 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         
                           
                             ∑ 
                             
                               
                                 n 
                                 ′ 
                               
                               = 
                               0 
                             
                             
                               
                                 N 
                                 t 
                                 ′ 
                               
                               - 
                               1 
                             
                           
                           
                             
                               k 
                               ⁡ 
                               ( 
                               
                                 x 
                                 , 
                                 
                                   
                                     x 
                                     ~ 
                                   
                                   
                                     n 
                                     ′ 
                                   
                                 
                               
                               ) 
                             
                             ⁢ 
                             
                               
                                 ( 
                                 
                                   
                                     
                                       ( 
                                       
                                         
                                           K 
                                           ~ 
                                         
                                         + 
                                         
                                           
                                             σ 
                                             2 
                                           
                                           ⁢ 
                                           
                                             I 
                                             ~ 
                                           
                                         
                                       
                                       ) 
                                     
                                     
                                       - 
                                       1 
                                     
                                   
                                   ⁢ 
                                   
                                     y 
                                     ~ 
                                   
                                 
                                 ) 
                               
                               
                                 [ 
                                 
                                   n 
                                   ′ 
                                 
                                 ] 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         
                           
                             
                               
                                 
                                   k 
                                   ~ 
                                 
                                 T 
                               
                               ( 
                               
                                 
                                   K 
                                   ~ 
                                 
                                 + 
                                 
                                   
                                     σ 
                                     2 
                                   
                                   ⁢ 
                                   
                                     I 
                                     ~ 
                                   
                                 
                               
                               ) 
                             
                             
                               - 
                               1 
                             
                           
                           ⁢ 
                           
                             y 
                             ~ 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   25 
                   ) 
                 
               
             
           
         
       
       
         
           
             
               
                 
                   
                     
                       
                         
                           V 
                           [ 
                           
                             
                               
                                 f 
                                 ⁡ 
                                 ( 
                                 x 
                                 ) 
                               
                               ❘ 
                               x 
                             
                             , 
                             
                               D 
                               
                                 t 
                                 - 
                                 1 
                               
                             
                           
                           ] 
                         
                         ≈ 
                           
                         
                           V 
                           [ 
                           
                             
                               
                                 f 
                                 ⁡ 
                                 ( 
                                 x 
                                 ) 
                               
                               ❘ 
                               x 
                             
                             , 
                             
                               E 
                               t 
                             
                           
                           ] 
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         
                           
                             k 
                             ⁡ 
                             ( 
                             
                               x 
                               , 
                               x 
                             
                             ) 
                           
                           - 
                           
                             
                               
                                 
                                   
                                     k 
                                     ~ 
                                   
                                   T 
                                 
                                 ( 
                                 
                                   
                                     K 
                                     ~ 
                                   
                                   + 
                                   
                                     
                                       σ 
                                       2 
                                     
                                     ⁢ 
                                     
                                       I 
                                       ~ 
                                     
                                   
                                 
                                 ) 
                               
                               
                                 - 
                                 1 
                               
                             
                             ⁢ 
                             
                               k 
                               ~ 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   26 
                   ) 
                 
               
             
           
         
       
       
         
           
             
               
                 
                   
                     
                       a 
                       t 
                     
                     ( 
                     
                       x 
                       ❘ 
                       
                         D 
                         
                           t 
                           - 
                           1 
                         
                       
                     
                     ) 
                   
                   ≈ 
                   
                     
                       a 
                       t 
                     
                     ( 
                     
                       x 
                       ❘ 
                       
                         E 
                         t 
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   27 
                   ) 
                 
               
             
           
         
       
         
         {tilde over (K)} is a matrix of N t ′ rows and N t ′ columns, {tilde over (K)} [r,c] =k({tilde over (x)} r ,{tilde over (x)} c ) 
         Ĩ is an identity matrix of N t ′ rows and Mt′ columns. 
       
    
         {tilde over (y)} =( {tilde over (y)}   0   , {tilde over (y)}   1   , . . . , {tilde over (y)}   N′     t     −1 ) T    
         {tilde over (k)} =( k ( x,{tilde over (x)}   0 ),  k ( x,{tilde over (x)}   1 ), . . . ,  k ( x,{tilde over (x)}   N′     d     −1 )) T    
     For example, where LCB is adopted as the acquisition function, the acquisition function a t  is expressed by the following formula (28). 
         a   t ( x|E   t )=− E [ f ( x )| x, E   t ]+κ V [ f ( x )| x, E   t ]  (28)
 
     Even where an acquisition function other than LCB is adopted, the acquisition function a t  used to determine a proposal point is defined based on the expected value E and the variance V in a prediction period. 
     As described above, in the present embodiment, the expected value E of the predicted value, the variance V of the predicted value and the acquisition function a t  are approximated using the extracted data E t  including pairs that correspond to the observation points x n  having a high similarity k(x,x n ) and a high degree of contribution. Since the approximation is performed by utilizing such extracted data E t , the accuracy of approximation is high and the deterioration due to the approximation is small. 
     In the method of Patent Document 1, the expected value E of the predicted value, the variance V of the predicted value, and the acquisition function a t  are respectively approximated by the formulas (29), (30) and (31) set forth below. Here, Ft={(x n ,y n )|dist(S t ,x n )≤A, n=0, 1, . . . , N t−1 −1}, dist (S,x) is a function that calculates the distance between space S and point x. “A” represents a threshold value regarding a distance. 
         E [ f ( x )| x, D   t−1 ]≈ E [ f ( x )| x, F   t ]  (29)
 
         V [ f ( x )| x, D   t−1 ]≈ V [ f ( x )| x, F   t ]  (30)
 
         a   t ( x|D   t−1 )≈ a   t ( x|F   t )   (31)
 
       where,  F   t {( x   n   ,y   n )|dist( S   t   ,x   n )≤ A, n= 0,1, . . . ,  N   t−1 −1}
 
     The short distance dist(S t ,x n ) between the space S t  and the point x n  and the high similarity k(x,x n ) between the point x (∈S t ) and the point x n  do not always match. Therefore, Ft is not limited to data on the pairs corresponding to observation points xn having a high degree of contribution, and the method of Patent Document 1 may undergo certain deterioration due to approximation, and the approximation accuracy is not necessarily high. Therefore, the method of Patent Document 1 does not always have satisfactory search efficiency. 
     Since the observation data D t−1  is used in the method of Non-Patent Document 1, the calculation order of (K+σ 2 I) −1  depends on the number of elements N t−1  of D t−1  and is O(N t−1   3 ). On the other hand, in the present embodiment, the extracted data E t−1  is used, so that the calculation order of (K ˜ +σ 2 I ˜ ) −1  depends on the number of elements N t ′ of E t  and is O (N t ′ 3 ). From 1≤N t ′≤N t−1 , the calculation cost of an inverse matrix in the present embodiment is equal to or less than that of the method of Non-Patent Document 1. Depending upon the value of T t , N t ′&lt;N t−1 . In this case, the calculation cost of an inverse matrix in the present embodiment is lower than that of the method of Non-Patent Document 1. 
     As described above, in the present embodiment, the expected value and variance of a predicted value and an acquisition function are approximated with high accuracy, and the calculation cost of an inverse matrix in GP regression is low. According to this embodiment, therefore, the calculation cost of an inverse matrix in GP regression can be reduced as much as possible without much deterioration in the search efficiency of a parameter vector value. 
     Even though the present embodiment enables the calculation cost of an inverse matrix in GP regression to be reduced as much as possible without deterioration in the search efficiency of a parameter vector value, the advantages of the present embodiment are not limited to this. In some cases, the search efficiency of parameter optimization can be improved. 
       FIG.  4    is a diagram illustrating a state in which the value of an objective function is observed at seven observation points in the D-dimensional space of the case where D=2. In the graph  41  on the left side of  FIG.  4   , the horizontal axis corresponds to the 0th element of a D-dimensional parameter vector, and the vertical axis corresponds to the 1st element. The axis of the depth direction corresponds to the value of an objective function. Each of the seven points represents the position of an observation point in the D-dimensional space. The broken line represents low-dimensional search space S t . The shade of the ellipses represents the value of an unknown objective function f. In this shade, black indicates that the value of an objective function is small, and white indicates that the value of an objective function is large. 
     In the graph  42  on the right side of  FIG.  4   , the horizontal axis represents a distance ∥x n −x′∥ to a predetermined point x′(∈S t ) at each observation point x n  (n=0, 1, . . . , 6), and the vertical axis represents a similarity k(x n ,x′) between x n  and x′. The solid curve represents a squared exponential kernel function with a small length scale, and the broken-line curve represents a squared exponential kernel function with a large length scale. 
     As shown in  FIG.  4   , where the squared exponential kernel function with a large length scale is used, the degrees of similarity at the observation points x n  are relatively uniform, and where the squared exponential kernel function with a small length scale is used, the degrees of similarity depend on the observation points x n  and are significantly different. 
     Since the objective function f in  FIG.  4    takes a small value locally, an observation point x n  located at a position farther from the low-dimensional search space S t  than the local solution is not useful for predicting a value of an objective function for a point in S t . In the example of  FIG.  4   , therefore, it is preferable that the length scale of the squared exponential kernel function is small. 
     As described above, as the hyperparameter of a kernel function, a predetermined value is adopted, or a value estimated from observation data or from extracted data described later is adopted. Therefore, an optimum value is not always adopted in correspondence to the shape of an objective function. 
     Where the length scale is larger than an optimum value, the prediction accuracy of GP regression is low, and the search efficiency of parameter optimization is poor. On the other hand, in the present embodiment, only extracted data E t  of observation data D t−1  is utilized for GP regression, and observation points having low degrees of similarity are not used, that is, the degrees of similarity to such observation points are forcibly replaced with 0. Therefore, the behavior of GP regression becomes similar to the behavior of the case where the length scale is reduced and an optimum length scale is adopted. As a result, there is a case where the search efficiency of parameter optimization is improved more where only the extracted data E t  is used than where the observation data D t−1  is used. 
     As described above, in the present embodiment, it may be possible to achieve both improvement in the search efficiency of a parameter vector value and reduction in the calculation cost of an inverse matrix in GP regression. This advantage is not limited to the case where the objective function f has a large number of local solutions. The advantage is achieved where the length scale is large compared to the optimal value. 
     &lt;Modification 1&gt; 
     The extraction unit  103  according to modification 1 refers to one or more points in the D-dimensional space represented by one or more parameter vector values included in the observation data stored in the storage unit  101 , and extracts, as extracted data, a set of pairs corresponding to one more points at which degrees of similarity to a point included in the low-dimensional search space are within a predetermined percentage in descending order. Modification 1 will be described in detail below. 
     Observation points x n  (n=0, 1, . . . , N t−1 −1) are rearranged such that degrees of similarity k(x n ,x′) to a predetermined point x′ are arranged in descending order, and the rearranged observation points are represented by x″ n  (n=0, 1, . . . , N t−1 −1) and the corresponding observation values are represented by y″ n . The extraction unit  103  may extract extracted data E t  represented by the formula (32) from D t−1 . It should be noted that r t  represents a percentage and takes a value that is not less than 1/N t−1  and not more than 1. Where r t  is 1, E t  is equal to D t−1 . floor(⋅) is a function with which to obtain the largest integer that is not more than an argument. 
         E   t ={( x″   n   ,y″   n )| n= 0,1, . . . , floor( r   t   N   t−1 )−1}  (32)
 
     E t  of the present embodiment and {(x n ,y n )|k(x n ,x′)≥T t , n=0, 1, . . . , N t−1 −1} shown in the present embodiment become equivalent, depending upon how r t  and T t  are set. In this modification, the number of elements N t ′ of E t  can be directly controlled by r t , as shown in the following formula (33). 
         N   t ′=floor( r   t   N   t−1 )   (33)
 
     Since the calculation cost of an inverse matrix of GP regression depends on N t ′, this modification is advantageous in that the calculation cost can be controlled. 
     The calculation cost of an inverse matrix increases sharply as N t ′ is large, while the calculation cost of the inverse matrix does not become a practical problem as long as N t ′ is small. Therefore, it is preferable to set r t  to 1 while the time t is small and the number of elements N t−1  of D t−1  is small. If the time t is large and the calculation cost of an inverse matrix becomes too high by making E t  equal to D t−1  and making N t ′ equal to N t−1 , then it is preferable to set r t  to be smaller than 1 and set the calculation time to be within a desired time. As a result, the calculation cost of an inverse matrix can be suppressed with almost no deterioration in the search efficiency of parameter optimization. 
     In the present embodiment, where a predetermined point x′ is defined as a certain point in the low-dimensional search space S t , the following formula (34) holds. 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           E 
                           t 
                         
                         = 
                           
                         
                           { 
                           
                             
                               
                                 ( 
                                 
                                   
                                     x 
                                     n 
                                   
                                   , 
                                   
                                     y 
                                     n 
                                   
                                 
                                 ) 
                               
                               ❘ 
                               
                                 
                                   
                                       
                                     ∃ 
                                   
                                   
                                     x 
                                     ′ 
                                   
                                 
                                 ∈ 
                                 
                                   S 
                                   t 
                                 
                               
                             
                             , 
                             
                               
                                 k 
                                 ⁡ 
                                 ( 
                                 
                                   
                                     x 
                                     n 
                                   
                                   , 
                                   
                                     x 
                                     ′ 
                                   
                                 
                                 ) 
                               
                               ≥ 
                               
                                 T 
                                 t 
                               
                             
                             , 
                             
                               n 
                               = 
                               0 
                             
                             , 
                             1 
                             , 
                             … 
                                 
                             , 
                             
                               
                                 N 
                                 
                                   t 
                                   - 
                                   1 
                                 
                               
                               - 
                               1 
                             
                           
                           } 
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         
                           { 
                           
                             
                               
                                 ( 
                                 
                                   
                                     x 
                                     n 
                                   
                                   , 
                                   
                                     y 
                                     n 
                                   
                                 
                                 ) 
                               
                               ❘ 
                               
                                 
                                   
                                     max 
                                     
                                       
                                         x 
                                         ′ 
                                       
                                       ∈ 
                                       
                                         S 
                                         t 
                                       
                                     
                                   
                                   
                                     k 
                                     ⁡ 
                                     ( 
                                     
                                       
                                         x 
                                         n 
                                       
                                       , 
                                       
                                         x 
                                         ′ 
                                       
                                     
                                     ) 
                                   
                                 
                                 ≥ 
                                 
                                   T 
                                   t 
                                 
                               
                             
                             , 
                             
                               n 
                               = 
                               0 
                             
                             , 
                             1 
                             , 
                             … 
                                 
                             , 
                             
                               
                                 N 
                                 
                                   t 
                                   - 
                                   1 
                                 
                               
                               - 
                               1 
                             
                           
                           } 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   34 
                   ) 
                 
               
             
           
         
       
     
     In this case, the maximum degrees of similarity maxk(x n ,x′) shown in the formula (34) and rearranged in descending order are represented by x″ n  (n=0, 1, . . . , N t−1 −1) and the corresponding observation values are represented by y″ n . The extraction unit  103  may extract extracted data E t  represented by the formula (35) from D t−1 . 
         E   t ={( x″   n   ,y″   n )| n= 0,1, . . . , floor( r   t   N   t−1 )−1}  (35)
 
     E t  of the formula (35) and E t  of the formula (34) are equivalent, depending upon how r t  and T t  are set. In this modification, the number of elements N t ′ of E t  can be directly controlled by r t , as shown in the following formula (36). 
         N′   t =floor( r   t   N   t−1 )   (36)
 
     Since the calculation cost of an inverse matrix of GP regression depends on N t ′, this modification is advantageous in that the calculation cost can be controlled. By controlling r t  as above, the calculation cost of an inverse matrix can be suppressed with almost no deterioration in the search efficiency of parameter optimization. 
     &lt;Modification 2&gt; 
     The proposal unit  104  according to modification 2 calculates a similarity between two points in the D-dimensional space, from components of orthogonal complement space of linear subspace accompanying R-dimensional affine subspace, which is low-dimensional search space included in the D-dimensional space. Modification 2 will be described in detail below. 
     In the present embodiment, extracted data E t  is represented by the following formula (37). 
         E   t ={( x   n   ,y   n )| k ( x   n   ,P   S     t   ( x   n ))≥ T   t   , n= 0,1, . . . ,  N   t−1 −1}  (37)
 
     For example, where the kernel function is a squared exponential kernel function, the formula (38) set forth below holds from the definition of the function P St . (I D −P Ut ) is an orthographic projection matrix projected onto the orthogonal complement space U t   ⊥  of the R t -dimensional linear subspace U t  accompanying S t . 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           k 
                           ⁡ 
                           ( 
                           
                             
                               x 
                               n 
                             
                             , 
                             
                               
                                 P 
                                 
                                   S 
                                   t 
                                 
                               
                               ( 
                               
                                 x 
                                 n 
                               
                               ) 
                             
                           
                           ) 
                         
                         = 
                           
                         
                           
                             θ 
                             σ 
                             2 
                           
                           ⁢ 
                           
                             exp 
                             ⁡ 
                             ( 
                             
                               
                                 - 
                                 
                                   1 
                                   2 
                                 
                               
                               ⁢ 
                               
                                 
                                   
                                      
                                     
                                       
                                         x 
                                         n 
                                       
                                       - 
                                       
                                         
                                           P 
                                           
                                             S 
                                             t 
                                           
                                         
                                         ( 
                                         
                                           x 
                                           n 
                                         
                                         ) 
                                       
                                     
                                      
                                   
                                   2 
                                 
                                 
                                   θ 
                                   l 
                                   2 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         
                           
                             θ 
                             σ 
                             2 
                           
                           ⁢ 
                           
                             exp 
                             ⁡ 
                             ( 
                             
                               
                                 - 
                                 
                                   1 
                                   2 
                                 
                               
                               ⁢ 
                               
                                 
                                   
                                      
                                     
                                       
                                         ( 
                                         
                                           
                                             I 
                                             D 
                                           
                                           - 
                                           
                                             P 
                                             
                                               U 
                                               t 
                                             
                                           
                                         
                                         ) 
                                       
                                       ⁢ 
                                       
                                         ( 
                                         
                                           
                                             x 
                                             n 
                                           
                                           - 
                                           
                                             x 
                                             
                                               b 
                                               
                                                 t 
                                                 - 
                                                 1 
                                               
                                             
                                           
                                         
                                         ) 
                                       
                                     
                                      
                                   
                                   2 
                                 
                                 
                                   θ 
                                   l 
                                   2 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   38 
                   ) 
                 
               
             
           
         
       
     
     Any point x in the D-dimensional space is represented by the formula (39) set forth below. Specifically, any point x in the D-dimensional space can be decomposed into a component of the first term on the right side of the formula (39) and a component of the second term on the right side thereof. The former is referred to as the U t  component of the point x, and the latter is referred to as the U t   ⊥  component of the point x. (I D −P Ut ) (x n −x bt−1 ) is a U t   ⊥  component of the difference vector (x n −x bt−1 ) between the observation point x n  and the best observation point x bt−1 , and does not have U t  component. 
         x=P   U     t     x +( I   D   −P   U     t   ) x    (39)
 
     Where all of R t  vectors along the R t  coordinate axes in the D-dimensional space are elements of an R t -dimensional linear subspace U t , (I D −P Ut ) is a diagonal matrix. Of the diagonal components of the diagonal matrix, R t  components corresponding to R t  coordinate axes are 0, and the remaining (D−R t ) components are 1. The R t  components correspond to U t  components, and the remaining (D−R t ) components correspond to U t   ⊥  components. Therefore, (I D −P Ut ) (x n −x bt−1 ) can be calculated by referring to only the (D−R t ) components corresponding to the U t   ⊥  components of x n  and x bt−1 . 
     This property is utilized in the present modification, and U t  is changed in accordance with the time t under the constraint that all R t  vectors along the R t  coordinate axes in the D-dimensional space are elements of the R t -dimensional linear subspace U t , k(x n ,P St (x n )) is calculated by referring to only the (D−R t ) components corresponding to the U t   ⊥  components, and extracted data E t  is extracted. Since the values of the U t  components need not be referred to, the calculation cost can be reduced. 
     &lt;Modification 3&gt; 
     In the present embodiment, as shown in the formula (40) set forth below, the extraction unit  103  extracts extracted data E t  on the condition that the similarity k(x n ,x′) is a predetermined value Tt or more. 
         E   t ={( x   n   ,y   n )| k ( x   n   ,x ′)≥ T   t   , n= 0,1, . . . ,  N   t−1 −1}  (40)
 
     The extraction unit  103  according to modification 3 extracts the extracted data E t , based on another condition. Where the kernel function is a squared exponential kernel function, the fact that k(x n ,x′)≥T t  holds is equivalent to the fact that the following formula (41) holds. 
     
       
         
           
             
               
                 
                   
                     
                       θ 
                       σ 
                       2 
                     
                     ⁢ 
                     
                       exp 
                       ⁡ 
                       ( 
                       
                         
                           - 
                           
                             1 
                             2 
                           
                         
                         ⁢ 
                         
                           
                             
                                
                               
                                 
                                   x 
                                   n 
                                 
                                 - 
                                 
                                   x 
                                   ′ 
                                 
                               
                                
                             
                             2 
                           
                           
                             θ 
                             l 
                             2 
                           
                         
                       
                       ) 
                     
                   
                   ≥ 
                   
                     T 
                     t 
                   
                 
               
               
                 
                   ( 
                   41 
                   ) 
                 
               
             
           
         
       
     
     Assuming that T t ≤θσ 2 , the fact that k(x n ,x′)≥Tt holds is equivalent to the fact that the following formula (42) holds for the distance ∥x n −x′∥. 
     
       
         
           
             
               
                 
                   
                     
                        
                       
                         
                           x 
                           n 
                         
                         - 
                         
                           x 
                           ′ 
                         
                       
                        
                     
                     ≤ 
                     
                       
                         T 
                         t 
                         ′ 
                       
                       ⁢ 
                       
                         θ 
                         l 
                       
                     
                   
                   ⁢ 
                   
 
                   
                     
                       T 
                       t 
                       ′ 
                     
                     = 
                     
                       
                         
                           - 
                           2 
                         
                         ⁢ 
                         
                           log 
                           e 
                         
                         ⁢ 
                         
                           
                             T 
                             t 
                           
                           
                             θ 
                             σ 
                             2 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   42 
                   ) 
                 
               
             
           
         
       
     
     The extraction unit  103  according to modification 3 extracts extracted data E t  on the condition that the distance ∥x n −x′∥ is T t ′-fold of the length scale θl or less. Therefore, the following formula (43) holds for E t . 
         E   t ={( x   n   ,y   n )|∥ x   n   −x′∥≤T′   t θ l   , n= 0,1, . . . ,  N   t−1 −1}  (43)
 
     The extracted data E t  of modification 3 is the same extracted data as extracted on the condition that the similarity k(x n ,x′) is equal to or higher than a predetermined value T t . Therefore, advantages similar to those of the present embodiment can be obtained. 
     From the definition of T t ′ shown in the formula (42), the user is only required to determine T t  as T t ′, and an adaptive value corresponding to the hyperparameter θ σ  of the kernel function is automatically set. The threshold value T t ′θ l  for the distance ∥x n −x′∥ is an adaptive value in correspondence to the hyperparameter θ l  of the kernel function. Therefore, the threshold value T t ′θ l  is adaptively set for the distance ∥x n −x′∥ in accordance with the hyperparameters θ l  and θ σ  of the kernel function. 
     T t ′ is not limited to that shown in the formula (42). In this case, there is no guarantee that the extracted data is the same as that of the present embodiment, and T t ′ does not depend on the signal standard deviation θ σ . In this case, the calculation of logarithm and square root is unnecessary, and the calculation cost is reduced, accordingly. Even in this case, a set of pairs having a high similarity k(x n ,x′) are extracted as extracted data E t . 
     Where x′=P St (x n ), U t  is changed in accordance with the time t under the constraint that all R t  vectors along the R t  coordinate axes in the D-dimensional space are elements of the R t -dimensional linear subspace U t , and ∥x n −x′∥ may be calculated by referring to only the (D−R t ) components corresponding to the U t   ⊥  components. Since the values of the U t  components need not be referred to, the calculation cost can be reduced. 
     Modification 3 was described referring to the case where the kernel function is a squared exponential kernel function. Even if the kernel function is not a squared exponential kernel function, it is only required to have a length scale as a hyperparameter. In this case, the extraction unit  103  may refer to observation points {x n |n=0, 1, . . . , N t−1 −1)} included in the observation data D t−1  stored in the storage unit  101 , and extract, as extracted data E t , a set of pairs corresponding to one or more observation points at which the distance ∥x n −x′∥ to a predetermined point x′ included in the low-dimensional search space S t  is a coefficient multiple of the length scale θl or less. In this case, there is no guarantee that the extracted data is the same as that of the present embodiment, but a set of pairs corresponding to the observation points x n  at which degrees of similarity k(x n ,x′) are high are extracted as the extracted data E t . 
     &lt;Modification 4&gt; 
     Where the kernel function has a length scale as a hyperparameter, the extraction unit  103  according to modification 4 refers to one or more points in the D-dimensional space represented by one or more parameter vector values included in the observation data stored in the storage unit  101 , and extracts, as extracted data, a set of pairs corresponding to one or more points at which all D distances in the coordinate axis directions of the D-dimensional space to a point included in the low-dimensional search space are a coefficient multiple of the length scale or less. Specifically, the extraction unit  103  may extract extracted data E t  on the basis that the absolute value of the d-th component difference between the point x n  and the point x′ is T t ″-fold of the length scale θ l  or less for all values of d (=0, 1, . . . , D−1). It should be noted that T t ″ is a coefficient set by the user. In this case, E t  is expressed by the following formula (44). 
         E   t ={( x   n   ,y   n )| ∀   d  ∈ {0,1, . . . ,  D− 1}.|( x   n ) [d] −( x ′) [d]   |≤T″   t θ l   , n= 0,1, . . . ,  N   t−1 −1}  (44)
 
     As can be seen from the formula (44), for the distance |(x n ) [d] −(x′) [d] | in each coordinate axis direction d (=0, 1, . . . , D−1) in the D-dimensional space, an adaptive threshold is set in accordance with the hyperparameters of the kernel function. Modification 4 is not equivalent to modification 3 but is an approximation thereto. Therefore, advantages similar to those of modification 3 can be obtained. 
     Where x′=P St (x n ), U t  is changed in accordance with the time t under the constraint that all R t  vectors along the R t  coordinate axes in the D-dimensional space are elements of the R t -dimensional linear subspace U t , and extracted data E t  may be extracted on the basis that the absolute value of the d-th component difference between the point x n  and the point x′ is than T t ″-fold of the length scale θ l  or less for all (D−R t ) values of d corresponding to the U t   ⊥  components. Since the values of the U t  components need not be referred to, the calculation cost can be reduced. 
     &lt;Modification 5&gt; 
     Where a kernel function for calculating a similarity has a length scale vector as a hyperparameter, the extraction unit  103  according to modification 5 refers to one or more points in the D-dimensional space represented by one or more parameter vector values included in the observation data stored in the storage unit  101  and extracts, as extracted data, a set of pairs corresponding to one or more points at which the square of a normalized Euclidean distance to a point included in the low-dimensional search space is a predetermined value or less. In the calculation of the square of the normalized Euclidean distance, the extraction unit  103  adopts the value of each element of the length scale vector as the standard deviation corresponding to each coordinate axis direction of the D-dimensional space. Modification 5 will be described in detail below. 
     Where the kernel function is an ARD squared exponential kernel function, the fact that k(x n ,x′)≥T t  holds is equivalent to the fact that the following formula (45) holds. 
     
       
         
           
             
               
                 
                   
                     
                       θ 
                       σ 
                       2 
                     
                     ⁢ 
                     
                       exp 
                       ⁡ 
                       ( 
                       
                         
                           - 
                           
                             1 
                             2 
                           
                         
                         ⁢ 
                         
                           
                             ∑ 
                             
                               d 
                               = 
                               0 
                             
                             
                               D 
                               - 
                               1 
                             
                           
                           
                             
                               
                                 ( 
                                 
                                   
                                     
                                       ( 
                                       
                                         x 
                                         n 
                                       
                                       ) 
                                     
                                     
                                       [ 
                                       d 
                                       ] 
                                     
                                   
                                   - 
                                   
                                     
                                       ( 
                                       
                                         x 
                                         ′ 
                                       
                                       ) 
                                     
                                     
                                       [ 
                                       d 
                                       ] 
                                     
                                   
                                 
                                 ) 
                               
                               2 
                             
                             
                               
                                 ( 
                                 
                                   θ 
                                   l 
                                 
                                 ) 
                               
                               
                                 [ 
                                 d 
                                 ] 
                               
                               2 
                             
                           
                         
                       
                       ) 
                     
                   
                   ≥ 
                   
                     T 
                     t 
                   
                 
               
               
                 
                   ( 
                   45 
                   ) 
                 
               
             
           
         
       
     
     Further, where T t ″′ is defined by the formula (46) set forth below, the establishment of the formula (45) is equivalent to the establishment of the formula (47) set forth below. 
     
       
         
           
             
               
                 
                   
                     T 
                     t 
                     ″′ 
                   
                   = 
                   
                     
                       - 
                       2 
                     
                     ⁢ 
                     
                       log 
                       e 
                     
                     ⁢ 
                     
                       
                         T 
                         t 
                       
                       
                         θ 
                         σ 
                         2 
                       
                     
                   
                 
               
               
                 
                   ( 
                   46 
                   ) 
                 
               
             
           
         
       
       
         
           
             
               
                 
                   
                     
                       ∑ 
                       
                         d 
                         = 
                         0 
                       
                       
                         D 
                         - 
                         1 
                       
                     
                     
                       
                         
                           ( 
                           
                             
                               
                                 ( 
                                 
                                   x 
                                   n 
                                 
                                 ) 
                               
                               
                                 [ 
                                 d 
                                 ] 
                               
                             
                             - 
                             
                               
                                 ( 
                                 
                                   x 
                                   ′ 
                                 
                                 ) 
                               
                               
                                 [ 
                                 d 
                                 ] 
                               
                             
                           
                           ) 
                         
                         2 
                       
                       
                         
                           ( 
                           
                             θ 
                             l 
                           
                           ) 
                         
                         
                           [ 
                           d 
                           ] 
                         
                         2 
                       
                     
                   
                   ≤ 
                   
                     T 
                     t 
                     ″′ 
                   
                 
               
               
                 
                   ( 
                   47 
                   ) 
                 
               
             
           
         
       
     
     From the definition of the formula (46), the user is only required to determine T t , and an adaptive threshold value T t ′″ corresponding to the hyperparameter θ σ  of the kernel function is automatically set. 
     Where the kernel function is an ARD squared exponential kernel function, the extraction unit  103  may extract the extracted data E t  on the basis that the square of the normalized Euclidean distance between the point x n  and the point x′ is T t ″′ or less. In the calculation of the square of the normalized Euclidean distance, the value of each element of the D-dimensional length scale vector θ l  is adopted as the standard deviation of each dimension. In this case, the following formula (48) holds for E t . 
     
       
         
           
             
               
                 
                   
                     E 
                     t 
                   
                   = 
                   
                     { 
                     
                       
                         
                           ( 
                           
                             
                               x 
                               n 
                             
                             , 
                             
                               y 
                               n 
                             
                           
                           ) 
                         
                         ❘ 
                         
                           
                             
                               ∑ 
                               
                                 d 
                                 = 
                                 0 
                               
                               
                                 D 
                                 - 
                                 1 
                               
                             
                             
                               
                                 
                                   ( 
                                   
                                     
                                       
                                         ( 
                                         
                                           x 
                                           n 
                                         
                                         ) 
                                       
                                       
                                         [ 
                                         d 
                                         ] 
                                       
                                     
                                     - 
                                     
                                       
                                         ( 
                                         
                                           x 
                                           ′ 
                                         
                                         ) 
                                       
                                       
                                         [ 
                                         d 
                                         ] 
                                       
                                     
                                   
                                   ) 
                                 
                                 2 
                               
                               
                                 
                                   ( 
                                   
                                     θ 
                                     l 
                                   
                                   ) 
                                 
                                 
                                   [ 
                                   d 
                                   ] 
                                 
                                 2 
                               
                             
                           
                           ≤ 
                           
                             T 
                             t 
                             ″′ 
                           
                         
                       
                       , 
                       
                         n 
                         = 
                         0 
                       
                       , 
                       1 
                       , 
                       … 
                           
                       , 
                       
                         
                           N 
                           
                             t 
                             - 
                             1 
                           
                         
                         - 
                         1 
                       
                     
                     } 
                   
                 
               
               
                 
                   ( 
                   48 
                   ) 
                 
               
             
           
         
       
     
     T t ′″ is not limited to that shown in the formula (46). In this case, there is no guarantee that the extracted data is the same as that of the first embodiment, and T t ′″ does not depend on the signal standard deviation θ σ . In this case, the calculation of logarithm is unnecessary, and the calculation cost is reduced, accordingly. Even in this case, a set of pairs having a high similarity k(x n ,x′) are extracted as extracted data E t . 
     Where x′=P St (x n ), U t  is changed in accordance with the time t under the constraint that all R t  vectors along the R t  coordinate axes in the D-dimensional space are elements of the R t -dimensional linear subspace U t , and a square of a normalized Euclidean distance may be calculated by referring to only the (D−R t ) components corresponding to the U t   ⊥  components. Since the values of the U t  components need not be referred to, the calculation cost can be reduced. 
     The present modification was described referring to the case where the kernel function is an ARD squared exponential kernel function. Even where the kernel function is not an ARD squared exponential kernel function, it is only required to have a D-dimensional length scale as a hyperparameter. In this case, the extraction unit  103  may refer to observation points {x n |n=0, 1, . . . , N t−1 −1)} included in the observation data D t−1  stored in the storage unit  101 , and extract, as extracted data E t , a set of pairs corresponding to one or more observation points at which the square of the normalized Euclidean distance to a predetermined point x′ included in the low-dimensional search space S t  is equal to a predetermined value or less. In this case, there is no guarantee that the extracted data is the same as that of the first embodiment, but a set of pairs corresponding to the observation points x n  at which the similarity k(x n ,x′) is high are extracted as the extracted data E t . 
     &lt;Modification 6&gt; 
     Where the kernel function for calculating a similarity has a length scale vector as a hyperparameter, the extraction unit  103  according to modification 6 refers to one or more points in the D-dimensional space represented by one or more parameter vector values included in the observation data stored in the storage unit  101 , and extracts, as extracted data, a set of pairs corresponding to one or more points at which all D distances in the coordinate axis directions of the D-dimensional space with respect to a point included in the low-dimensional search space are a coefficient multiple of the corresponding element of the length scale vector or less. Specifically, where the kernel function has a D-dimensional length scale vector as a hyperparameter, the extraction unit  103  may extract extracted data E t  on the condition that the absolute value of the d-th component difference between the point x n  and the point x′ is T t ″″-fold of the d-th element of the D-dimensional length scale vector θ l  or less for all values of d (=0, 1, . . . , D−1). It should be noted that T t ″″ is a coefficient set by the user. In this case, E t  is expressed by the following formula (49). 
         E   t ={( x   n   ,y   n )| ∀   d ∈ { 0,1, . . . ,  D− 1}.|( x   n ) [d] −( x ′) [d]   |≤T″″   t (θ l ) [d]   , n= 0,1, . . . ,  N   t−1 −1}  (49)
 
     As can be seen from the formula (49), for the distance |(x n ) [d] −(x′) [d] | in each coordinate axis direction d (=0, 1, . . . , D−1) in the D-dimensional space, an adaptive threshold value can be set in accordance with the hyperparameter of the kernel function. This is not equivalent to modification 5 but is an approximation thereto. Therefore, advantages similar to those of modification 5 can be obtained. 
     Where x′=P St (x n ), U t  is changed in accordance with the time t under the constraint that all R t  vectors along the R t  coordinate axes in the D-dimensional space are elements of the R t -dimensional linear subspace U t , and extracted data E t  may be extracted on the basis that the absolute value of the d-th component difference between the point x n  and the point x′ is T t ″″-fold of the d-th element of the length scale vector θ l  or less for all (D−R t ) values corresponding to the U t   ⊥  components. Since the values of the U t  components need not be referred to, the calculation cost can be reduced. 
     &lt;Modification 7&gt; 
     Where the kernel function is a squared exponential kernel function, observation points x n  (n=0, 1, . . . , N t−1 −1) are rearranged such that distances of ∥x n −x′)∥ to a predetermined point x′ are arranged in ascending order, and the rearranged observation points are represented by x″ n  (n=0, 1, . . . , N t−1 −1) and the corresponding observation values are represented by y″ n . The extraction unit  103  may extract extracted data E t  represented by the formula (50) from D t−1 . It should be noted that r t  represents a percentage and takes a value that not less than 1/N t−1  and not more than 1, as in modification 1. Where r t  is 1, E t  is equal to D t−1 . floor(⋅) is a function for calculating the largest integer that is not more than an argument. 
         E   t ={( x″   n   ,y″   n )| n= 0,1, . . . , floor( r   t   N   t−1 )−1}  (50)
 
     E t  of the present modification and E t  of modification 3 are equivalent, depending upon how r t  and T t ′ are set. The present modification differs from modification 5 in that the number of elements N t ′ of E t  can be directly controlled by r t , as shown in the following formula (51). 
         N′   t =floor( r   t   N   t−1 )   (51)
 
     Since the calculation cost of an inverse matrix of GP regression depends on N t ′, the present modification is advantageous in that the calculation cost can be controlled. 
     The calculation cost of an inverse matrix increases sharply as N t ′ is large, while the calculation cost of the inverse matrix does not become a practical problem as long as N t ′ is small. Therefore, it is preferable to set r t  to 1 while the time t is small and the number of elements N t−1  of D t−1  is small. If the time t is large and the calculation cost of an inverse matrix becomes too high by making E t  equal to D t−1  and making N t ′ equal to N t−1 , it is preferable to set r t  to be smaller than 1 and set the calculation time to be within a desired time. As a result, the calculation cost of an inverse matrix can be suppressed with almost no deterioration in the search efficiency of parameter optimization. 
     Where x′=P St (x n ), U t  is changed in accordance with the time t under the constraint that all R t  vectors along the R t  coordinate axes in the D-dimensional space are elements of the R t -dimensional linear subspace U t , and a square of a normalized Euclidean distance may be calculated by referring to only the (D−R t ) components corresponding to the U t   ⊥  components. Since the values of the U t  components need not be referred to, the calculation cost can be reduced. 
     The present modification was described referring to the case where the kernel function is a squared exponential kernel function. Even if the kernel function is not a squared exponential kernel function, it is only required to have a length scale as a hyperparameter. In this case, the extraction unit  103  may refer to observation points {x n |n=0, 1, . . . , N t−1 −1)} included in the observation data D t−1  stored in the storage unit  101 , and extract, as extracted data E t , a set of pairs corresponding to observation points at which the distances ∥x n −x′∥ to a predetermined point x′ included in the low-dimensional search space S t  are within a predetermined percentage in ascending order. Even in this case, a set of pairs corresponding to observation points x n  at which the similarity k(x n ,x′) is high are extracted as extracted data E t . 
     &lt;Modification 8&gt; 
     Where a kernel function for calculating a similarity has a length scale vector as a hyperparameter, the extraction unit  103  according to modification 8 refers to one or more points in the D-dimensional space represented by one or more parameter -vector values included in the observation data stored in the storage unit  101  and extracts, as extracted data, a set of pairs corresponding to points at which the squares of normalized Euclidean distances to a point included in the low-dimensional search space are within a predetermined percentage in ascending order. In the calculation of the square of the normalized Euclidean distance, the extraction unit  103  adopts the value of each element of the length scale vector as the standard deviation corresponding to each coordinate axis direction of the D-dimensional space. 
     Where the kernel function is an ARD squared exponential kernel function, the observation points x n  (n=0, 1, . . . , N t−1 −1) are rearranged such that the squares of the normalized Euclidean distances to a predetermined point x′ are arranged in ascending order, and the rearranged observation points are represented by x* n  (n=0, 1, . . . , N t−1 −1) and the corresponding observation values are represented by y* n . In the calculation of the squares of the normalized Euclidean distances, the value of each element of the D-dimensional length scale vector θl is adopted as a standard deviation corresponding to each coordinate axis direction of the D-dimensional space. Therefore, the square of the normalized Euclidean distance of an observation point X n  to the predetermined point x′ is expressed by the following formula (52). 
     
       
         
           
             
               
                 
                   
                     ∑ 
                     
                       d 
                       = 
                       0 
                     
                     
                       D 
                       - 
                       1 
                     
                   
                   
                     
                       
                         ( 
                         
                           
                             
                               ( 
                               
                                 x 
                                 n 
                               
                               ) 
                             
                             
                               [ 
                               d 
                               ] 
                             
                           
                           - 
                           
                             
                               ( 
                               
                                 x 
                                 ′ 
                               
                               ) 
                             
                             
                               [ 
                               d 
                               ] 
                             
                           
                         
                         ) 
                       
                       2 
                     
                     
                       
                         ( 
                         
                           θ 
                           l 
                         
                         ) 
                       
                       
                         [ 
                         d 
                         ] 
                       
                       2 
                     
                   
                 
               
               
                 
                   ( 
                   52 
                   ) 
                 
               
             
           
         
       
     
     The extraction unit  103  may extract extracted data E t  expressed by the formula (53) from D t−1 . It should be noted that r t  represents a percentage and takes a value that is not less than 1/N t−1  and not more than 1, as in modification 1. Where r t  is 1, E t  is equal to D t−1 . floor(⋅) is a function for calculating the largest integer that is not more than an argument. 
         E   t ={( x*   n   ,y*   n )| n= 0,1, . . . , floor( r   t   N   t−1 )−1}  (53)
 
     E t  of the present modification and E t  of modification 5 are equivalent, depending upon how r t  and T t ′″ are set. The present modification differs from modification 5 in that the number of elements N t ′ of E t  can be directly controlled by r t , as shown in the following formula (54). 
         N′   t =floor( r   t   N   t−1 )   (54)
 
     Since the calculation cost of an inverse matrix of GP regression depends on N t ′, the present modification is advantageous in that the calculation cost can be controlled. 
     The calculation cost of an inverse matrix increases sharply as N t ′ is high, while the calculation cost of the inverse matrix does not become a practical problem as long as N t ′ is small. Therefore, it is preferable to set r t  to 1 while the time t is small and the number of elements N t−1  of D t−1  is small. If the time t is large and the calculation cost of an inverse matrix becomes too high by making E t  equal to D t−1  and making N t ′ equal to N t−1  , it is preferable to set r t  to be smaller than 1 and set the calculation time to be within a desired time. As a result, the calculation cost of an inverse matrix can be suppressed with almost no deterioration in the search efficiency of parameter optimization. 
     Where x′=P St (x n ), U t  is changed in accordance with the time t under the constraint that all R t  vectors along the R t  coordinate axes in the D-dimensional space are elements of the R t -dimensional linear subspace U t , and a square of a normalized Euclidean distance may be calculated by referring to only the (D−R t ) components corresponding to the U t   ⊥  components. Since the values of the U t  components need not be referred to, the calculation cost can be reduced. 
     The present modification illustrates the case where the kernel function is an ARD squared exponential kernel function. Even if the kernel function is not an ARD squared exponential kernel function, it is only required to have a length scale as a hyperparameter. In this case, the extraction unit  103  may refer to observation points {x n |n=0, 1, . . . , N t−1 −1)} included in the observation data D t−1  stored in the storage unit  101 , and extract, as extracted data E t , a set of pairs corresponding to observation points at which the squares of the normalized Euclidean distances to the predetermined point x′ included in the low-dimensional search space S t  are within a predetermined percentage in ascending order. Even in this case, a set of pairs corresponding to observation points x n  at which the high degrees of similarity k(x n ,x′) are high are extracted as extracted data E t . 
     &lt;Modification 9&gt; 
     The extraction unit  103  according to the present embodiment extracts extracted data E t  from observation data D t−1  at the time t in S 203 . Depending upon the kernel function used for this extraction, there is a hyperparameter. If the extraction of the extracted data E t  depends on the hyperparameter of a kernel function, it is necessary to determine the hyperparameter in advance. As the hyperparameter, a length scale or a vector of the length scale is assumed. 
     Where the adopted kernel function has a hyperparameter, the value of this hyperparameter should be determined in advance. The value may be a constant or may be changed in accordance with the time t. Where the value is a constant, it is preferable that the extraction unit  103  stores the hyperparameter value. 
     Where the hyperparameter of the kernel function is changed in accordance with the time t, the extraction unit  103  may have to estimate the hyperparameter value from observation data D t−1  or extracted data E t  at the time t in S 203  only for the extraction of E t . If this is done, the calculation cost increases, accordingly. Where the method of Non-Patent Document 1 is to be compared, it is preferable that the calculation cost should be as low as possible because the method of Non-Patent Document 1 does not include the process of extracting extracted data E t . 
       FIG.  5    is a diagram showing a functional configuration example of a parameter optimization system  5  according to modification 9. As shown in  FIG.  5   , in a parameter vector value proposal apparatus  500  according to modification 9, the storage unit  101  stores hyperparameters as well. In connection with the processes of modification 9, a description will be given of only modified points. In the description below, structural elements having substantially the same functions as the present embodiment will be denoted by the same reference symbols, and a repetitive description will be given only where necessary. 
     In S 203  where the time t is 1, the extraction unit  103  estimates a hyperparameter value from the observation data D 0 , using an arbitrary existing method as the hyperparameter estimation method. Extracted data E t  is extracted using the estimated hyperparameter value. 
     In S 204  at the time t, the proposal unit  104  estimates a hyperparameter value from the extracted data E t . As the hyperparameter estimation method, any existing method can be used. The estimated hyperparameter value is supplied to the storage unit  101 . The storage unit  101  stores the received hyperparameter value. The estimated hyperparameter value is also reflected in the definition of the acquisition function a t  used for determining proposal points. 
     In S 203  where the time t is 2 or thereafter, the extraction unit  103  acquires the hyperparameter value from the storage unit  101 . The hyperparameter value to be acquired is the hyperparameter value estimated by the proposal unit  104  at the time (t−1). The extraction unit  103  extracts extracted data E t  by using the hyperparameter value acquired by the extraction unit  103 . 
     According to this modification, the extraction unit  103  extracts extracted data E t  by utilizing the hyperparameter value which the proposal unit  104  estimates at an immediately preceding time, so that the hyperparameter value does not have to be estimated by the extraction unit  103 . 
     &lt;Modification 10&gt; 
       FIG.  6    is a diagram showing a pseudo program code which is according to modification 10 and corresponds to the parameter optimization process shown in  FIG.  2   . In the description below, reference will be made only to how the pseudo program code differs from that shown in  FIG.  3   . 
     S 601  is similar to S 301 , and S 602  is similar to S 302 . 
     S 603  corresponds to t=1 shown in the “for statement” of S 303 . In  FIG.  3   , the time t is incremented by the “for statement” of S 303 , whereas in  FIG.  6   , the time t is incremented in S 616  described later. 
     S 604  is a “for statement” not shown in  FIG.  3   . In this “for statement”, the “for statement” of S 605  described later is repeated J times. The maximum value of the time t is determined by J and by G and L described later. 
     S 605  is a “for statement” not shown in  FIG.  3   . In this “for statement”, the processes from S 606  to S 617  are repeated G times. 
     The processing content of S 606  is similar to that of S 304 , but the processing timing is different. In S 304 , processing is performed each time the time advances by 1, whereas in S 606  processing is performed each time the time advances by L (described later) since this step is outside the “for statement” of S 610  (described later) including S 616  (described later) in which the time t is incremented. 
     The processing content of S 607  is similar to that of S 305 , but the processing timing is different. In S 305 , processing is performed each time the time advances by 1, whereas in S 607  processing is performed each time the time advances by L (described later) since this step is outside the “for statement” of S 610  (described later) including S 616  (described later) in which the time t is incremented. 
     The processing content of S 608  is similar to that of S 306 , but the processing timing is different. In S 306 , processing is performed each time the time advances by 1, whereas in S 608  processing is performed each time the time advances by L (described later) since this step is outside the “for statement” of S 610  (described later) including S 616  (described later) in which the time t is incremented. 
     The processing content of S 609  is similar to that of S 307 , but the processing timing is different. In S 307 , processing is performed each time the time advances by 1, whereas in S 609  processing is performed each time the time advances by L (described later) since this step is outside the “for statement” of S 610  (described later) including S 616  (described later) in which the time t is incremented. 
     S 610  is a “for statement” not shown in  FIG.  3   . In this “for statement”, the processes from S 611  to S 616  are repeated L times. Since the processes from S 606  to S 608  for updating the low-dimensional search space S t  are outside this “for statement”, S t  does not change in this “for statement”. 
     The processing content of S 611  is similar to that of S 308 . The processing timing is also similar in that the time advances by one. 
     The processing content of S 612  is similar to that of S 309 . The processing timing is also similar in that the time advances by one. 
     The processing content of S 613  is similar to that of S 310 . The processing timing is also similar in that the time advances by one. 
     In S 614 , the extraction unit  103  generates extracted data E t  by integrating extracted data E t−1  and pairs (x Nt−1 , y Nt−1 ). Since x Nt−1  is a proposal point which the proposal unit  104  determines in the low-dimensional search space S t , it is an element of S t . Therefore, the similarity k(x Nt−1 ,x′) between the proposal point x Nt−1  and the predetermined point x′ is high. For example, where the kernel function is a squared exponential kernel function and x′=P St (x n ), the formula (55) set forth below holds. This is the maximum value that the similarity can take under these conditions. Therefore, even if the process of S 307  is performed at the same timing as S 614 , the same extracted data E t  as obtained in the process of S 614  is generated. Therefore, S 614  is equivalent to S 307 , depending upon the conditions. 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           k 
                           ⁡ 
                           ( 
                           
                             
                               x 
                               
                                 N 
                                 
                                   t 
                                   - 
                                   1 
                                 
                               
                             
                             , 
                             
                               x 
                               ′ 
                             
                           
                           ) 
                         
                         = 
                           
                         
                           k 
                           ⁡ 
                           ( 
                           
                             
                               x 
                               
                                 N 
                                 
                                   t 
                                   - 
                                   1 
                                 
                               
                             
                             , 
                             
                               
                                 P 
                                 
                                   S 
                                   t 
                                 
                               
                               ( 
                               
                                 x 
                                 
                                   N 
                                   
                                     t 
                                     - 
                                     1 
                                   
                                 
                               
                               ) 
                             
                           
                           ) 
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         
                           k 
                           ⁡ 
                           ( 
                           
                             
                               x 
                               
                                 N 
                                 
                                   t 
                                   - 
                                   1 
                                 
                               
                             
                             , 
                             
                               x 
                               
                                 N 
                                 
                                   t 
                                   - 
                                   1 
                                 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         
                           
                             θ 
                             σ 
                             2 
                           
                           ⁢ 
                           
                             exp 
                             ⁡ 
                             ( 
                             
                               
                                 - 
                                 
                                   1 
                                   2 
                                 
                               
                               ⁢ 
                               
                                 
                                   
                                      
                                     
                                       
                                         x 
                                         
                                           N 
                                           
                                             t 
                                             - 
                                             1 
                                           
                                         
                                       
                                       - 
                                       
                                         x 
                                         
                                           N 
                                           
                                             t 
                                             - 
                                             1 
                                           
                                         
                                       
                                     
                                      
                                   
                                   2 
                                 
                                 
                                   θ 
                                   l 
                                   2 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         
                           θ 
                           σ 
                           2 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   55 
                   ) 
                 
               
             
           
         
       
     
     The processing content of S 615  is similar to that of S 311 . The processing timing is also similar in that the time advances by one. S 616  corresponds to the increment of the time t shown in the “for statement” of S 303 . 
     S 617  is a “for statement” not shown in  FIG.  3   , and corresponds to the above-mentioned S 610 . S 618  is a “for statement” not shown in  FIG.  3   , and corresponds to the above-mentioned S 605 . S 619  is a “for statement” not shown in  FIG.  3   , and corresponds to the above-mentioned S 604 . 
     In S 620 , T is defined based on the number of times the time t is incremented in S 616 . This T corresponds to the T of S 303 . 
     S 621  is similar to S 313 . S 622  is similar to S 314 . 
     In the pseudo code of  FIG.  6   , the processes from S 606  to S 608 , which are related to the low-dimensional search space S t , are not executed until the time advances by L. In the processes performed by this pseudo code, S t  is fixed during that time, and proposal, observation and updating are repeated in the state in which S t  is fixed. 
     In S 607 , U t  may be changed and set in accordance with g. For example, R t  may be set to 1 regardless of the time t to establish G=D, g may be associated with each coordinate axis direction of the D-dimensional space, and U t  may be set as representing the one-dimensional linear subspace corresponding to g. 
     U t  may be set by another rule. An example will be described. G sets having integers 0 to D−1 as elements are defined and represented by h g (g=0, 1, . . . , G−1). The number of elements of h g  is 1 or more. For example, let it be assumed that h 0 ={0,1}, h 1 ={2,3,4,5}, h 2 ={6}, . . . , h G−1 ={D−2,D−1}. In correspondence with g of S 605 , it is preferable to set U t  as an R t -dimensional linear subspace that has only the direction vector of each coordinate axis corresponding to an element of h g  in the D-dimensional space as the basis vector. In this case, R t =#(h g ). It should be noted that #(⋅) is a function for calculating the number of elements. As a result, the basis vector of U t  changes in accordance with g. That is, the dimension and direction of U t  change in accordance with g. In this example, h g (g=0, 1, . . . , G−1) can be changed in various manners. An example in which R t  is set to 1 regardless of the time t, G and D are made equal to each other, g is made to correspond to each coordinate axis direction of the D-dimensional space, and the one-dimensional linear subspace corresponding to g is U t  corresponds to the case where h 0 ={0}, h 1 ={1}, h G−1 ={D−1}. 
     The number of elements of each h g  may be made constant regardless of j, or may be changed in accordance with j. Where the number of elements of each h g  is changed in accordance with j, the number may be changed randomly or may be changed according to a predetermined rule. The element of each h g  may be made constant regardless of j, or may be changed in accordance with j. Where the element of each h g  is changed in accordance with j, it may be changed randomly or may be changed according to a predetermined rule. 
     U t  may be set by still another rule. An example will be described. G sets having D-dimensional vectors as elements are defined, and these sets are represented by u g (g=0, 1, . . . , G−1). The number of elements of u g  is 1 or more. For example, let it be assumed that u 0 ={v 0,0 , v 0,1 }, u 1 ={v 1,0 , v 1,1 , v 1,2 , v 1,3 }, u 2 ={v 2,0 }, . . . , u G−1 ={v G−1,0 , v G−1,1 }. In correspondence with g of S 605 , it is preferable to set U t  as the R t -dimensional linear subspace that has only a D-dimensional vector, which is an element of u g , as the basis vector. In this case, R t =#(u g ). As a result, the basis vector of U t  changes in accordance with g. U t  in this case is not necessarily along the coordinate axis direction of the D-dimensional space. 
     The number of elements of each u g  may be made constant regardless of j, or may be changed in accordance with j. Where the number of elements of each u g  is changed in accordance with j, the number may be changed randomly or may be changed according to a predetermined rule. The elements of each u g  may be made constant regardless of j, or may be changed in accordance with j. Where the elements of each u g  are changed in accordance with j, they may be changed randomly or may be changed according to a predetermined rule. 
     By setting the U t  of the R t  (&lt;D) dimension in S 607 , the dimension of S t  also becomes an R t  dimension smaller than D, so that the search efficiency of parameter optimization is improved. 
     The pseudo code shown in  FIG.  6    includes three “for statements”, but as in  FIG.  3   , the “for statements” may be limited those related to the time t and can be transformed into a pseudo code whose processing content is equivalent to that shown in  FIG.  6   . In the modified pseudo code, j, g, and l shown in  FIG.  6    have to be incremented. Further, g and l have to be reset to 0 when they have incremented and reached G−1 and L−1, respectively. The processing flow of the transformed pseudo code corresponds to that shown in  FIG.  2   . Therefore, the method of controlling U t  based on h g  or u g  can also be applied to the present embodiment. Since the present modification corresponds to  FIG.  2   , it has advantages similar to those of the present embodiment. 
     &lt;Modification 11&gt; 
     The extraction unit  103  according to modification 11 extracts extracted data from observation data, based on the cumulative contribution ratio regarding degrees of similarity. Modification 11 will be described in detail below. 
     As in modification 1, observation points x n  (n=0, 1, . . . , N t−1 −1) are rearranged such that degrees of similarity k(x n ,x′) to a predetermined point x′ are arranged in descending order, and the rearranged observation points are represented by x″ n  (n=0, 1, . . . , N t−1 −1) and the corresponding observation values are represented by y″ n . As shown in the formula (56) set forth below, the ratio of a cumulative similarity to the sum of degrees of similarity will be referred to as a cumulative contribution ratio regarding degrees of similarity. 
     
       
         
           
             
               
                 
                   
                     Cumulative 
                     ⁢ 
                         
                     contribution 
                     ⁢ 
                         
                     ratio 
                     : 
                     
                       
                         
                           ∑ 
                           
                             n 
                             = 
                             0 
                           
                           
                             N 
                             - 
                             1 
                           
                         
                         
                           k 
                           ⁡ 
                           ( 
                           
                             
                               x 
                               n 
                               ″ 
                             
                             , 
                             
                               x 
                               ′ 
                             
                           
                           ) 
                         
                       
                       
                         
                           ∑ 
                           
                             n 
                             = 
                             0 
                           
                           
                             
                               N 
                               
                                 t 
                                 - 
                                 1 
                               
                             
                             - 
                             1 
                           
                         
                         
                           k 
                           ⁡ 
                           ( 
                           
                             
                               x 
                               n 
                             
                             , 
                             
                               x 
                               ′ 
                             
                           
                           ) 
                         
                       
                     
                   
                   ⁢ 
                   
 
                   
                     Sum 
                     ⁢ 
                         
                     of 
                     ⁢ 
                         
                     degrees 
                     ⁢ 
                         
                     of 
                     ⁢ 
                         
                     similarity 
                     : 
                     
                       
                         ∑ 
                         
                           n 
                           = 
                           0 
                         
                         
                           
                             N 
                             
                               t 
                               - 
                               1 
                             
                           
                           - 
                           1 
                         
                       
                       
                         k 
                         ⁡ 
                         ( 
                         
                           
                             x 
                             n 
                           
                           , 
                           
                             x 
                             ′ 
                           
                         
                         ) 
                       
                     
                   
                   ⁢ 
                   
 
                   
                     Cumulative 
                     ⁢ 
                         
                     similarity 
                     : 
                     
                       
                         ∑ 
                         
                           n 
                           = 
                           0 
                         
                         
                           N 
                           - 
                           1 
                         
                       
                       
                         k 
                         ⁡ 
                         ( 
                         
                           
                             x 
                             n 
                             ″ 
                           
                           , 
                           
                             x 
                             ′ 
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   56 
                   ) 
                 
               
             
           
         
       
     
     The extraction unit  103  may obtain a minimum N at which the cumulative contribution ratio becomes more than a predetermined value, and extract extracted data E t  represented by the formula (57) from D t−1 . 
         E   t ={( x″   n   ,y″   n )| n= 0,1, . . . ,  N− 1}  (57)
 
     The extraction of E t  according to the formula (57) is equivalent to the extraction of E t  according to the formula (5) in which T t  satisfying k(x″ N−1 ,x′)≥T t &gt;k(x″ N ,x′) is set. In the present embodiment, T t  that satisfying k(x″ N−1 ,x′)≥T t &gt;k(x″ N ,x′) may be set. Therefore, the advantages of the present modification are similar to those of the present embodiment. In the present modification or in the present embodiment in which T t  satisfying k(x″ N−1 ,x′)≥T t &gt;k(x″ N ,x′) is set, the approximation of the formula (23) to the formula (25) is applicable to the case where the cumulative contribution ratio regarding degrees of similarity is used, so that the approximation accuracy is highly explanatory. 
     &lt;Modification 12&gt; 
     The present embodiment and a number of modifications have been described above. These are presented by way of example only and are not intended to limit the scope of the invention. Indeed, the novel embodiments described herein may be embodied in a variety of other forms; furthermore, various omissions, substitutions and changes in the form of the embodiments described herein may be made without departing from the spirit of the invention. The accompanying claims are intended to cover such forms or modifications as would fall within the scope and spirit of the invention. 
     &lt;Hardware Configuration&gt; 
       FIG.  7    is a diagram showing a hardware configuration example of the parameter vector value proposal apparatus  100 ,  500 . As shown in  FIG.  7   , the parameter vector value proposal apparatus  100 ,  500  include a processing circuit  71 , a main storage device  72 , an auxiliary storage device  73 , a display device  74 , an input device  75 , and a communication device  76 . The processing circuit  71 , the main storage device  72 , the auxiliary storage device  73 , the display device  74 , the input device  75 , and the communication device  76  are coupled to each other via a bus. 
     The processing circuit  71  executes a parameter vector value proposal program read from the auxiliary storage device  73  to the main storage device  72 , and functions as a search space determination unit  102 , an extraction unit  103 , a proposal unit  104  and a control unit  105 . The main storage device  72  is a memory, such as a RAM (Random Access Memory). The auxiliary storage device  73  is an HDD (Hard Disk Drive), an SSD (Solid State Drive), a memory card, or the like. The main storage device  72  and the auxiliary storage device  73  function as a storage unit  101 . 
     The display device  74  displays various kinds of information. The display device  74  is, for example, a display, a projector, or the like. 
     The input device  75  is an interface for operating a computer. The input device  75  is, for example, a keyboard, a mouse, or the like. The display device  74  and the input device  75  may be configured as a touch panel. The communication device  76  is an interface for communicating with another device, such as an observation apparatus  200 . 
     A Program executed on a computer is recorded in a computer-readable storage medium, such as a CD-ROM, a memory card, a CD-R, and a DVD (Digital Versatile Disc), as an installable or executable format file, and is delivered as a computer program product. 
     A program executed on a computer may be stored in a computer connected to a network, such as the Internet, and may be provided as a program downloadable via the network. Further, the program executed on the computer may be provided via the network, such as the Internet, without being downloaded. 
     A program executed on a computer may be provided by incorporating it into a ROM or the like in advance. The program executed on the computer has a module configuration which is included among the functional configurations (functional blocks) of the parameter vector value proposal apparatus  100 ,  500  and which includes a functional block that can be realized by the program. As actual hardware, each functional block is loaded onto the main storage device  72  when the processing circuit  71  reads a program from the storage medium and executes the program. That is, each of the above functional blocks is generated on the main storage device  72 . 
     Instead of realizing part or all of the above-mentioned functional blocks by software, they may be realized by hardware such as an IC (Integrated Circuit). Where each function is realized by using a plurality of processors, each processor may realize one function, or may realize two or more functions. 
     The operation mode of the computer that realizes the parameter vector value proposal apparatus  100 ,  50  may be arbitrarily determined. For example, the parameter vector value proposal apparatus  100 ,  50  may be realized by one computer. Further, for example, the parameter vector value proposal apparatus  100 ,  50  may be operated as a cloud system on the network. 
     While certain embodiments have been described, these embodiments have been presented by way of example only, and are not intended to limit the scope of the inventions. Indeed, the novel embodiments described herein may be embodied in a variety of other forms; furthermore, various omissions, substitutions and changes in the form of the embodiments described herein may be made without departing from the spirit of the inventions. The accompanying claims and their equivalents are intended to cover such forms or modifications as would fall within the scope and spirit of the inventions.