Bayesian Optimization - Revision history

Deepakorani: /* Acquisition Function */

2021-12-20T00:23:38Z

Acquisition Function

← Older revision		Revision as of 20:23, 19 December 2021
Line 61:		Line 61:

	====Acquisition Function====		====Acquisition Function====
	The second component of Bayesian Optimization is the Acquistion Function.The role of the acquisition function is to guide the search for the optimum<ref>E. Brochu, V. M. Cora, and N. De Freitas, “arXiv : 1012 . 2599v1 [ cs . LG ] 12 Dec 2010 A Tutorial on Bayesian Optimization of Expensive Cost Functions , with Application to Active User Modeling and Hierarchical Reinforcement Learning,” 2010.</ref>. Typically, acquisition functions are defined such that high acquisition corresponds to potentially high values of the objective function, whether because the prediction is high, the uncertainty is great, or both. Maximizing the acquisition function is used to select the next point at which to evaluate the function. Hence the main goal is to sample <math> f </math> at <math> \arg\max </math> <math>~~x_u~~(x\|D)</math> , where <math> u~~(·)~~ </math> is the generic symbol for an acquisition function.		The second component of Bayesian Optimization is the Acquistion Function.The role of the acquisition function is to guide the search for the optimum<ref>E. Brochu, V. M. Cora, and N. De Freitas, “arXiv : 1012 . 2599v1 [ cs . LG ] 12 Dec 2010 A Tutorial on Bayesian Optimization of Expensive Cost Functions , with Application to Active User Modeling and Hierarchical Reinforcement Learning,” 2010.</ref>. Typically, acquisition functions are defined such that high acquisition corresponds to potentially high values of the objective function, whether because the prediction is high, the uncertainty is great, or both. Maximizing the acquisition function is used to select the next point at which to evaluate the function. Hence the main goal is to sample <math> f </math> at <math> \arg\max </math> <math>x_{u(x\|D)}</math> , where <math> u </math> is the generic symbol for an acquisition function.

	A good acquisition function should trade off exploration and exploitation. Two typically used acquisition functions are the ''Probability of Improvement (PI)'' and the ''Expected Improvement (EI)'' . In PI, the probability that sampling a given data-point, <math> x </math>, improves over the current best observation is maximized. One problem with the approach taken in PI is that it will, by its nature, prefer a point with a small but certain improvement over one which offers a far greater improvement, but at a slightly higher risk. In order to combat this effect, EI proposes maximizing the expected improvement over the current best known point.<ref>D. Jasrasaria and E. O. Pyzer-knapp, “Dynamic Control of Explore / Exploit Trade-Off In Bayesian Optimization,” no. July, 2018.</ref>EI has been shown to have strong theoretical guarantees and empirical effectiveness<ref>B. J. Snoek, H. Larochelle, and R. P. Adams, “PRACTICAL BAYESIAN OPTIMIZATION OF MACHINE LEARNING,” pp. 1–12.</ref> , and is often used as the acquistion function as a baseline. The formulations of common acquisition functions, Upper Bound Confidence, Probability of Improvement and Expected Improvement are defined below:		A good acquisition function should trade off exploration and exploitation. Two typically used acquisition functions are the ''Probability of Improvement (PI)'' and the ''Expected Improvement (EI)'' . In PI, the probability that sampling a given data-point, <math> x </math>, improves over the current best observation is maximized. One problem with the approach taken in PI is that it will, by its nature, prefer a point with a small but certain improvement over one which offers a far greater improvement, but at a slightly higher risk. In order to combat this effect, EI proposes maximizing the expected improvement over the current best known point.<ref>D. Jasrasaria and E. O. Pyzer-knapp, “Dynamic Control of Explore / Exploit Trade-Off In Bayesian Optimization,” no. July, 2018.</ref>EI has been shown to have strong theoretical guarantees and empirical effectiveness<ref>B. J. Snoek, H. Larochelle, and R. P. Adams, “PRACTICAL BAYESIAN OPTIMIZATION OF MACHINE LEARNING,” pp. 1–12.</ref> , and is often used as the acquistion function as a baseline. The formulations of common acquisition functions, Upper Bound Confidence, Probability of Improvement and Expected Improvement are defined below:

Deepakorani: /* Acquisition Function */

2021-12-20T00:22:58Z

Acquisition Function

← Older revision		Revision as of 20:22, 19 December 2021
Line 61:		Line 61:

	====Acquisition Function====		====Acquisition Function====
	The second component of Bayesian Optimization is the Acquistion Function.The role of the acquisition function is to guide the search for the optimum<ref>E. Brochu, V. M. Cora, and N. De Freitas, “arXiv : 1012 . 2599v1 [ cs . LG ] 12 Dec 2010 A Tutorial on Bayesian Optimization of Expensive Cost Functions , with Application to Active User Modeling and Hierarchical Reinforcement Learning,” 2010.</ref>. Typically, acquisition functions are defined such that high acquisition corresponds to potentially high values of the objective function, whether because the prediction is high, the uncertainty is great, or both. Maximizing the acquisition function is used to select the next point at which to evaluate the function. Hence the main goal is to sample <math> f </math> at <math> \arg\max </math> <~~sub~~>~~x</sub>u~~(x\|D) , where <math> u(·) </math> is the generic symbol for an acquisition function.		The second component of Bayesian Optimization is the Acquistion Function.The role of the acquisition function is to guide the search for the optimum<ref>E. Brochu, V. M. Cora, and N. De Freitas, “arXiv : 1012 . 2599v1 [ cs . LG ] 12 Dec 2010 A Tutorial on Bayesian Optimization of Expensive Cost Functions , with Application to Active User Modeling and Hierarchical Reinforcement Learning,” 2010.</ref>. Typically, acquisition functions are defined such that high acquisition corresponds to potentially high values of the objective function, whether because the prediction is high, the uncertainty is great, or both. Maximizing the acquisition function is used to select the next point at which to evaluate the function. Hence the main goal is to sample <math> f </math> at <math> \arg\max </math> <math>x_u(x\|D)</math> , where <math> u(·) </math> is the generic symbol for an acquisition function.

	A good acquisition function should trade off exploration and exploitation. Two typically used acquisition functions are the ''Probability of Improvement (PI)'' and the ''Expected Improvement (EI)'' . In PI, the probability that sampling a given data-point, <math> x </math>, improves over the current best observation is maximized. One problem with the approach taken in PI is that it will, by its nature, prefer a point with a small but certain improvement over one which offers a far greater improvement, but at a slightly higher risk. In order to combat this effect, EI proposes maximizing the expected improvement over the current best known point.<ref>D. Jasrasaria and E. O. Pyzer-knapp, “Dynamic Control of Explore / Exploit Trade-Off In Bayesian Optimization,” no. July, 2018.</ref>EI has been shown to have strong theoretical guarantees and empirical effectiveness<ref>B. J. Snoek, H. Larochelle, and R. P. Adams, “PRACTICAL BAYESIAN OPTIMIZATION OF MACHINE LEARNING,” pp. 1–12.</ref> , and is often used as the acquistion function as a baseline. The formulations of common acquisition functions, Upper Bound Confidence, Probability of Improvement and Expected Improvement are defined below:		A good acquisition function should trade off exploration and exploitation. Two typically used acquisition functions are the ''Probability of Improvement (PI)'' and the ''Expected Improvement (EI)'' . In PI, the probability that sampling a given data-point, <math> x </math>, improves over the current best observation is maximized. One problem with the approach taken in PI is that it will, by its nature, prefer a point with a small but certain improvement over one which offers a far greater improvement, but at a slightly higher risk. In order to combat this effect, EI proposes maximizing the expected improvement over the current best known point.<ref>D. Jasrasaria and E. O. Pyzer-knapp, “Dynamic Control of Explore / Exploit Trade-Off In Bayesian Optimization,” no. July, 2018.</ref>EI has been shown to have strong theoretical guarantees and empirical effectiveness<ref>B. J. Snoek, H. Larochelle, and R. P. Adams, “PRACTICAL BAYESIAN OPTIMIZATION OF MACHINE LEARNING,” pp. 1–12.</ref> , and is often used as the acquistion function as a baseline. The formulations of common acquisition functions, Upper Bound Confidence, Probability of Improvement and Expected Improvement are defined below:

Deepakorani: /* Acquisition Function */

2021-12-20T00:21:55Z

Acquisition Function

← Older revision		Revision as of 20:21, 19 December 2021
Line 61:		Line 61:

	====Acquisition Function====		====Acquisition Function====
	The second component of Bayesian Optimization is the Acquistion Function.The role of the acquisition function is to guide the search for the optimum<ref>E. Brochu, V. M. Cora, and N. De Freitas, “arXiv : 1012 . 2599v1 [ cs . LG ] 12 Dec 2010 A Tutorial on Bayesian Optimization of Expensive Cost Functions , with Application to Active User Modeling and Hierarchical Reinforcement Learning,” 2010.</ref>. Typically, acquisition functions are defined such that high acquisition corresponds to potentially high values of the objective function, whether because the prediction is high, the uncertainty is great, or both. Maximizing the acquisition function is used to select the next point at which to evaluate the function. Hence the main goal is to sample <math> f </math> at <math> \arg\max </math> <sub>x</sub>u(x\|D)~~'''''~~,~~'''~~ where ''u(·)'' is the generic symbol for an acquisition function.		The second component of Bayesian Optimization is the Acquistion Function.The role of the acquisition function is to guide the search for the optimum<ref>E. Brochu, V. M. Cora, and N. De Freitas, “arXiv : 1012 . 2599v1 [ cs . LG ] 12 Dec 2010 A Tutorial on Bayesian Optimization of Expensive Cost Functions , with Application to Active User Modeling and Hierarchical Reinforcement Learning,” 2010.</ref>. Typically, acquisition functions are defined such that high acquisition corresponds to potentially high values of the objective function, whether because the prediction is high, the uncertainty is great, or both. Maximizing the acquisition function is used to select the next point at which to evaluate the function. Hence the main goal is to sample <math> f </math> at <math> \arg\max </math> <sub>x</sub>u(x\|D) , where <math> u(·) </math> is the generic symbol for an acquisition function.

	A good acquisition function should trade off exploration and exploitation. Two typically used acquisition functions are the ''Probability of Improvement (PI)'' and the ''Expected Improvement (EI)'' . In PI, the probability that sampling a given data-point, <math> x </math>, improves over the current best observation is maximized. One problem with the approach taken in PI is that it will, by its nature, prefer a point with a small but certain improvement over one which offers a far greater improvement, but at a slightly higher risk. In order to combat this effect, EI proposes maximizing the expected improvement over the current best known point.<ref>D. Jasrasaria and E. O. Pyzer-knapp, “Dynamic Control of Explore / Exploit Trade-Off In Bayesian Optimization,” no. July, 2018.</ref>EI has been shown to have strong theoretical guarantees and empirical effectiveness<ref>B. J. Snoek, H. Larochelle, and R. P. Adams, “PRACTICAL BAYESIAN OPTIMIZATION OF MACHINE LEARNING,” pp. 1–12.</ref> , and is often used as the acquistion function as a baseline. The formulations of common acquisition functions, Upper Bound Confidence, Probability of Improvement and Expected Improvement are defined below:		A good acquisition function should trade off exploration and exploitation. Two typically used acquisition functions are the ''Probability of Improvement (PI)'' and the ''Expected Improvement (EI)'' . In PI, the probability that sampling a given data-point, <math> x </math>, improves over the current best observation is maximized. One problem with the approach taken in PI is that it will, by its nature, prefer a point with a small but certain improvement over one which offers a far greater improvement, but at a slightly higher risk. In order to combat this effect, EI proposes maximizing the expected improvement over the current best known point.<ref>D. Jasrasaria and E. O. Pyzer-knapp, “Dynamic Control of Explore / Exploit Trade-Off In Bayesian Optimization,” no. July, 2018.</ref>EI has been shown to have strong theoretical guarantees and empirical effectiveness<ref>B. J. Snoek, H. Larochelle, and R. P. Adams, “PRACTICAL BAYESIAN OPTIMIZATION OF MACHINE LEARNING,” pp. 1–12.</ref> , and is often used as the acquistion function as a baseline. The formulations of common acquisition functions, Upper Bound Confidence, Probability of Improvement and Expected Improvement are defined below:

Deepakorani at 00:18, 20 December 2021

2021-12-20T00:18:11Z

← Older revision		Revision as of 20:18, 19 December 2021
Line 147:		Line 147:

	Results for the first 8 iterations for the Gaussian Process Regression and Acquistion functions are shown in Figure 2 and Figure 3. As one of the assumptions stated earlier was that the observation contain noise, it is impossible to converge to the ground truth solution.However, as seen in Figure 2 an 3; with a limited budget of 8 evaluations; BO has converged close to the global minimum at <math> x^\star = 0.75725 </math>		Results for the first 8 iterations for the Gaussian Process Regression and Acquistion functions are shown in Figure 2 and Figure 3. As one of the assumptions stated earlier was that the observation contain noise, it is impossible to converge to the ground truth solution.However, as seen in Figure 2 an 3; with a limited budget of 8 evaluations; BO has converged close to the global minimum at <math> x^\star = 0.75725 </math>
	* [[File:Screen Shot 2021-12-19 at 6.15.29 PM.png\|thumb\|'''Figure 2''': GPR and Acquistion Function plots for first four time steps]]		[[File:Screen Shot 2021-12-19 at 6.15.29 PM.png\|thumb\|'''Figure 2''': GPR and Acquistion Function plots for first four time steps]]
	[[File:Screen Shot 2021-12-19 at 6.15.44 PM.png\|thumb\|'''Figure 4''': GPR and Acquistion Function for next four iterations]]		[[File:Screen Shot 2021-12-19 at 6.15.44 PM.png\|thumb\|'''Figure 4''': GPR and Acquistion Function for next four iterations]]

Deepakorani at 00:10, 20 December 2021

2021-12-20T00:10:41Z

← Older revision		Revision as of 20:10, 19 December 2021
Line 147:		Line 147:

	Results for the first 8 iterations for the Gaussian Process Regression and Acquistion functions are shown in Figure 2 and Figure 3. As one of the assumptions stated earlier was that the observation contain noise, it is impossible to converge to the ground truth solution.However, as seen in Figure 2 an 3; with a limited budget of 8 evaluations; BO has converged close to the global minimum at <math> x^\star = 0.75725 </math>		Results for the first 8 iterations for the Gaussian Process Regression and Acquistion functions are shown in Figure 2 and Figure 3. As one of the assumptions stated earlier was that the observation contain noise, it is impossible to converge to the ground truth solution.However, as seen in Figure 2 an 3; with a limited budget of 8 evaluations; BO has converged close to the global minimum at <math> x^\star = 0.75725 </math>
	[[File:Screen Shot 2021-12-19 at 6.15.29 PM.png\|thumb\|'''Figure 2''': GPR and Acquistion Function plots for first four time steps]]		* [[File:Screen Shot 2021-12-19 at 6.15.29 PM.png\|thumb\|'''Figure 2''': GPR and Acquistion Function plots for first four time steps]]
	[[File:Screen Shot 2021-12-19 at 6.15.44 PM.png\|thumb\|'''Figure 4''': GPR and Acquistion Function for next four iterations]]		[[File:Screen Shot 2021-12-19 at 6.15.44 PM.png\|thumb\|'''Figure 4''': GPR and Acquistion Function for next four iterations]]

Deepakorani: /* Results and Running the Optimization */

2021-12-20T00:09:15Z

Results and Running the Optimization

← Older revision		Revision as of 20:09, 19 December 2021
Line 146:		Line 146:
	Evaluate <math> f(x_{n+1})</math> and update the posterior, until convergence.		Evaluate <math> f(x_{n+1})</math> and update the posterior, until convergence.

	Results for the first 8 iterations for the Gaussian Process Regression and Acquistion functions are shown in Figure 2 and Figure 3 ~~below~~. As one of the assumptions stated earlier was that the observation contain noise, it is impossible to converge to the ground truth solution.However, as seen in Figure 2 an 3; with a limited budget of 8 evaluations; BO has converged close to the global minimum at <math> x^\star = 0.75725 </math>		Results for the first 8 iterations for the Gaussian Process Regression and Acquistion functions are shown in Figure 2 and Figure 3. As one of the assumptions stated earlier was that the observation contain noise, it is impossible to converge to the ground truth solution.However, as seen in Figure 2 an 3; with a limited budget of 8 evaluations; BO has converged close to the global minimum at <math> x^\star = 0.75725 </math>
	[[File:Screen Shot 2021-12-19 at 6.15.29 PM.png\|thumb\|'''Figure 2''': GPR and Acquistion Function plots for first four time steps]]		[[File:Screen Shot 2021-12-19 at 6.15.29 PM.png\|thumb\|'''Figure 2''': GPR and Acquistion Function plots for first four time steps]]
	[[File:Screen Shot 2021-12-19 at 6.15.44 PM.png\|thumb\|'''Figure 4''': GPR and Acquistion Function for next four iterations]]		[[File:Screen Shot 2021-12-19 at 6.15.44 PM.png\|thumb\|'''Figure 4''': GPR and Acquistion Function for next four iterations]]

Deepakorani: /* Objective Function */

2021-12-20T00:02:57Z

Objective Function

← Older revision		Revision as of 20:02, 19 December 2021
Line 114:		Line 114:
	The objective function for this example is a simple function defined below. The objective function has both a local and a global minimum as seen in Figure 1. The global minimum is at <math> x^\star = 0.75725 </math>		The objective function for this example is a simple function defined below. The objective function has both a local and a global minimum as seen in Figure 1. The global minimum is at <math> x^\star = 0.75725 </math>
	<math> f(x) = (6x - 2)^2 </math> <math> sin(12x-4) </math> ,		<math> f(x) = (6x - 2)^2 </math> <math> sin(12x-4) </math> ,
	<math> x \epsilon [0,1] </math>		<math> x \epsilon [0,1] </math>

	[[File:B6B598F0-7339-48F5-8799-C2384A243D24.jpg\|thumb\|'''Figure 1''' : Objective Function :		[[File:B6B598F0-7339-48F5-8799-C2384A243D24.jpg\|thumb\|'''Figure 1''' : Objective Function :

Deepakorani: /* Define Acquistion Function */

2021-12-20T00:02:22Z

Define Acquistion Function

← Older revision		Revision as of 20:02, 19 December 2021
Line 134:		Line 134:
	For this problem, the acquisition function used is the Lower Confidence Bound acquisition function due to its simplicity and easy interpretability.		For this problem, the acquisition function used is the Lower Confidence Bound acquisition function due to its simplicity and easy interpretability.

	The acquisition function is defined as :		The Lower Confidence Bound acquisition function is defined as :

	<math> \alpha(x) = \mu(x) - \kappa\sigma(x) </math>		<math> \alpha(x) = \mu(x) - \kappa\sigma(x) </math>

	Here in <math> \mu(x) </math> and <math> \sigma(x) </math> are the mean and square root variance of the posterior at point <math> x </math>		Here in <math> \mu(x) </math> and <math> \sigma(x) </math> are the mean and square root variance of the posterior at point <math> x </math>

	===Results and Running the Optimization===		===Results and Running the Optimization===

Deepakorani: /* Acquisition Function */

2021-12-20T00:01:26Z

Acquisition Function

← Older revision		Revision as of 20:01, 19 December 2021
Line 63:		Line 63:
	The second component of Bayesian Optimization is the Acquistion Function.The role of the acquisition function is to guide the search for the optimum<ref>E. Brochu, V. M. Cora, and N. De Freitas, “arXiv : 1012 . 2599v1 [ cs . LG ] 12 Dec 2010 A Tutorial on Bayesian Optimization of Expensive Cost Functions , with Application to Active User Modeling and Hierarchical Reinforcement Learning,” 2010.</ref>. Typically, acquisition functions are defined such that high acquisition corresponds to potentially high values of the objective function, whether because the prediction is high, the uncertainty is great, or both. Maximizing the acquisition function is used to select the next point at which to evaluate the function. Hence the main goal is to sample <math> f </math> at <math> \arg\max </math> <sub>x</sub>u(x\|D)''''',''' where ''u(·)'' is the generic symbol for an acquisition function.		The second component of Bayesian Optimization is the Acquistion Function.The role of the acquisition function is to guide the search for the optimum<ref>E. Brochu, V. M. Cora, and N. De Freitas, “arXiv : 1012 . 2599v1 [ cs . LG ] 12 Dec 2010 A Tutorial on Bayesian Optimization of Expensive Cost Functions , with Application to Active User Modeling and Hierarchical Reinforcement Learning,” 2010.</ref>. Typically, acquisition functions are defined such that high acquisition corresponds to potentially high values of the objective function, whether because the prediction is high, the uncertainty is great, or both. Maximizing the acquisition function is used to select the next point at which to evaluate the function. Hence the main goal is to sample <math> f </math> at <math> \arg\max </math> <sub>x</sub>u(x\|D)''''',''' where ''u(·)'' is the generic symbol for an acquisition function.

	A good acquisition function should trade off exploration and exploitation. Two typically used acquisition functions are the ''Probability of Improvement (PI)'' and the ''Expected Improvement (EI)'' . In PI, the probability that sampling a given data-point, x, improves over the current best observation is maximized. One problem with the approach taken in PI is that it will, by its nature, prefer a point with a small but certain improvement over one which offers a far greater improvement, but at a slightly higher risk. In order to combat this effect, EI proposes maximizing the expected improvement over the current best known point.<ref>D. Jasrasaria and E. O. Pyzer-knapp, “Dynamic Control of Explore / Exploit Trade-Off In Bayesian Optimization,” no. July, 2018.</ref>EI has been shown to have strong theoretical guarantees and empirical effectiveness<ref>B. J. Snoek, H. Larochelle, and R. P. Adams, “PRACTICAL BAYESIAN OPTIMIZATION OF MACHINE LEARNING,” pp. 1–12.</ref> , and is often used as the acquistion function as a baseline. The formulations of common acquisition functions, Upper Bound Confidence, Probability of Improvement and Expected Improvement are defined below:		A good acquisition function should trade off exploration and exploitation. Two typically used acquisition functions are the ''Probability of Improvement (PI)'' and the ''Expected Improvement (EI)'' . In PI, the probability that sampling a given data-point, <math> x </math>, improves over the current best observation is maximized. One problem with the approach taken in PI is that it will, by its nature, prefer a point with a small but certain improvement over one which offers a far greater improvement, but at a slightly higher risk. In order to combat this effect, EI proposes maximizing the expected improvement over the current best known point.<ref>D. Jasrasaria and E. O. Pyzer-knapp, “Dynamic Control of Explore / Exploit Trade-Off In Bayesian Optimization,” no. July, 2018.</ref>EI has been shown to have strong theoretical guarantees and empirical effectiveness<ref>B. J. Snoek, H. Larochelle, and R. P. Adams, “PRACTICAL BAYESIAN OPTIMIZATION OF MACHINE LEARNING,” pp. 1–12.</ref> , and is often used as the acquistion function as a baseline. The formulations of common acquisition functions, Upper Bound Confidence, Probability of Improvement and Expected Improvement are defined below:

	=====Upper Bound Confidence=====		=====Upper Bound Confidence=====

Deepakorani: /* Results and Running the Optimization */

2021-12-19T23:53:48Z

Results and Running the Optimization

← Older revision		Revision as of 19:53, 19 December 2021
Line 146:		Line 146:
	Evaluate <math> f(x_{n+1})</math> and update the posterior, until convergence.		Evaluate <math> f(x_{n+1})</math> and update the posterior, until convergence.

	Results for the first 8 iterations for the Gaussian Process Regression and Acquistion functions are shown in Figure 2 and Figure 3 below. As one of the assumptions stated earlier was that the observation contain noise, it is impossible to converge to the ground truth solution.However, as seen in Figure 2 an 3; with a limited budget of 8 evaluations; BO has converged close to the global minimum at <math> x^\star = 0.75725 <\math>		Results for the first 8 iterations for the Gaussian Process Regression and Acquistion functions are shown in Figure 2 and Figure 3 below. As one of the assumptions stated earlier was that the observation contain noise, it is impossible to converge to the ground truth solution.However, as seen in Figure 2 an 3; with a limited budget of 8 evaluations; BO has converged close to the global minimum at <math> x^\star = 0.75725 </math>
	[[File:Screen Shot 2021-12-19 at 6.15.29 PM.png\|thumb\|'''Figure 2''': GPR and Acquistion Function plots for first four time steps]]		[[File:Screen Shot 2021-12-19 at 6.15.29 PM.png\|thumb\|'''Figure 2''': GPR and Acquistion Function plots for first four time steps]]
	[[File:Screen Shot 2021-12-19 at 6.15.44 PM.png\|thumb\|'''Figure 4''': GPR and Acquistion Function for next four iterations]]		[[File:Screen Shot 2021-12-19 at 6.15.44 PM.png\|thumb\|'''Figure 4''': GPR and Acquistion Function for next four iterations]]