Method for machine learning with state information
AssigneeInternational Business Machines Corporation
InventorsElad Eliezer Hazan, Nimrod Megiddo
Life of this patent
Estimating the term…
Abstract
Methods, systems, and computer program products are provided for the online convex optimization problem, in which the decision maker has knowledge of the all past states and resulting cost functions for his previous choices and attempts to make a new choice that results in minimum regret. The method does not rely upon the structure of the cost function or the characterization of the states and takes advantage of the similarity between successive states to enable the method to converge to a reasonably optimal result.
Claims14
A system for iteratively improving a chosen solution to an online convex optimization problem, the system executing procedures for:
- collecting known information known by a decision maker at time T, the collection of known information comprising a set of past decisions x1, . . . ,xt-1 made by a decision maker prior to time T, a set of state variables k1, . . . ,kt, and a sequence of T-1 convex functions of the form ƒt, each convex function mapping a convex set P into a set R of real numbers (ƒt:P→R) for t=1,2, . . . ,T−1;
- selecting a state vector {tilde over (k)}t from a plurality of known state vectors for which a distance between the selected state vector and each state vector from the plurality of state vectors is less than a threshold value ε;
- developing a new state vector based upon the selected state vector;
- and
- determining a cost associated with the new state vector.
A method for choosing a solution xt at time t (t=1,2, . . . ) to an online convex optimization problem, the method accepting ƒt-1, xt-1, the current state vector kt ∈ I, and all previous state vectors k1, . . . ,kt-1, wherein kt ∈ [0,1]d, wherein I is a metric space having a distance function and a diameter W, the metric space I being a subset of d-dimensional Euclidean space (I ⊂ Rd), and wherein P is a convex set with diameter D with the vectors xt ∈ P for t=1,2, . . . ,T, the method comprising the steps of:
- choosing a Lipschitz-constant L for the metric space I;
- choosing a threshold value ε;
- setting N=φ, wherein N is a subset of I;
- setting x0 to an arbitrary value for t=0;
- initializing an iteration value t equal to 1;
- and
- while t≦T, executing the steps of:
- choosing the state {tilde over (k)}t that is closest to kt among all state vectors in N by setting {tilde over (k)}t=arg min{∥k−kt∥:k ∈ N};
- setting xt←M({tilde over (k)}t) for t≠0;
- setting
- y
- ←
- ∏
- P
-
- (
- M
-
- (
- k
- ~
- t
- )
- -
- 1
- T
-
- ∇
- f
- t
-
- (
- M
-
- (
- k
- ~
- t
- )
- )
- )
- ,
- where ΠP denotes the projection operator into the convex set P;
- updating M({tilde over (k)}t)←y if ∥{tilde over (k)}t−kt∥≦ε,
- adding kt to the set N and setting M(kt)←y if ∥{tilde over (k)}t−kt∥>ε, and
- incrementing t by 1.
A tangible computer readable medium containing a computer program comprising:
- a mathematical framework describing an online convex optimization problem for a physical system at time t, the mathematical framework comprising:
- a Lipschitz-constant L for a metric space I with a diameter D;
- a time period T;
- a cost function ƒt-1;
- a current state vector kt ∈ I and all previous state vectors k1, . . . ,kt-1;
- a threshold value ε;
- and
- a null set N=φ;
- a distance operation for selecting a state vector {tilde over (k)}t chosen to be closest to state vector kt from among all state vectors in N according to the operation of {tilde over (k)}t=arg min {∥k−kt∥:k ∈ N};
- an initial condition achieved by setting xt←M({tilde over (k)}t) for t≠0 and setting x0 arbitrarily for t=0;
- an operation for choosing a vector y chosen according to the operation
- y
- ←
- ∏
- P
-
- (
- M
-
- (
- k
- ~
- t
- )
- -
- 1
- T
-
- ∇
- f
- t
-
- (
- M
-
- (
- k
- ~
- t
- )
- )
- )
- ,
- where ΠP denotes the projection operator into the convex set P;
- an updating operation consisting of updating M({tilde over (k)}t)←y if μkt−kt∥≦ε;
- and
- an additive operation consisting of adding kt to the set N and setting M(kt)←y if ∥{tilde over (k)}t−kt∥>ε;
- wherein the operations are executed within the mathematical framework to arrive at a feasible solution to the online convex optimization problem.
A computer program product comprising a computer useable medium having a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:
- define a metric space I having a diameter D;
- define a set N, wherein N ⊂ I;
- define a convex compact set P ⊂ Rn having a diameter W, wherein the set P is a feasible domain for solutions to an online convex optimization problem;
- define a mapping M that maps every point in the set N to a point in decision space P;
- accept as input Lipschitz-constant L for a metric space I;
- a time period T;
- a cost function ƒt-1;
- a current state vector kt ∈ I, all previous state vectors k1, . . . ,kt-1;
- and a threshold value ε;
- set as an initial condition xt←M({tilde over (k)}t) for t≠0;
- set x0 arbitrarily for t=0;
- calculate a state vector {tilde over (k)}t chosen to be closest to each state vector kt from among all state vectors in N;
- choose a vector y according to the criterion
- y
- ←
- ∏
- P
-
- (
- M
-
- (
- k
- ~
- t
- )
- -
- 1
- T
-
- ∇
- f
- t
-
- (
- M
-
- (
- k
- ~
- t
- )
- )
- )
- ,
- where ΠP is a projection operator into the convex set P;
- update M({tilde over (k)}t)←y if ∥{tilde over (k)}t−kt∥≦ε;
- and
- add kt to the set N and setting M(kt)←y if ∥{tilde over (k)}t−kt∥>ε.
Dependencies are inferred from the claim text.