Ke Tang Southern University of Science and Technology Yang Yu Nanjing University
. The need of machine learning . Evolutionary computation for supervised Learning – New case studies. . Evolutionary Reinforcement Learning
• Three key components of machine learning: –  Data/model representation – Evaluation – Training algorithm • Most modern machine learning problems are essentially searching for the model that is optimal with respect to some objective function (e.g., generalization). • Optimization algorithms thus play a crucial role in machine learning.
2

• Many machine learning tasks, when formulated as an optimization problem, cannot be well solved by traditional (e.g., convex) optimization techniques. Plan A: Approximate the original (non-convex) optimization problem with a convex one. Plan B: Seek an approximate solution to the original problem with heuristic methods, e.g., Evolutionary algorithms.
EAs have been applied to a large variety of learning problems in the past decades. •   Data representation –  Feature selection –  Feature extraction –  Dimensionality Reduction . Model training –  Decision tree –  Neural networks – Rule-based systems – Clustering •   Hyper-parameter tuning
Machine learning has its own characteristics that calls for specialized EAs. •  Huge problem size (i.e., the search space). •  Noisy fitness evaluation (since the generalization cannot be precisely measured) •  Expensive fitness evaluation • Theoretical guarantee is more preferred than in other areas.
•  Subset selection: select  a subset of size k from a total set of n variables for optimizing some criterion. Formally stated: given all variables V = {X1, ...,Xn}, a criterion f and a positive integer k, arg minscv f(S) s.t.  |S| ≤ k. • NP-hard in general [Natarajan,1995; Davis et al., 1997] and arises in many learning problems: –  Feature Selection –  Sparse Learning –  Compressed Sensing
• Greedy algorithms [Gilbert et al., SODA’03; Tropp, TIT’04] – Process: iteratively select or abandon one variable that makes the criterion currently optimized –  Weakness:  get stuck in local optima due to the greedy behavior
•  Convex relaxation methods [Tibshirani, JRSSB’96; Zou & Hastie, JRSSB’05] – Process:  replace the set size constraint with convex constraints, then find the optimal solutions to the relaxed problem. –  Weakness:  the optimal solution of the relaxed problem may be distant to the true optimum.
non-convex arg minwern g(w) convex
• There have been numerous EAs for subset selection, while rigorous theoretical guarantee is few. . Subset Selection as a bi-objective optimization problem POSS (Pareto Optimization for Subset Selection) minscv f(S) s.t.  |S| ≤ k The basic idea: 17 minscy  (f (S), |S|) constrained bi-objective
Algorithm 1 POSS Input : all vari and an integer parame Parameter: the nu Output: a sul Initialization: randomly generate a solution, put it into the archive P Reproduction: pick a solution randomly from P , and randomly change it to make a new one Evaluation & Selection: if the new solution is not dominated, put it into P and weed out bad solutions Output: select the best feasible solution Chaoqian paper
Sparse regression is to find a sparse approximation solution to the regression problem. Formally stated: given all observation variables V = {X1, ...,Xn}, a predictor variable Z and a positive integer k, define the mean squared error of a subset S ⊆ V as MSEz,s = min α∈RIsI E [(Z − ∑i∈sαiXi)²] Sparse regression is arg minscv MSEz,s s.t. |S| ≤ k. Chao Qian, Yang Yu, and Zhi-Hua Zhou. Subset Selection by Pareto Optimization.In: Advances in Neural Information Processing Systems 28 (NIPS'15), Montreal, Canada, 2015, pp.1765-1773.

Previous theoretical bounds:
u: the coherence, γ: the submodular ratio •   [Gilbert et al., 2003]: (1 + Θ(uk²)) •  OPT on MSEz s for u ∈ 0(1/k) by a two-phased approach •   [Tropp et al., 2003; Tropp, 2004]: improve the above bound •   [Das & Kempe, 2008]: (1 – Θ(uk))・ΟΡΤ on R 2 s for u ∈ 0(1/k) by the forward regression algorithm •  [Das & Kempe, 2011]: (1 — e-Y) •  OPT on R 2 s by the forward regression algorithm •   [Shalev-Shwartz et al., 2010; Yuan & Yan, 2013]: lower bounds on |S| for achieving OPT + ε strongest
13

Theorem 1. For sparse regression, POSS with E[T] ≤ 2ek²n and I(·) = 0 (i.e., a constant function) finds a set S of variables with | S | ≤ k and R ≥ , 5 ≥ (1 − e − γ ø, k ) · O P T . the best previous theoretical guarantee POSS can do at least as well as previous methods. Theorem 2.  For the Exponential Decay subclass of sparse regression, POSS with E[T] ∈ O(k²n² log n) and I(s ∈ {0, 1} n ) = min{ i | s i = 1} can find the optimal solution. Proposition 1.  For Example 1 with n = 3, r 2 = 0.03, r 3 = 0.5, Cov(Y1,Z) = Cov(Y2,Z) = δ and Cov(Y3,Z) = 0.505δ, FR cannot find the optimal solution for k = 2. POSS can do strictly better than previous methods.
14

POSS for Sparse Regression: Summary . the number of iterations Theory Theorem 1. For sparse regression, POSS with E[T] S of variables with |S| < k and P the best known polynomial-time approximation bound [Das & Kempe, ICML'11]
Experiment significantly better than all the compared methods on all data sets
Algorithm 1 POSS Xn}, a given objective f Input: all variables V = {X and an integer parameter k ∈ Parameter: the number of its Output : a subset of V  with at most k variables Process: 1:  Let s = {0} n and P = 2: Let t = 0. 3: while t < T da Select s from P uniformly at random. enerate s' by flipping each bit of s with prob. ^. valuate f 1 ( s ′ ) and f 2 ( s ′ if Az ∈ P such that z ← Q = {z ∈ P | s' ( P \ O ) end if t = t + 1. ll: 12:  end while 13:   return arg minsEP,|s|<k ƒ1( S ) generate only one new solution in one iteration sequential A sequential algorithm that cannot be readily parallelized restrict the application to large-scale real-world problems
Theoretical guarantee still holds? in one iteration Chao Qian, Jing-Cheng Shi, Yang Yu, Ke Tang, and Zhi-Hua Zhou. Parallel Pareto Optimization for Subset Selection. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI'16), New York, NY, 2016, pp.1939- 17 1945.
•
Theoretical results
f (S 2 ) ≥ f (S 1 ) for any S 1  ≥ S 2 Theorem 1. For maximizing a monotone function under the set size constraint, the expected number of iterations until PPOSS finds a solution s with |s| ≤ k and f(s) ≥ (1 − e− γmin) · OPT, where γmin = min s:|s|=k−1 γs,k, is (1) if(N)= o(n), then E(T) < 2ek²n/N; → the same approximation bound (2) if N = Ω(n ² ) for 1 ≤ i ≤ k, then E[T] = O(k 2 /i); (3) if N = Ω(nmin{3k-1,n}), then E[T] = O(1). . When the number of processors is less than the number of variables, the number of iterations can be reduced linearly w.r.t. the number of processors . With increasing number of processors, the number of iterations can be continuously reduced, eventually to a constant The best previous known bound . submodular [Nemhauser & Wolsey, MOR'78] . sparse regression (non-submodular) [Das & Kempe, ICML’11]
Sparse regression arg mins	cv MSEz.s s.t. | S| ≤ k R²s = (Var(Z) — MSEz,s)/Var(Z) the larger the better data set
the sparsity k = 8 the number of cores N = 1  → 10 For PPOSS with each N value on each data set, the run is repeated for 10 runs independently, and the average results are reported
19

Compare the speedup as well as the solution quality measured by R² values with different number of cores
the asynchronous version of PPOSS (f) on farm-ads (4143 instances, 54877 features) PPOSS (blue line): achieve speedup around 8 when the number of cores is 10; the R² values are stable PPOSS-asy (red line): achieve better speedup (avoid the synchronous cost); the R² values are slightly worse (the noise from asynchronization) the best previous algorithm [Das & Kempe, ICML'11]
• Ensemble Pruning is also a subset selection problem. Ensemble pruning: select a subset of learners to combine • reduce storage & improve efficiency • better performance than the complete ensemble [Martinez-Munoz and Suarez, ICML’06]
.
Better than any other method on more than 60% (12.5/20) data sets, and never significantly worse 24

Better than any other method on more than 80% (16/20)
data sets; never significantly worse, except two losses
Chao Qian, Yang Yu, and Zhi-Hua Zhou. Pareto Ensemble Pruning. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI'15), Austin, TX, 2015, pp.2935-2941.
Many real-world classification problems are cost-sensitive. . The optimal classifier for a binary classification problem . = argmin  C 10 · FNR(h)+ C 01 · FPR(h) hEQ (1)
 A good classifier could be used via cost-sensitive learning. .
26

However, costs are often subject to great uncertainty. . –  Very difficult to specify the exact cost values before training. –  The costs may change over time. Alternative: seeking a group of classifiers that maximize the . the Receiver Operating Characteristic (ROC) convex hull. “The optimal classifier for any cost values must be a vertex or on the edge of the convex hull of all (achievable) classifiers in the ROC space." [Provost and Fawcett, 2001]
27

• New Learning Target: To obtain a set of classifiers such that their ROCCH is maximized. • This is a set-oriented optimization problem can could hardly be solved with existing approaches. • Evolutionary Algorithms provides a natural way to search for a set (population) of classifiers.
28

. Multi-objective evolutionary algorithms (MOEAs) are off-the-shelf tools for this problem – Maximize TPR – Minimize FPR . Direct application of an MOEA is OK, while not ideal. – A Pareto optimal solution is not necessarily a vertex on the convex hull. − Many-to-one mapping between the hypothesis and ROC spaces.
. Approach: Convex Hull-based MOEA (CH-MOEA) • Features of CH-MOEA: –  Convex hull-based sorting –  Redundancy elimination
30

•
Convex Hull-based Sorting
Algorithm 2 DeltaArea (T)
Require:  T ≠ 0 1: T is a solution set Ensure:  DeltaArea 2:  Q = T 3:  m = sizeof(Q) 4:  E is performance of Q 5:  DeltaH 1 , …, DeltaH m ← 0 6:  if m < 3 then Set DeltaH 1 , …, DeltaH m ← ∞ 7: 8: else Set DeltaH 1 , DeltaH m ← ∞ 9: 10: for 2 ≤ i ≤ sizeof(Q) − 1 do 11: DeltaH i = 0.5 × det((E i -E i −1) 0 (E i +1-E i −1)) end for 12: while sizeof(Q) > 2 do 13: r ← argmin{DeltaH} 14: 15: Q ← Q/{Qr} Update(DeltaH r _1,DeltaH r +1) 16: end while 17: 18: end if 19:  Return (DeltaH) V Point x has vector X Point /  has vector L Point u has vector U The contribution of x to its current ROCCH front A x
•  Redundancy Elimination
• CH-MOEA can be combined with any base learners to build either homogeneous and heterogeneous ensembles –  Neural Network –  Decision Tree l SVM . Different types of base learners need different search operators. . We implemented CH-MOEA with Genetic Programming (CH- MOGP). P. Wang, M. Emmerich, R. Li, K. Tang, T. Baeck and X. Yao, "Convex Hull-Based Multi-objective Genetic Programming for Maximizing Receiver Operating Characteristic Performance," IEEE Transactions on Evolutionary Computation, 19(2): 188- 200, April 2015.
. Empirical studies −  Which MOEA framework performs the best for our problem? – Is CH-MOGP competitive in comparison to non-evolutionary methods? •
Compared methods
– NSGA-II – MOEA/D –  SMS-EMOA (an indicator based MOEA) - C4.5 –  PRIE ([Fawcett, 2008], a state-of-the-art heuristic approach for ROCCH maximization) –  Naïve Bayes All evolutionary approaches adopt the same base learner and reproduction operator
.
CH-MOEA outperformed other state-of-the-art methods in terms of solution quality Evolutionary Reinforcement Learning
learning a strategy to interact with the environment for maximizing the long-term reward
Policy (deterministic): π : S → A
Agent's goal: learn a policy to maximize long-term total reward discounted:
supervised learning reinforcement learning environment SL searches for a model RL searches for the right output and a model
general binary space problem f ( x max xE{0,1}n solving the optimal policy is NP-hard!
dynamic programming
A s'
s'
overall idea: how is the current policy   policy evaluation improve the current policy  policy improvement policy iteration: policy evaluation:   backward calculation V π(s) =    π(a|s) a policy improvement:  from the Bellman optimality equation V(s) ← max Q™(s,a) A
policy degradation in value-based methods [Bartlett. An Introduction to Reinforcement Learning Theory: Value Function Methods.  Advanced Lectures on Machine Learning, LNAI 2600] r(2)=1 optimal policy: red V*(2) > V*(1) > 0 Φ(2)=1 let V(s) = wφ(s), to ensure V(2) > V(1), w < 0 as value function based method minimizes || V − V* || results in w > 0 sub-optimal policy,  better value ≠ better policy Policy search parameterized policy
Policy search direct objective functions
i=1 use samples to estimate the gradient (unbiased estimation)
Policy search advantages: effective in high-dimensional and continuous action space learn stochastic policies directly avoid policy degradation disadvantages: converge only to a local optimum high variance
actor-critic ∇ θJ(θ) ≈ E[∇ θ log π θ(α|s)Q w(s, α)] if w is a minimizer of E [(Q™®(s,a) — Qw(s,a))²] Learn policy (actor) and Q-value (critic) simultaneously baseline ∇ θ J(θ) = E[∇ θ log π θ (α|s)(Q π (s,a) — b(s))] advantage function: A™(s,a) = Q™(s,a) — V™(s) ∇ θJ(θ) = E[∇ θ log π θ(α|s)A π(s, α)] learn policy, Q and V simultaneously
nature policy gradient [Kakade. A Natural Policy Gradient. NIPS'01] functional policy gradient exp(Ψ(s,α)) πφ ( α | S ) p( Ï( s,a' )) Ψ t [Yu et al. Boosting nonparametric policies. AAMAS'16] parameter-level exploration θ ～ N [Sehnke et al.  Parameter-exploring policy gradients. Neural Networks'10] asynchronous gradient update [Mnih et al.  Asynchronous Methods for Deep Reinforcement Learning . ICML’16]
the non-convexity
too many local minima
value-function representation
policy representation π(s) =
NEAT+Q
Shimon Whiteson and Peter Stone. Evolutionary Function Approximation for Reinforcement Learning. Journal of Machine Learning Research, 7:877–917,
on Atari games freeway asterix
Matthew J. Hausknecht, Piyush Khandelwal, Risto Miikkulainen, Peter Stone:HyperNEAT-GGP: a hyperNEAT-based atari general game player. GECCO 2012: Issue: low-efficiency Batch sampling Online update batch mode: sequential mode: Yi-Qi Hu, Hong Qian, and Yang Yu. Sequential classification-based optimization for direct policy search. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI'17), San Francisco, CA, 2017, pp.2029-2035.
Yi-Qi Hu, Hong Qian, and Yang Yu. Sequential classification-based optimization for direct policy search. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI'17), San Francisco, CA, 2017, pp.2029-2035.

centralized
1: Input: Learning rate α , noise standard deviation σ , initial policy parameters θ 0 2:  for t = 0, 1, 2, . . . do Sample ει, . . . εn ～ N (0, I ) 3: Compute returns F i = F (θ t + σε i ) for i = 1, . . . , n 4: Set θ t+1 ← θ t + α π ∑ i=1 FiEi 5: 6:  end for time steps of ES to the top performance of TRPO

parallel
1: Input: Learning rate α , noise standard deviation σ , initial policy parameters θ 0 2:  Initialize: n workers with known random seeds, and initial parameters θο 3:  for t = 0, 1, 2, . . .  do 4: for each worker i = 1, . . . , n do 5: 6: Sample ε̣〜 N (0, I) Compute returns F i = F (θ t + σε i ) 7: end for 8: Send all scalar returns F i from each worker to every other worker 9: for each worker i = 1, . . . , n do 10: 11: Reconstruct all perturbations ε j for j = 1, . . . , n Set θ t+1 ← θ t + α → ∑ j=1 F j ε j end for 12: 13:  end for More issues to be solved Noisy evaluation: too many repetitions Large model: too large search space Long-term reward: too complex objective function Thanks for your time! Questions/comments?
37