Performance Measure Regret:online prediction as good as the best offline model T Reget,) f:(w) cumulative loss of the w∈W best offline model t=1 Dynamic Regret optimal model changes in non-stationary environments T D-Regreti(u,…,ur)efi(v)-∑f(u,) t=1 allow changing comparators The comparators u,...,ur essentially depict the underlying(unknown)distributions of all rounds. ·stationary environments:ut=w,∈argminwew∑Z1fi(w) piecewise-stationary environments:ut-w!for a stationary interval t Zk Peng Zhao(Nanjing University) 11
Peng Zhao (Nanjing University) 11 Performance Measure Regret: online prediction as good as the best offline model cumulative loss of the best offline model Dynamic Regret optimal model changes in non-stationary environments allow changing comparators
Fundamental challenge T D-Regret(u,·,ur)=∑fiw)-∑f(e) t三1 t=1 Key difficulty:the uncertainty due to unknown environmental changes. Basic idea:Ensemble Methods Ensemble Methods Protocol:combine multiple base base-learner 1 learners to achieve robustness base-learner 2 Advantage:achieve more robust combiner ←output results under uncertain or even Zhi-Hua Zhou.Ensemble Methods: changing environments base-learner N Foundations and Algorithms. Chapman Hall/CRC,Jun.2012 Peng Zhao(Nanjing University) 12
Peng Zhao (Nanjing University) 12 Fundamental Challenge Key difficulty: the uncertainty due to unknown environmental changes. Zhi-Hua Zhou. Ensemble Methods: Foundations and Algorithms. Chapman & Hall/CRC, Jun. 2012. • Protocol: combine multiple base learners to achieve robustness • Advantage: achieve more robust results under uncertain or even changing environments Basic idea: Ensemble Methods
Online Ensemble(在线集成) Basic Components (1)base learner:an online learner to cope with a certain amount of non-stationarity (2)schedule:a set of parameters for initiating base learners that encourage diversity (3)meta learner:an expert-tracking learner that can combine base learners'decisions surrogate correction 图图凰遛 step size covering specification base learner schedule meta learner Peng Zhao (Nanjing University) 13
Peng Zhao (Nanjing University) 13 Online Ensemble (在线集成) Basic Components (1) base learner: an online learner to cope with a certain amount of non-stationarity (2) schedule: a set of parameters for initiating base learners that encourage diversity (3) meta learner: an expert-tracking learner that can combine base learners’ decisions base learner schedule meta learner step size specification surrogate correction covering …
收鲁条 Deploying Online Ensemble We will showcase that properly deploying online ensemble can effectively resolve several important online learning problems. Dynamic Regret of Bandit Convex Optimization Problem-dependent Dynamic Regret Peng Zhao (Nanjing University) 14
Peng Zhao (Nanjing University) 14 Deploying Online Ensemble We will showcase that properly deploying online ensemble can effectively resolve several important online learning problems. • Dynamic Regret of Bandit Convex Optimization • Problem-dependent Dynamic Regret
殿细 Deploying Online Ensemble We will showcase that properly deploying online ensemble can effectively resolve several important online learning problems. Dynamic Regret of Bandit Convex Optimization Problem-dependent Dynamic Regret Peng Zhao (Nanjing University) 15
Peng Zhao (Nanjing University) 15 Deploying Online Ensemble We will showcase that properly deploying online ensemble can effectively resolve several important online learning problems. • Dynamic Regret of Bandit Convex Optimization • Problem-dependent Dynamic Regret