Bayesian Algorithm for learning structure of dynamic bayesian networks from incomplete data

Bayesian Optimization CSC2541 - Topics in Machine LearningScalable and Flexible Models of UncertaintyUniversity of Toronto - Fall 2017Overview1.Bayesian Optimization of Machine Learning Algorithms2.Gaussian Process Optimization in the Bandit Setting3.Exploiting Structure for Bayesian OptimizationBayesian Optimization of Machine Learning Algorithms J. Snoek, A. Krause, H. Larochelle, and R.P. Adams (2012)Practical Bayesian Optimization of Machine Learning AlgorithmsJ. Snoek et al. (2015)Scalable Bayesian Optimization Using Deep Neural NetsPresentation by: Franco Lin, Tahmid Mehdi, Jason LiMotivationPerformance of Machine Learning algorithms are usually dependent on the choice of hyperparametersPicking the optimal hyperparameter values are hard-Ex. grid search, random search, etc.-Instead could we use a model to select which hyperparameters will be good next?Bayes Opt. of Machine Learning Algorithms-Bayesian Optimization uses all of the information from previous evaluations and performs some computation to determine the next point to try-If our model takes days to train, it would be beneficial to have a well structured way of selecting the next combination of hyperparameters to try-Bayesian Optimization is much better than a person finding a good combination of hyperparametersBayesian OptimizationIntuition:We want to find the peak of our true function (eg. accuracy as a function of hyperparameters)To find this peak, we will fit a Gaussian Process to our observed points and pick our next best point where we believe the maximum will be.This next point is determined by an acquisition function - that trades of exploration and exploitationBayesian Optimization TutorialBayesian Optimization Tutorialthat maximizes acquisition function Find the next best point xnBayesian Optimization TutorialEvaluate ƒ at the new observation xand update posteriornUpdate acquisition function from new posterior and find the next best pointAcquisition Function Intuition-We will use the acquisition functionProbability of Improvement (PI) asan example.-We want to find the point with thelargest area above our best value-This corresponds to the maximumof our acquisition functionAcquisition Functions-Guides the optimization by determining which point to observe next and is easier to optimize to find the next sample pointProbability of Improvement (PI)Expected Improvement (EI)GP-Upper/Lower Confidence Bound (GP-UCB/LCB)The Prior-Power of Gaussian Process depends on covariance function-For optimization, we don’t want kernels that produce unrealistically smooth sample functions-Automatic Relevance Determination (ARD) Matern 5/2 kernel is a good choiceKernel HyperparametersMarginalize over hyperparameters and compute integrated acquisition functionApproximate integral with Monte Carlo methodsConsiderations for Bayes Opt-Evaluating f may be time-consuming-Modern optimization methods should take advantage of multi-core/parallel programmingExpected Improvement per Second-Evaluating f will take longer in some regions of the parameter space-We want to pick points that are likely to be good and evaluated quickly -Let c(x) be the duration time to evaluate f(x)-Use GP to model ln[c(x)]-we can compute predicted expected inverse duration which allows us to obtain the EI per Second as a function of xParallelizing Bayes Opt-Can we determine which x to evaluate next, while other points are being evaluated?-Idea: Utilize tractable properties of GP to get Monte Carlo estimates of acquisition function under different results from pending function evaluationsConsider the case where N evaluations have completed, with data {xn ,yn}n=1N, and Jevaluations are pending {xj }j=1JParallelization Example-We’ve evaluated 3 observations and 2are pending {x 1,x 2}-Fit a model for each possible realizationof {f(x 1), f(x 2)}-Calculate acquisition for each model -Integrate all acquisitions over xResults●Branin-Hoo●Logistic Regression MNIST ●Online LDA●M3E●CNN CIFAR-10Logistic Regression - MNISTCIFAR-10●3-layer conv-net●Optimized over○Number of epochs○Learning rate○L2-norm constants ●Achieved state of the art○9.5% test errorGP Bayesian Optimization - Pros and Cons●Advantages○Computes the mean and variance●Disadvantages○Function evaluation is cubic on the number of inputsScalable Bayesian Optimization Using Deep Neural Networks●Replace a Gaussian Process with a Bayesian Neural Network●Use a deterministic neural network with Bayesian linear regression onthe last hidden layer●More accurately, use Bayesian linear regression with basis functions○DNN: R k -> R d○Bayesian linear regression: R d -> R○k is the dimensionality of the input, and d is the number of hidden units in the last layerBayesian Linear Regression●Still requires an inversion●Linear in the number of observations●Cubic in the basis function dimension or number of hidden units, DResultsGaussian Process Optimization in the Bandit SettingN. Srinivas, A. Krause, S. Kakade, and M. Seeger (2010)Gaussian process optimization in the bandit setting: No regret and experimental design Presentation by: Shadi Zabad, Wei Zhen Teoh, Shuja KhalidThe Bandits are Back!-We just learned about some exciting newtechniques for optimizing black box functions.Can we apply them to the classic multi-armedbandit problem?-In this case, we’d like to optimize the unknownreward function.Credit: D. Tolpin at ECAI 2012Cost-bounded Optimization-In the bandit setting, the optimization procedure is cost-sensitive: There’s a cost incurred each time we evaluate the function.-The cost is proportional to how far the point is from the point of maximum reward.-Therefore, we have to optimize the reward function while minimizing the cost incurred along the way.An Infinite Number of Arms-The multi-armed bandit algorithms and analyses we’ve seen so farassumed a discrete decision space (e.g. a decision space wherewe have K slot machines).-However, in Gaussian Process optimization, we’d like to considercontinuous decision spaces.-And in this domain, some of the theoretical analyses that wederived for discrete decision spaces can’t be extended in astraightforward manner.Credit: @Astrid, CrossValidatedMulti-armed Bandit Problem: Recap -The basic setting : We have a decision space that’sassociated with anunknown reward function .-Discrete examples: Slot machines at a casino, drug trials.-Continuous examples : Digging for oil or minerals, robotmotion planning.-In this setting, a “policy ” is a procedure for exploringthe decision space. An optimal policy is defined as aprocedure which minimizes a cost measure. The mostcommon cost measure is the “regret ”.Credit: Intelligent Motion Lab (Duke U)Credit: Gatis GribustsA Measure of Regret-In general terms, regret is defined as “the loss in reward due to not knowing” the maximum pointsbeforehand.-We can formalize this notion with 2 concepts:-Instantaneous regret (r t): the loss in reward at step t: r t = f(D max) - f(D t)-Cumulative regret (R T): the total loss in reward after T steps:R T = ∑r tMinimizing Regret: A Tradeoff-As we have seen before, we can define policies thatbalance exploration and exploitation. Some of thepolicies we’ve looked at are:-Epsilon-greedy-Thompson sampling-Upper Confidence Bound (UCB)-Some of these policies perform better than othersin minimizing the average regret over time.Average Regret = R T / TCredit: Russo et al., 2017Asymptotic Regret-We can also look at the cumulative or average regret measure as the number of iterations goes toinfinity.-An algorithm is said to be no-regret if its asymptoticcumulative regret rate is sublinear with respect to T (i.e. the number of iterations)sqrt(T) and log(T) are examples of sublinear regret rates w.r.t. T.Why is Asymptotic Regret Important?-In real world applications, we know neitherinstantaneous nor average regret. So, whyare we concerned with characterizing theirasymptotic behavior?-Answer: Bounds on the average regret tellus about the convergence rate (i.e. how fastwe approach the maximum point) of theoptimization algorithm.Credit: N. de Freitas et al., 2012Regret Bounds in Discrete Decision Spaces-In the previous lecture, we discussed asymptotic regret in discrete decision spaces where we have K slot machines or drug trials.-We also looked at theorems by Auer et al. that derive an upper bound on the regret rate for the UCB algorithm in discrete settings.Dani et al. 2008“In the traditional K-arm bandit literature, the regret is often characterized for a particular problem in terms of T, K, and problem dependent constants . In the K-arm bandit results of Auer et al. [2002], this problem dependent constant is the ‘gap’ between the loss of the best arm and the second best arm.”Regret Bounds in Continuous Decision Spaces-Dani et al.** extended Auer et al.’s theoretical results to continuous decision spaces and proved upper and lower regretbounds for the UCB algorithm.-However, their method places restrictions on the types of reward functions considered, primarily: The functions are defined overfinite-dimensional linear spaces.** Dani, V., Hayes, T. P., and Kakade, S. M. Stochastic linear optimization under bandit feedback. In COLT, 2008.Infinite-dimensional Functions-Srinivas et al. propose to relax some of the restrictionsof Dani et al.’s analysis and extend the results torandom, infinite-dimensional functions.-Earlier in the semester, we learned about a method forgenerating such classes of functions: GaussianProcesses.-Idea: Assuming the target reward function is sampledfrom a Gaussian Process, try to optimize it usingGP-UCB.-How to derive regret bounds for those classes ofCredit: Duvenaud, The Kernel Cookbook functions?Using Information Gain To Derive Regret BoundsInformation GainRecall Mackay (1992) paper: Information gain can be quantified as change in entropy In this context: Information gain =entropy in prior - entropy in posterior after y A sampled = H(f) - H( f | y A )= I(f; y A ), mutual information between f and observed y A=I(y A ; f) = H(y A ) - H( y A |f) = (log| 2I + K A |)/2 - (log| 2I |)/2 = (log|I + -2 K A |)/2Note:information gain depends on kernel of GP prior and input spaceCredit: Srinivas et al. 2010If our goal is just exploration ...Greedy Experimental Design Algorithm:Sequentially, findHowever the worse point weselect, the more penalty we get Credit: Srinivas et al. 2010GP - UCB to the rescueExplore ExploitCredit: Srinivas et al. 2010Maximum information GainDefinition:Maximum information gain after T data points sampled,This term will be used to quantify the regret bound for the algorithmRegret Bounds - Finite Domain Theorem 1:Assumptions:-Finite D- f sample of a GP with mean 0,-k(x, x’) of GP s.t. k(x,x) (variance) not greater than 1Then, by running GP-UCB for f withWe obtain: TAssuming some strictly sublinear T ...(we will verify later that this is achievable by choice of kernels),We can find some sublinear function f(T) bounding above P(R T curve lies below) is at least 1-f(T)Regret Bounds II - General Compact+Convex SpaceTheorem 2:Assumptions:- D compact and convex in [0,r]d,- f sample of a GP with mean 0,-k(x, x’) of GP s.t. k(x,x) (variance) not greater than 1-k(x,x’) s.t. f fulfills smoothness condition -- discussed nextThen, by running GP-UCB for f withWe obtain:Regret Bounds II ContinuedTheorem 2 requires f to fulfill:This holds for stationary kernels k(x,x’) = k(x-x’) which are 4-times differentiable: Squared Exponential Kernel Matern Kernels with v>2Credit: Srinivas et al. 2010Bounding Information Gain-- F is submodular function⇒T⇒ T SubmodularityThis holds if A constructed byGreedy Experiment Design Rule Credit: Krause, https://las.inf.ethz.ch/sfo/Bounding Information Gain ContinuedWe can bound the term by considering the worst allocation of the T samples under some relaxed greedy procedure (see appendix section C).In finite space D, this eventually gives us a bound in terms of the eigenvalues of the covariance matrix for all |D| points:The faster the spectrum decays, the slower the growth of the boundBounding Information Gain ContinuedCredit: Srinivas et al. 2010Bounding Information Gain ContinuedTheorem 5: Assume general compact and convex set D in R d , kernel k(x,x’)≤1:1.d- dimensional bayesian linear regression:2.Squared exponential kernel:3.Matern kernel (v>1) :Now recall the bound obtained for GP-UCB in theorem 2: Combining the two theorems we obtain the following (1-δ) upper confidence bound for the total regret, R T (up to polylog factors):With T = + Credit: Srinivas et al. 2010Results and DiscussionExperimental Setup●Synthetic and real sensor network data (traffic and temperature)used to illustrate the differences●Gaussian Processes - Upper Confidence Bound (GP-UCB) iscompared with various heuristics:○Expected Improvement (EI)○Most Probable Improvement (MPI)○Naive Methods (only mean or only variance)。

- 贝叶斯近似算法介绍全文共四篇示例，供读者参考第一篇示例：贝叶斯近似算法（Bayesian Approximation Algorithm）是一种基于贝叶斯统计推断原理的近似算法，通常用于解决模型复杂、数据量大的问题。

在机器学习领域中，贝叶斯方法是一种常见且有效的方法，它不仅可以用于分类、回归等监督学习任务，还可以应用于聚类、降维、推荐系统等无监督学习任务。

贝叶斯近似算法的核心思想是基于贝叶斯定理进行概率推断，通过对参数的后验分布进行近似推断，从而得到参数的估计结果。

与传统的最大似然估计方法相比，贝叶斯方法能够更好地利用先验知识，对参数的不确定性进行更合理的建模，同时还能够避免过拟合的问题。

在实际应用中，由于后验分布的计算通常是非常困难甚至不可行的，因此需要借助于贝叶斯近似算法来进行推断。

常见的贝叶斯近似算法包括马尔科夫链蒙特卡洛（MCMC）方法、变分推断方法、拉普拉斯近似方法等。

马尔可夫链蒙特卡洛方法是一种基于随机模拟的推断方法，通过构建马尔可夫链来模拟参数的后验分布。

通过多次迭代采样，最终得到参数的后验分布的近似值。

但是MCMC方法的计算复杂度较高，收敛速度较慢，在处理大规模数据时可能会面临挑战。

变分推断方法是另一种常见的贝叶斯近似算法，它通过最优化一个参数化的分布来近似真实的后验分布。

变分推断方法通常会引入一些近似假设，例如独立性假设、指数族假设等，从而简化推断的计算复杂度。

变分推断方法的优点是计算效率高，但是可能会引入一定的偏差。

拉普拉斯近似方法是一种基于高斯分布的近似推断方法，通过在后验分布的峰值处进行局部近似，得到参数的估计结果。

拉普拉斯近似方法通常适用于后验分布近似是单峰分布的情况，当后验分布是多峰分布时可能会出现不准确的情况。

贝叶斯近似算法是一种在处理复杂、大规模数据时非常有效的推断方法。

通过合理地选择适当的近似算法，结合先验知识和数据信息，可以得到更加准确和稳健的模型参数估计结果。

贝叶斯算法基础学习
贝叶斯算法是基于概率论的一种常用的统计学方法，它由英国统计学家Thomas Bayes所发明，于1763年提出的“贝叶斯定理”，是概率推断的基础。

贝叶斯算法主要通过概率的方式来计算一些事件发生的可能性，最终得出的结果在预测不同的结果时会有不同的可能性。

贝叶斯算法的基本原理是：将已经观察到的事实（也称为条件数据）作为先验概率来计算每种可能解释结果的后验概率，以及所有可能解释结果的最终概率。

贝叶斯算法就是根据先验概率和后验概率来确定可能的结果。

最终的结果由先验概率和后验概率之间的函数来确定，而且各种可能的结果的概率值可以通过贝叶斯定理来确定，其中，先验概率是已经知道的事实，而后验概率则是根据先验概率和此事实发生的可能性来确定的。

贝叶斯算法的主要用途是分类问题，它可以帮助我们根据现有的数据计算每种可能解释结果的可能性，以及所有可能解释结果中，哪一种最有可能是正确的。

它还可以帮助我们根据现有的结果，来判断哪些假设是有可能的，哪些不太可能。

%学习 bnet3 = learn_params(bnet2,data);
实验结果： 手动给出的CPT nsamples=20 nsamples=200
分区 机器学习 的第 3 页
nsamples=200 nsamples=2000 可以看出，随着训练样本数的增加，学习到的条件概率表越来越逼近于手动给出的条件概率表。
rand('state',seed); bnet2.CPD{C} = tabular_CPD(bnet2,C); bnet2.CPD{S} = tabular_CPD(bnet2,S); bnet2.CPD{R} = tabular_CPD(bnet2,R); bnet2.CPD{W} = tabular_CPD(bnet2,W);
%计算单个节点后验概率，即进行推理 marg1 = marginal_nodes(engine,S); marg1.T %计算对节点联合后验概率 marg2 = marginal_nodes(engine,[S R W]); marg2.T %给出“软证据”，即节点的可能分布概率情况下的推理 evidence{R} = []; soft_evidence{R}=[0.6 0.4]; [engine, loglike] = enter_evidence(engine,evidence,'soft',soft_evidence); marg3 = marginal_nodes(engine,S); marg3.T 实验结果: 1.贝叶斯网络 2.单个节点后验概率 3.多个节点后验概率 4.soft_evidence情况下的后验概率 2. 焚化炉厂废物排放模型建立及推理：（包含离散变量和连续变量） 这个实验与第一个实验不同的地方就是它所建立的贝叶斯网中的节点变量包含连续变量，在建立 条件概率概率表时会有所不同，离散变量使用CPD构造器tabular_CPD,连续变量使用 gaussian_CPD。这里指给出这一部分的代码： bnet.CPD{B} = tabular_CPD(bnet,B,'CPT',[0.85 0.15]);