Directional optimization via EBW
View Patent ↗An optimization system and method includes determining a best gradient as a sparse direction in a function having a plurality of parameters. The sparse direction includes a direction that maximizes change of the function. This maximum change of the function is determined by performing an optimization process that gives maximum growth subject to a sparsity regularized constraint. An extended Baum Welch (EBW) method can be used to identify the sparse direction. A best step size is determined along the sparse direction by finding magnitudes of entries of direction that maximizes the function restricted to the sparse direction. A solution is recursively refined for the function optimization using a processor and storage media.
1. An optimization method, comprising:
determining a best gradient as a sparse direction in a function having a plurality of parameters, the sparse direction including a direction that maximizes change of the function as determined by an optimization method where a sparse direction is defined from sparse regularized constraints;
determining a best step size along the sparse direction by finding magnitudes of entries of direction by solving an optimization problem that is constrained to the sparse direction; and
recursively refining a solution to the optimization problem using a processor and storage media until a threshold constraint is met.
2. The method as recited in claim 1 , wherein determining a best gradient includes identifying a size ε of a directional ball for determining the best direction for a directional optimization problem in parameter space of the plurality of parameters.
3. The method as recited in claim 2 , wherein determining a best gradient includes given the sparse direction, determining a larger directional ball R along the sparse direction; and identifying a sub-optimal size inside R.
4. The method as recited in claim 1 , wherein determining a best gradient includes performing an extended Baum Welch method to identify the sparse direction.
5. The method as recited in claim 4 , wherein performing an extended Baum Welch (EBW) method to identify the sparse direction includes solving the EBW with the following:
z
i
t
+
1
=
z
i
t
+
1
(
D
)
=
(
c
i
+
D
)
z
i
t
∑
j
c
j
z
j
t
+
D
(
12
)
where t, i and j are indexes,
c
j
=
c
j
(
z
t
)
=
∂
G
(
z
t
)
∂
z
j
t
,
D is a constant that controls growth of function values, G is a differentiable function in z, which converges to a local maximum of G(z) in the domain Σz i =1, z i ≧0.
6. The method as recited in claim 1 , wherein determining a best gradient includes computing the gradient as
max
v
F
(
v
0
+
v
)
-
F
(
v
0
)
s
.
t
.
v
0
1
<
ɛ
where F is the function, v is a direction, direction vector v belongs to a subspace that passes through the point v 0 , and a sparsity constraint includes ∥v∥ 1 <ε where ε is a threshold for the sparsity constraint.
7. The method as recited in claim 1 , wherein the function includes a function subject to a fractional normalized constrained inequality.
8. The method as recited in claim 7 , further comprising:
adding a dumb non-negative variable to map the constrained inequality into a fractionally constrained multi-dimensional sphere;
transforming the fractional multi-dimensional sphere into a norm one sphere;
mapping the norm one sphere into a simplex of non-negative numbers; and
transforming an objective function over the norm one sphere into the objective function over the simplex.
9. A computer readable storage medium comprising a computer readable program for an optimization method, wherein the computer readable program when executed on a computer causes the computer to perform the steps of:
determining a best gradient as a sparse direction in a function having a plurality of parameters, the sparse direction including a direction that maximizes change of the function as determined by an optimization method where a sparse direction is defined from sparse regularized constraints;
determining a best step size along the sparse direction by finding magnitudes of entries of direction by solving an optimization problem that is constrained to the sparse direction; and
recursively refining a solution to the optimization problem until a threshold constraint is met.
10. The computer readable storage medium as recited in claim 9 , wherein determining a best gradient includes identifying a size ε of a directional ball for determining the best direction for a directional optimization problem in parameter space of the plurality of parameters.
11. The computer readable storage medium as recited in claim 10 , wherein determining a best gradient includes given the sparse direction, determining a larger directional ball R along the sparse direction; and identifying a sub-optimal size inside R.
12. The computer readable storage medium as recited in claim 9 , wherein determining a best gradient includes performing an extended Baum Welch method to identify the sparse direction.
13. The computer readable storage medium as recited in claim 12 , wherein performing an extended Baum Welch (EBW) method to identify the sparse direction includes solving the EBW with the following:
z
i
t
+
1
=
z
i
t
+
1
(
D
)
=
(
c
i
+
D
)
z
i
t
∑
j
c
j
z
j
t
+
D
(
12
)
where t, i and j are indexes,
c
j
=
c
j
(
z
t
)
=
∂
G
(
z
t
)
∂
z
j
t
,
D is a constant that controls growth of function values, G is a differentiable function in z, which converges to a local maximum of G(z) in the domain Σz i =1, z i ≦0.
14. The computer readable storage medium as recited in claim 9 , wherein determining a best gradient includes computing the gradient as
max
v
F
(
v
0
+
v
)
-
F
(
v
0
)
s
.
t
.
v
0
1
<
ɛ
where F is the function, v is a direction, direction vector v belongs to a subspace that passes through the point v 0 , and a sparsity constraint includes ∥v∥ 1 <ε where ε is a threshold for the sparsity constraint.
15. The computer readable storage medium as recited in claim 9 , wherein the function includes a function subject to a fractional normalized constrained inequality.
16. The computer readable storage medium as recited in claim 15 , further comprising:
adding a dumb non-negative variable to map the constrained inequality into a fractionally constrained multi-dimensional sphere;
transforming the fractional multi-dimensional sphere into a norm one sphere;
mapping the norm one sphere into a simplex of non-negative numbers; and
transforming an objective function over the norm one sphere into the objective function over the simplex.
17. A system for optimization of a function with a large number of parameters, comprising:
a processor configured to determine a best gradient as a sparse direction in a function having a plurality of parameters, the sparse direction including a direction that maximizes change of the function as determined by an optimization method where a sparse direction is defined from sparse regularized constraints;
the processor being configured to determine a best step size along the sparse direction by solving an optimization problem to find magnitudes of entries of direction that are constrained to the sparse direction; and
a memory storage device is configured to store a recursively refined optimization solution of the function.
18. The system as recited in claim 17 , further comprising a directional ball of a size ε which is employed as a constraint for determining the best direction in parameter space for the plurality of parameters.
19. The system as recited in claim 18 , wherein given the sparse direction, the processor determines a larger sized ball R along the sparse direction; and identifies a sub-optimal size inside R.
20. The system as recited in claim 17 , wherein the processor performs an extended Baum Welch to identify the sparse direction.
21. The system as recited in claim 17 , wherein a best gradient is determined by:
max
v
F
(
v
0
+
v
)
-
F
(
v
0
)
s
.
t
.
v
1
<
ɛ
where F is the function, v is a direction, direction vector v belongs to a subspace that passes through the point v 0 and a sparsity constraint includes ∥v∥ 1 <ε where ε is a threshold for the sparsity constraint.
22. The system as recited in claim 21 , wherein an extended Baum Welch (EBW) method identifies the sparse direction by solving the EBW with the following:
z
i
t
+
1
=
z
i
t
+
1
(
D
)
=
(
c
i
+
D
)
z
i
t
∑
j
c
j
z
j
t
+
D
(
12
)
where t, i and j are indexes,
c
j
=
c
j
(
z
t
)
=
∂
G
(
z
t
)
∂
z
j
t
,
D is a constant that controls growth of function values, G is a differentiable function in z, which converges to a local maximum of G(z) in the domain Σz i =1, z i ≧0.
23. The system as recited in claim 17 , wherein the function includes a function subject to a fractional normalized constrained inequality.
24. The system as recited in claim 17 , wherein the function includes at least 100,000 parameters.