text:
# Targeted ARP packets getting forward to broadcast

Hi all,

I've been working on a project that attempts to use ARP spoofing / poisoning for less nefarious purposes in the home security world (e.g. Circle and Firewalla). I've been observing a behavior that I can't seem to pin down and was hoping someone might be able to help me understand better what is going on.

I produce ARP packets that target specific devices on the network to spoof, and can observe expected packets in Wireshark like this from my laptop:

b8:27:eb:19:f1:1f b8:27:eb:19:f1:1f f0:18:98:14:2a:51 ARP 42 192.168.11.1 is at b8:27:eb:19:f1:1f

These packets are produced using ScaPy, and we do sometimes produce multiple of them at a time and send them out serially. However, eventually (there is always a time delay between it working as expected initially and then acting up), I start to identify packets produced by the spoofing machine that are ending up not at the target but instead broadcast to the entire network:

b8:27:eb:19:f1:1f b8:27:eb:19:f1:1f ff:ff:ff:ff:ff:ff ARP 60 192.168.11.1 is at b8:27:eb:19:f1:1f

These packets that end up at broadcast will still list the ARP layer with the correct sender and destination information:

Address Resolution Protocol (reply)
Hardware type: Ethernet (1)
Hardware size: 6
Protocol size: 4

But at the Ethernet layer I'm seeing broadcast as the Destination instead of the MAC of the true target:

Ethernet II, Src: b8:27:eb:19:f1:1f, Dst: ff:ff:ff:ff:ff:ff
Destination: ff:ff:ff:ff:ff:ff
Source: b8:27:eb:19:f1:1f
Type: ARP (0x0806)

I'm hoping someone can help me understand how these broadcasts that aren't explicitly sent to broadcast are ending up there anyway - is this an expected behavior, maybe for devices that aren't available to successfully receive the packet that was sent out? Is this behavior different by router model / manufacturer or expected based on the protocol and is otherwise universal? The current setup is running through a DD-WRT-based router. What's more, is there any way to prevent this from happening automatically?

~Michael

edit retag close merge delete

Could this be an issue in your networking stack?

( 2021-02-12 16:12:13 +0000 )edit

Are they flagged as Gratuitous ARP in Wireshark?

( 2021-02-12 16:40:54 +0000 )edit

Do you explicitly set the destination MAC in scapy and it is getting overwritten?

( 2021-02-12 17:33:49 +0000 )edit

• @hugo.vanderkooij - by networking stack do you mean on the machine sending the ARPs (rather than the networking stack on the router)? It's certainly possible, but it isn't a hard problem - as in, it starts by acting correctly and then devolves. The device sending the ARPs is an embedded Linux device run on a Raspberry Pi 3 for the time being.

• @Chuckc they are not flagged as such, though that's effectively what they are. They're type-2 ARP replies that haven't been requested.

• @Bob Jones That's correct, the destination MAC is explicitly set in scapy and is overwritten eventually. We get minutes of proper, targeted ARPs sent before they devolve and are forwarded to broadcast. I've been suspicious that this might be particularly true for devices that don't always respond to pings and ARPs (like mobile devices that turn wifi ...

(more)
( 2021-02-12 18:21:42 +0000 )edit

Did you isolate the source of these? Is your RaspberryPI sending them? Or is another entity on the network sending them? Sniffing in various locations should narrow down the source.

( 2021-02-12 18:42:49 +0000 )edit


text:
Browse Questions

# Prove that $\int_0^a f(x)dx = \int_0^a f(a-x)dx.$ Using it, evaluate $\int_0^2 x\sqrt {2-x} dx.$

Can you answer this question?

format: plain


text:
# Quantum mechanics formalism and C*-algebras

Many authors (e.g Landsman, Gleason) have stated that in quantum mechanics, the observables of a system can be taken to be the self-adjoint elements of an appropriate C*-algebra. However, many observables in quantum mechanics - such as position, momentum, energy - are in general unbounded operators. Is there any way to reconcile these two apparently contradictory statements?

I have looked at the notion of affiliation for a C*-algebra in the sense of Woronowicz. However, I can't see how you would extend states to elements affiliated with a C*-algebra and so it doesn't seem to solve the problem.

-
If I remember correctly then your question is explained very nicely in Strocchi's lecture notes "An Introduction to the Mathematical Structure of Quantum Mechanics - A Short Course for Mathematicians". –  user5831 Feb 19 '11 at 16:39
One thing you can do is to consider $U(s) = e^{i s P}$ and $V(t) = e^{i t Q}$ for example, if $P,Q$ are the position and momentum operators and $s,t$ real numbers. $U(s)$ and $V(t)$ are unitaries.You then have the Weyl form of the canonical commutation relations, $U(s) V(t) = e^{ist} V(t) U(s)$. –  Pieter Naaijkens Feb 19 '11 at 16:50
I don't have anything substantially new to add to Pieter Naaijkens' comment and Tim van Beek's answer. I just want to comment that the use of C*-algebraic techniques in this context should be considered natural and even expected. The real point is that an essentially self adjoint unbounded operator $T$ can be characterized (in a certain sense) by its functional calculus, i.e. by the \textit{bounded} operators $f(T)$ where $f$ is a bounded continuous function on the spectrum of $T$. This is also the reason why C*-algebraic techniques are useful for understanding differential operators. –  Paul Siegel Feb 19 '11 at 19:08
It's also worth mentioning that von Neumann in fact invented much of what we now consider to be basic C*-algebra and von Neumann algebra theory in order to handle operators coming from quantum mechanics that he knew not to be bounded –  Paul Siegel Feb 19 '11 at 19:12
If you know the expectation values of all projection operators then you can also calculate the expectation values of the unbounded operators. –  jjcale Jun 30 '13 at 8:42

In addition to what has already been said I would like to add some more comments. I completely understand your suspicion that the passage from unbounded operators to bounded ones is at least tricky. For the canonical commutation relations of position and momentum operators this can be solved in a reasonable and also physically acceptable way by passing to the Weyl algebra (OK; there are zillions of Weyl algebras around in math, but I'm refering here to the $C^*$-algebra generated by the exponentials of $Q$'s and $P$'s subject to the heuristic commutation relations arising from $[Q, P] = \mathrm{i} \hbar$).

However, there are other situations in physics where this is much more complicated: when one tries to quantize a classical mechanical system which has a more complicated phase space than just $\mathbb{R}^{2n}$ then one can not hope to get some easy commutation relations which allow for a Weyl algebra like construction. To be more specific, for general symplectic of Poisson manifolds the beast quantization scheme one can get in this generality is probably formal deformation quantization. Here the classical observable algebra (a Poisson algebra) is deformed into a noncommutative algebra in a $\hbar$-dependent way such that the new product, the so-called star product, depends on $\hbar$ in such a way that for $\hbar = 0$ one recovers the classical mutliplication and in first order of $\hbar$ one gets the Poisson bracket in the commutator.

Now two difficulties arise: the most severe one is that in this generality one only can hope for formal power series in $\hbar$. Thus one has even changed the underlying ring of scalars from $\mathbb{C}$ to $\mathbb{C}[[\hbar]]$. So there is of course no notion of a $C^\ast$-algebra whatsoever on this ring. Nevertheless, there is a good notion of states in the sense of positive functionals already at this stage. Second, even if one succeeds to find a convergent subalgebra one does usually not end up with a $C^\ast$-algebra on the nose. Worse: in most of the explicit exampes one knows (and there are not really many of them...) the commutation relations one obtains are very complicated. In particular, it is not clear at all how one can affiliate a $C^\ast$-algebra to them. Moreover, it is not clear which of the previous states survive this condition of convergence and yield reasonable representations by the GNS construction.

It takes quite some effort to first represent the observables by typically very unbounded operators in a reasonable way and then show that they give rise to some self-adjoint operators still obying the relevant commutation relations. This is far from being obvious. To get a flavour for the difficulties it is quite illustrative to take a look at the book of Klimyk and Schmüdgen on Quantum Groups adn their Representations. Note that in these examples one still has a lot of structure around which helps to understand the analysis.

However, physics usually requires still much more general situations. Most important here are systems with gauge degrees of freedoms where one has to pass to a reduced phase space. Even if one starts with a geometrically nice phase space the reduced one can be horribly complicated. This problem is present in any contemporary QFT really relevant to physics :(

For other quantization schemes things are similar, even though I'm not quite the expert to say something more substantial :)

So one may ask the question why one should actually insist on $C^\ast$-algebras and this strong analytic background. There is indeed a physical reason and this is that quantum physics predicts not only expectation values of observables in given states (here the notion of a ${}^\ast$-algebra and a positive functional is sufficient) but also the possible outcomes of a measurement: they are given by particular numbers called the physical spectrum of the observable. To get a good description with predictive power the (as far as I know) only way to achieve this is to say that the physical spectrum is givebn by the mathematical spectrum of a self-adjoint operator in a Hilbert space. If one is here at this point, then the passage from a (unbounded) self-adjoint operator to a $C^\ast$-algebra is comparably easy: one has the spectral projections and takes e.g. the von Neumann algebra generated by them...

So the point I would like to make is that it is very desirable from a physical point of view to have the strong analytic framework for observables as either self-adjoint operators or Hermitian elements in a $C^\ast$-algebra. But the quantum theory of many nontrivial systems requires a long long and nontrivial way before one ends up in this nice heavenly situation.

-

The book mentioned by Bora,

• F. Strocchi: "An Introduction to the Mathematical Structur of Quantum Mechanics"

is indeed a good reference for an axiomatic approach to quantum mechanics where the observables of a given system are assumed to form a $C^*$-algebra. The physical motivation for this approach is that every detector is representable by an observable (a self-adjoint operator) that is bounded, because every detector has an upper bound of values it can measure. A detector is therefore a bounded function of an unbounded, essentially self-adjoint observable as the impuls operator in, say, the usual (space or impuls) representation of the Heisenberg comutation relations.

This is the physical motivation of the basic assumption of an axiomatic approach to quantum physics via $C^*$- algebras: The assumption is that a quantum system, whose observables are essentially self-adjoint - maybe unbounded - operators, can equivalently be described by an operator algebra containing all bounded functions of the original observables. (The function $e^{i s A}$ for a real number s and an essentially self-adjoint operator A is of course an example, as mentioned in the comment by Pieter).

For an explanation of how and why this works in quantum mechanics, see the book by Strocci. (The short answer is that the $C^*$ - algebra of a massive particle described by position and momentum as observables is the Weyl algebra which is generated by the bounded operators occuring in the Weyl communtation relations mentioned by Pieter.)

In axiomatic quantum field theory, the difference of bounded versus unbounded observables manifests itself in two different sets of axioms:

• the Wightman axioms use unbounded operators,

• the Haag-Kastler axioms use bounded operators.

In this setting it is not completely clear that both sets of axioms are equivalent, although the relations Wightman => Haag-Kastler and vice versa have been proven with certain additional "technical" assumptions, see for example:

• H.J. Borchers, Jakob Yngvason: “From quantum fields to local von Neumann algebras”, Rev.Math.Phys. Special issue, 1992, p.15-47.

("Quantum fields" refer to the Wightman axioms and "local von Neumann algebras" to the Haag-Kastler axioms.)

When you compare the situation in quantum field theory to the situation in quantum mechancis, you'll see that the situation is more complicated because in quantum field theory the von Neumann uniqueness theorem cannot be applied.

-
The reference should be: F. Strocchi, "An introduction to the mathematical structure of quantum mechanics". –  Matthew Daws Feb 21 '11 at 9:01

I wrote a paper about this at an REU I attended two years ago. At the time, I had the goal of making the transition from classical mechanics to quantum mechanics as natural as possible, motivating the axioms of quantum mechanics from those of classical mechanics, which are a lot more intuitive. Unfortunately, given the time constraints of the REU (just a couple of months) and being relatively new to the subject, I found myself mostly following other sources (in particular, Strocchi), which made use of the $C^*$-algebraic formalism. I have to admit, at the time, I did feel a bit uncomfortable throwing away all the unbounded operators, because, having studied "physicist's" quantum mechanics before, these are some things I naturally wanted to include.

Come two years later at the same REU, I tried to tackle the same problem, but this time I wanted to develop the axioms of quantum mechanics so to as allow unbounded operators in the theory. This led me to develop the notion of what I call an $F^*$-algebra ($F$ for Frechet). I am actually still working on the paper at the moment, but, after reading your post, I decided to upload a preliminary copy to my academia.edu account. You should read it, check it out, and see what you think. I'd be very happy to hear any comments you have.

Be warned though, I am still in the process of editing and revising it, so dare I say, there may be some errors. Read it with a skeptical eye and let me know if you catch anything.

Cheers! Jonny Gleason

P.S.: How do you make the accent in Frechet on mathoverflow?

-
My (rash?) assumption was that the OP was referring to work of Andrew Gleason (any relation?), cf. en.wikipedia.org/wiki/Gleason%27s_theorem –  Yemon Choi Aug 13 '11 at 20:57
He definitely could be. If that is the case, I would be incredibly embarassed for being so presumptuous =P. In any case, I did spend the summer two years ago and this summer working to solve the very question the OP asked, and my best (current) solution that I have found I am currently writing up and would be very interested in hearing what the OP (or anybdy else for that matter) has to say about it :). Also, if you know anything Andrew has written up on the $C^*$-algebraic foundations of QM I would love to see it. P.S.: As far as I know, no, there is no relation :). –  Jonathan Gleason Aug 13 '11 at 21:29
Hi Jonny, don't fret: we all make silly mistakes from time to time. A consequence of your mistake is that your very nice survey article is now disseminated to a wide audience. I enjoyed reading it. May all your mistakes be of this caliber. –  Tom LaGatta Aug 13 '11 at 22:18
Thanks Tom! Glad you enjoyed the article :) –  Jonathan Gleason Aug 14 '11 at 20:21
the command for the "accent aigu" you look for is \'{...} –  Adrien Hardy Nov 5 '11 at 13:40


text:
DeepAI

# Learning Gaussian Processes by Minimizing PAC-Bayesian Generalization Bounds

Gaussian Processes (GPs) are a generic modelling tool for supervised learning. While they have been successfully applied on large datasets, their use in safety-critical applications is hindered by the lack of good performance guarantees. To this end, we propose a method to learn GPs and their sparse approximations by directly optimizing a PAC-Bayesian bound on their generalization performance, instead of maximizing the marginal likelihood. Besides its theoretical appeal, we find in our evaluation that our learning method is robust and yields significantly better generalization guarantees than other common GP approaches on several regression benchmark datasets.

• 8 publications
• 5 publications
• 5 publications
• 6 publications
09/22/2019

### PAC-Bayesian Bounds for Deep Gaussian Processes

Variational approximation techniques and inference for stochastic models...
04/07/2021

### Adversarial Robustness Guarantees for Gaussian Processes

Gaussian processes (GPs) enable principled computation of model uncertai...
09/06/2021

### Gaussian Process Uniform Error Bounds with Unknown Hyperparameters for Safety-Critical Applications

Gaussian processes have become a promising tool for various safety-criti...
06/16/2020

### PAC-Bayesian Generalization Bounds for MultiLayer Perceptrons

We study PAC-Bayesian generalization bounds for Multilayer Perceptrons (...
06/26/2018

### Scalable Gaussian Process Inference with Finite-data Mean and Variance Guarantees

Gaussian processes (GPs) offer a flexible class of priors for nonparamet...
02/21/2020

### Knot Selection in Sparse Gaussian Processes

Knot-based, sparse Gaussian processes have enjoyed considerable success ...
11/28/2012

### Nonparametric Bayesian Mixed-effect Model: a Sparse Gaussian Process Approach

Multi-task learning models using Gaussian processes (GP) have been devel...

## 1 Introduction

Gaussian Processes (GPs) are a powerful modelling method due to their non-parametric nature rasmussen-williams-book

. Although GPs are probabilistic models and hence come equipped with an intrinsic measure of uncertainty, this uncertainty does not allow conclusions about their performance on previously unseen test data. For instance, one often observes overfitting if a large number of hyperparameters is adjusted using marginal likelihood optimization

bauer-understanding-sparse-GP-approximations . While a fully Bayesian approach, i.e. marginalizing out the hyperparameters, reduces this risk, it incurs a prohibitive runtime since the predictive distribution is no longer analytically tractable. Also, it does not entail out-of-the-box safety guarantees.

In this work, we propose a novel training objective for GP models, which enables us to give rigorous

and quantitatively good performance guarantees on future predictions. Such rigorous guarantees are developed within Statistical Learning Theory (e.g.

understanding-machine-learning-book ). But as the classical uniform learning bounds are meaningless for expressive models like deep neural nets understanding-deep-learning-requires-rethinking-generalization (as e.g. the VC dimension exceeds the training size) and GPs or non-parametric methods in general, such guarantees cannot be employed for learning those models. Instead, common optimization schemes are (regularized) empirical risk minimization (ERM) understanding-deep-learning-requires-rethinking-generalization ; understanding-machine-learning-book , maximum likelihood (MLE) rasmussen-williams-book , or variational inference (VI) jordan-ghahramani-et-al-vi ; titsias09 .

On the other hand, better non-uniform learning guarantees have been developed within the PAC-Bayesian framework mcallester-pac-bayesian-model-averaging ; asdf2 ; catoni-thermodyn-of-ml (Sect. 2). They are specially adapted to probabilistic methods like GPs and can yield tight generalization bounds, as observed for GP classification seeger-classification-paper , probabilistic SVMs tighter-pac-bayes-bounds-svm ; pac-bayes-and-margins

, linear classifiers

pac-bayes-learning-of-linear-classifiers , or stochastic NNs nonvacuous-generalization-bounds-snn . Most previous works used PAC-Bayesian bounds merely for the final evaluation of the generalization performance, whereas learning by optimizing a PAC-Bayesian bound has been barely explored pac-bayes-learning-of-linear-classifiers ; nonvacuous-generalization-bounds-snn . This work, for the first time, explores the use of PAC-Bayesian bounds (a) for GP training and (b) in the regression setting.

Specifically, we propose to learn full and sparse GP predictors directly by minimizing a PAC-Bayesian upper bound from Eq. (5) on the true future risk of the predictor, as a principled method to ensure good generalization (Sect. 3). Our general approach comes naturally for GPs because the KL divergence

in the PAC-Bayes theorem can be evaluated analytically for GPs

sharing the same hyperparameters. As this applies to popular sparse GP variants such as DTC seeger-dtc , FITC snelson-spgp , and VFE titsias09 , they all become amenable to our method of PAC-Bayes learning, combining computational benefits of sparse GPs with theoretical guarantees. We carefully account for the different types of parameters (hyperparameters, inducing inputs, observation noise, free-form parameters), as only some of them contribute to the “penalty term” in the PAC-Bayes bound. Further, we base GP learning directly on the inverse binary KL divergence seeger-classification-paper , and not on looser bounds used previously, such as from Pinsker’s inequality (e.g., nonvacuous-generalization-bounds-snn ).

We demonstrate our GP learning method on regression tasks, whereas PAC-Bayes bounds have so far mostly been used in a classification setting. A PAC-Bayesian bound for regression with potentially unbounded loss function was developed in

pac-bayesian-theory-meets-bayesian-inference , it requires a sub-Gaussian assumption w.r.t. the (unknown) data distribution, see also excess-risk-bounds-using-vi-in-gaussian-models . To remain distribution-free as in the usual PAC setting, we employ and investigate a generic bounded loss function for regression.

We evaluate our learning method on several datasets and compare its performance to state-of-the-art GP methods rasmussen-williams-book ; snelson-spgp ; titsias09 in Sect. 4. Our learning objective exhibits robust optimization behaviour with the same scaling to large datasets as the other GP methods. We find that our method yields significantly better risk bounds, often by a factor of more than two, and that only for our approach the guarantee improves with the number of inducing points.

## 2 General PAC-Bayesian Framework

### 2.1 Risk functions

We consider the standard supervised learning setting understanding-machine-learning-book where a set of training examples () is used to learn in a hypothesis space , a subset of the space of functions . We allow learning algorithms that output a distribution over hypotheses , rather than a single hypothesis , which is the case for GPs we consider later on.

To quantify how well a hypothesis performs, we assume a bounded loss function to be given, w.l.o.g. scaled to the interval . measures how well the prediction approximates the actual output at an input . The empirical risk of a hypothesis is then defined as the average training loss . As in the usual PAC framework, we assume an (unknown) underlying distribution on the set of examples, and define the (true) risk as . We will later assume that the training set consists of independent draws from and study how close is to its mean understanding-machine-learning-book . To quantify the performance of stochastic learning algorithms, that output a distribution over hypotheses, we define the empirical and true risks by a slight abuse of notation as mcallester-pac-bayesian-model-averaging :

 RS(Q):= Eh∼Q[RS(h)]=1NN∑i=1Eh∼Q[ℓ(yi,h(xi))], (1) R(Q):= Eh∼Q[R(h)]=E(x∗,y∗)∼μEh∼Q[ℓ(y∗,h(x∗))]. (2)

These are the average losses, also termed Gibbs risks, on the training and true distributions, respectively, where the hypothesis is sampled according to before prediction.

In the following, we focus on the regression case, where is the set of reals. An exemplary loss function in this case is , where the functions specify an interval outside of which a prediction is deemed insufficient; similar to

-support vector regression

vapnik-the-nature-of-statistical-learning-theory , we use , with a desired accuracy goal specified before learning (see Sect. 4). In any case, the expectations over in (1)–(2) reduce to one-dimensional integrals as

is a real-valued random variable at each

. See App. C, where we also explore other loss functions.

Instead of the stochastic predictor with , one is often interested in the deterministic Bayes predictor seeger-classification-paper ; for GP regression, this simply equals the predictive mean at . The corresponding Bayes risk is defined by . While PAC-Bayesian theorems do not directly give a bound on but only on , it is easy to see that if is quasi-convex in , as in the examples above, and the distribution of is symmetric around its mean (e.g., Gaussian) seeger-classification-paper . An upper bound on below thus implies a nontrivial bound on .

### 2.2 PAC-Bayesian generalization bounds

In this paper we aim to learn a GP by minimizing suitable risk bounds. Due to the probabilistic nature of GPs, we employ generalization bounds for stochastic predictors, which were previously observed to yield stronger guarantees than those for deterministic predictors seeger-classification-paper ; tighter-pac-bayes-bounds-svm ; nonvacuous-generalization-bounds-snn . The most important results in this direction are the so-called “PAC-Bayesian bounds”, originating from mcallester-pac-bayesian-model-averaging ; asdf2 and developed in various directions seeger-classification-paper ; maurer-note-pac-bayes ; catoni-thermodyn-of-ml ; pac-bayes-learning-of-linear-classifiers ; pac-bayesian-bounds-based-on-the-renyi-divergence ; pac-bayesian-theory-meets-bayesian-inference .

The PAC-Bayesian theorem (Theorem 1) gives a probabilistic upper bound (generalization guarantee) on the true risk of a stochastic predictor in terms of its empirical risk on a training set . It requires to fix a distribution on the hypothesis space before seeing the training set , and applies to the true risk of any distribution on 111We follow common usage and call and

“prior” and “posterior” distributions in the PAC-Bayesian setting, although their meaning is somewhat different from priors and posteriors in Bayesian probability theory.

. The bound contains a term that can be interpreted as complexity of the hypothesis distribution , namely the Kullback-Leibler (KL) divergence , which takes values in . The bound also contains the binary KL-divergence , defined for , or more precisely its (upper) inverse w.r.t. the second argument (for , ):

 kl−1(q,ε):=max{p∈[0,1]:kl(q∥p)≤ε}, (3)

which equals the unique satisfying . While has no closed-form expression, we refer to App. A for an illustration and more details, including its derivatives for optimization.

###### Theorem 1 (PAC-Bayesian theorem mcallester-pac-bayesian-model-averaging ; seeger-classification-paper ; maurer-note-pac-bayes ).

For any -valued loss function , for any distribution , for any , for any distribution on a hypothesis set , and for any , the following holds with probability at least over the training set :

 ∀Q:R(Q)≤kl−1⎛⎜⎝RS(Q),KL(Q∥P)+ln2√NδN⎞⎟⎠. (4)

The RHS of (4) can be upper bounded by , which gives a useful intuition about the involved terms, but can exceed and thereby yield a trivial statement. Note that the full PAC-Bayes theorem maurer-note-pac-bayes gives a simultaneous lower bound on , which is however not relevant here as we are going to minimize the upper risk bound. Further refinements of the bound are possible (e.g., maurer-note-pac-bayes ), but as they improve over Theorem 1 only in small regimes catoni-thermodyn-of-ml ; pac-bayes-learning-of-linear-classifiers ; pac-bayesian-bounds-based-on-the-renyi-divergence , often despite adjustable parameters, we will stick with the parameter-free bound (4).

We want to consider a family of prior distributions parametrized by , e.g. in GP hyperparameter training rasmussen-williams-book . If this family is countable, one can generalize the above analysis by fixing some probability distribtion on and defining the mixture prior ; when

is a finite set, the uniform distribution

is a canonical choice. Using the fact that holds for each (App. B), Theorem 1 yields that, with probability at least over ,

 ∀θ∈Θ ∀Q:R(Q)≤kl−1⎛⎜⎝RS(Q),KL(Q∥Pθ)+ln1pθ+ln2√NδN⎞⎟⎠ =: B(Q). (5)

The bound (5) holds simultaneously for all and all 222The same result can be derived from (4) via a union bound argument (see Appendix B).. One can thus optimize over both and to obtain the best generalization guarantee, with confidence at least . We use for our training method below, but we will also compare to training with the suboptimal upper bound as was done previously nonvacuous-generalization-bounds-snn . The PAC-Bayesian bound depends only weakly on the confidence parameter , which enters logarithmically and is suppressed by the sample size . When the hyperparameter set is not too large (i.e.  is small compared to ), the main contribution to the penalty term in the second argument of comes from , which must be for a good generalization statement (see Sect. 4).

## 3 PAC-Bayesian learning of GPs

### 3.1 Learning full GPs

GP modelling is usually presented as a Bayesian method rasmussen-williams-book , in which the prior is specified by a positive definite kernel and a mean function on the input set . In ordinary GP regression, the learned distribution is then chosen as the Bayesian posterior coming from the assumption that the training outputs are noisy versions of with i.i.d. Gaussian likelihood . Under this assumption, is again a GP rasmussen-williams-book :

 Q(f)=GP(f∣m(x)+kN(x)(KNN+σ2n1)−1(yN−mN),K(x,x′)−kN(x)(KNN+σ2n1)−1kN(x′)T), (6)

with , , . Eq. (6) is employed to make (stochastic) predictions for on new inputs . In our approach below, we do not require any Bayesian rationale behind but merely use its form, parametrized by , as an optimization ansatz within the PAC-Bayesian theorem.

Importantly, for any full GP prior and its corresponding posterior from (6), the KL-divergence in Theorem 1 and Eq. (5) can be evaluated on finite (-)dimensional matrices. This allows us to evaluate the PAC-Bayesian bound and in turn to learn GPs by optimizing it. More precisely, one can easily verify that and have the same conditional distribution 333In fact, direct computation rasmussen-williams-book gives . Remarkably, does not depend on nor on , even though from (6) does. Intuitively this is because, for the above likelihood, is independent of given ., so that

 KL(Q∥P) =KL(Q(fN)Q(f∣fN)∥P(fN)P(f∣fN)) =KL(Q(fN)∥P(fN)) (7) =12lndet[KNN+σ2n1]−N2lnσ2n−12tr[KNN(KNN+σ2n1)−1] (8) +12(yN−mN)T(KNN+σ2n1)−1KNN(KNN+σ2n1)−1(yN−mN),

where in the last step we used the well-known formula kullback-leibler-paper

for the KL divergence between normal distributions

To learn a full GP means to select “good” values for the hyperparameters , which parametrize a family of GP priors , and for the noise level rasmussen-williams-book . Those values are afterwards used to make predictions with the corresponding posterior from (6). In our experiments (Sect. 4) we will use the squared exponential (SE) kernel on , , where

is the signal variance,

are the lengthscales, and we set the mean function to zero. The hyperparameters are (SE-ARD kernel rasmussen-williams-book ), or if we take all lengthscales to be equal (non-ARD).

The basic idea of our method, which we call “PAC-GP” is now to learn the parameters444Contrary to the usual GP viewpoint rasmussen-williams-book , is not a hyperparameter in our method since the prior does not depend on . Thus, does also not contribute to the “penalty term” . is merely a free parameter in the posterior distribution . By (8), as , so we need this parameter because otherwise and the bound as well as the optimization objective would become trivial. Although the parameter is originally motivated by a Gaussian observation noise assumption, the aim here is merely to parameterize the posterior in some way while maintaining computational tractability; cf. also Sect. 3.2. and by minimizing the upper bound from Eq. (5), therefore selecting the GP predictor with the best generalization performance guarantee within the scope of the PAC-Bayesian bound. Note that all involved terms (App. C) and from (8) as well as their derivatives (App. A) can be computed effectively, so we can use gradient-based optimization.

The only remaining issue is that the learned prior hyperparameters have to come from a discrete set that must be specified before seeing the training set (Sect. 2.2). To achieve this, we first minimize the RHS of Eq. (5) over and in a gradient-based manner, and thereafter discretize each of the components of to the closest point in the equispaced -element set ; thus, when denotes the number of components of , the penalty term to be used in the optimization objective (5) is . The SE-ARD kernel has , while the standard SE kernel has parameters. In our experiments we round each component of to two decimal digits in the range , i.e. , . We found that this discretization has virtually no effect on the predictions of , and that coarser rounding (i.e. smaller ) does not significantly improve the bound (5) (via its smaller penalty term ) nor the optimization (via its higher sensitivity to ); see App. F.

### 3.2 Learning sparse GPs

Despite the fact that, with confidence , the bound in (5) holds for any from the prior GP family and for any distribution , we optimized in Sect. 3.1 the upper bound merely over the parameters after substituting and the corresponding from (6). We are limited by the need to compute effectively, for which we relied on the property and the Gaussianity of and , cf. (7). Building on this two requirements, we now construct more general pairs of GPs with effectively computable , so that our learning method becomes more widely applicable, including sparse GP methods.

Instead of the points associated with the training set as in Sect. 3.1, one may choose from the input space any number of points , often called inducing inputs

, and any Gaussian distribution

on function values , with any and positive semidefinite matrix . The distribution on can be extended to all function values at all inputs using the conditional from the prior (see Sect. 3.1). This yields the following predictive GP:

 Q(f)=GP(f∣ m(x)+kM(x)K−1MM(aM−mM), (9) K(x,x′)−kM(x)K−1MM[KMM−BMM]K−1MMkM(x′)T),

where , , and . This form of

includes several approximate posteriors from Bayesian inference that have been used in the literature

rasmussen-williams-book ; seeger-classification-paper ; titsias09 ; scalable-variational-gaussian-process-classification , even for noise models other than the Gaussian one used to motivate the from Sect. 3.1. Analogous reasoning as in (7) now gives seeger-classification-paper ; titsias09 ; KL-divergence-between-stochastic-processes :

 KL(Q∥P)=KL(Q(fM)∥P(fM))= −12lndet[BMMK−1MM]+12tr[BMMK−1MM]−M2 +12(aM−mM)TK−1MM(aM−mM). (10)

One can thus effectively optimize in (5) the prior and the posterior distribution by varying the number and locations of inducing inputs and the parameters and , along with the hyperparameters . Optimization can in this framework be organized such that it consumes time per gradient step and memory as opposed to and for the full GP of Sect. 3.1. This is a big saving when and justifies the name “sparse GP” rasmussen-williams-book ; unifying-view-sparse-gp-approx .

Some popular sparse-GP methods unifying-view-sparse-gp-approx are special cases of the above form, by prescribing certain and depending on the training set , so that only the inducing inputs and a few parameters such as are left free:

 aM=KMMQ−1MMKMN(αΛ+σ2n1)−1yN,BMM= KMMQ−1MMKMM, (11)

where with , , and is a diagonal -matrix with entries . Setting corresponds to the FITC approximation snelson-spgp , whereas is the VFE and DTC method titsias09 ; seeger-dtc (see App. D

for their training objectives); one can also linearly interpolate between both choices with

bui-yan-turner-unifying . Another form of sparse GPs where the latent function values are fixed and not marginalized over, corresponds to , which however gives diverging via (10) and therefore trivial bounds in (4)–(5).

Our learning method for sparse GPs (“PAC-SGP”) follows now similar steps as in Sect. 3.1: One has to include a penality for the prior hyperparameters , which are to be discretized into the set after the optimization of (5). Note, contains the prior hyperparameters only and not the inducing points nor , , , or from (11); all these quantities can be optimized over simultaneously with , but do not need to be discretized. The number of inducing inputs can also be varied, which determines the required computational effort, and all optimizations can be both discrete seeger-dtc or continuous snelson-spgp ; titsias09 . When optimizing over positive , the parametrization with a lower triangular matrix can be used scalable-variational-gaussian-process-classification . For the experiments below we always employ the FITC parametrization (fixed ) in our proposed PAC-SGP method, i.e. our optimization parameters are and besides the length scale hyperparameters .

## 4 Experiments555Python code (building on GPflow gpflow and TensorFlow tensorflow ) implementing our method is available at https://github.com/boschresearch/PAC_GP.

We now illustrate our learning method and compare it with other GP methods on various regression tasks. In contrast to prior work nonvacuous-generalization-bounds-snn , we found the gradient-based training with the objective (5) to be robust enough, such that no pretraining with conventional objectives (such as from App. D) is necessary. We set throughout seeger-classification-paper ; nonvacuous-generalization-bounds-snn , cf. Sect. 2.2, and use (unless specified otherwise) the generic bounded loss function for regression, with accuracy goal as specified below.

We evaluate the following methods: (a) PAC-GP: Our proposed method (cf. Sect. 3.1) with the training objective (5) (kl-PAC-GP) and for comparison with the looser training objective (sqrt-PAC-GP) (see below (5), similar to e.g. nonvacuous-generalization-bounds-snn ); (b) PAC-SGP: Our sparse GP method (Sect. 3.2), again with objectives (kl-PAC-SGP) and (sqrt-PAC-SGP), respectively; (c) full-GP: The ordinary full GP for regression rasmussen-williams-book ; (d) VFE: Titsias’ sparse GP titsias09 ; (e) FITC: Snelson-Ghahramani’s sparse GP snelson-spgp . Note that full-GP, VFE, and FITC as well as sqrt-PAC-GP and sqrt-PAC-SGP are trained on other objectives (see App. D), and we will evaluate the upper bound (5) on their generalization performance by evaluating via (8) or (10). To obtain finite generalization bounds, we discretize for all methods at the end of training as in Sect. 3.1 and use the appropriate in (5).

##### (a) Predictive distribution.

To get a first intuition, we illustrate in Fig. 1 the effect of varying in the loss function on the predictive distribution of our sparse PAC-SGP. The accuracy goal defines a band around the predictive mean within which data-points do not contribute to the empirical risk . We thus chose the accuracy goal relative to the observation noise obtained from an ordinary full-GP. Results are presented on the 1D toy dataset666snelson: dimensions 200 1, available at www.gatsby.ucl.ac.uk/~snelson. from the original FITC snelson-spgp and VFE titsias09 publications (for a comparison to the predictive distributions of FITC and VFE see App. E, which also contains an illustration that our kl-PAC-SGP avoids FITC’s known overfitting on pathological datasets.). Here and below, we optimize the hyperparameters in each experiment anew.

We find that for large (right plot) the predictive distribution (blue) becomes smoother: Due to the wider -band (green), the PAC-SGP does not need to adapt much to the data for the -band to contain many data points. Hence the predictive distribution can remain closer to the prior, which reduces the KL-term in the objective (5). For the same reason, the inducing points need not adapt much compared to their initial positions for large . For smaller , the PAC-SGP adapts more to the data, whereas for very small (left plot), it is anyhow not possible to place many data points within the narrow -band, so the predictive distribution can again be closer to the prior (compare e.g. in the first and second plots the blue curves near the rightmost datapoints) for a smaller KL-term. In particular, the KL-divergence (divided by number of training points) for the three settings in Fig.1 are: 0.097 (left), 0.109 (middle), and 0.031 (right).

##### (b) Full-GP experiments – dependence on the accuracy goal ε.

To explore the dependence on the desired accuracy further, we compare in Fig. 2 the ordinary full-GP to our PAC-GPs on the boston housing dataset777boston: dimensions 506 13, available at http://lib.stat.cmu.edu/datasets/boston. As pre-processing we normalized all features and the output to mean zero and unit variance, then analysed the impact of the accuracy goal . We used 80% of the dataset for training and 20% for testing, in ten repetitions of the experiment.

Our PAC-GP yields significantly better generalization guarantees for all accuracy goals compared to full-GP, since we are directly optimizing the bound (5). This effect is stronger for large , where the KL-term of PAC-GP can decrease as may again remain closer to while keeping the training loss low. Although better bounds do not necessarily imply better Gibbs test risk, kl-PAC-GP performs only slightly below the ordinary full-GP in this regard. Moreover, our PAC-GPs exhibit less overfitting than the full-GP, for which the training risks are significantly larger than the test risks (see Table 1 in App. G for numerical values). On the other hand, the tighter objective (5) in the kl-PAC-GP allows learning a slightly more complex GP in terms of the KL-divergence compared to the sqrt-PAC-GP, which results in better test risks and at the same time better guarantees. This confirms that kl-PAC-GP is always preferable to sqrt-PAC-GP. However, as any prediction within the full -band around the ground truth incurs no risk for our PAC-GPs, their mean squared error (MSE) increases with .

The fact that our learned PAC-GPs exhibit higher training and test errors (Gibbs risk and esp. MSE) than full-GP can be explained by their underfitting in order to hedge against violating Eq. (5) (i.e. Theorem 1). This underfitting is evidenced by PAC-GP’s significantly less complex learned posterior as measured by (Fig. 2), or similarly (via Eqs. (8,10)), by its larger learned noise variance compared to full-GP’s (Table 1 in App. G). It is exactly this stronger regularization of PAC-GP in terms of the divergence that leads to its better generalization guarantees.

In the following, we will fix after pre-processing data as above, to illustrate PAC-GP further. Note however that in a concrete application, should be fixed to a desired accuracy goal using domain knowledge, but before seeing the training set . Alternatively, one can consider a set of -values chosen in advance, at the cost of a term in addition to in the objective (5).

##### (c) Sparse-GP experiments – dependence on number of inducing inputs M.

We now examine our sparse PAC-SGP method (Sect. 3.2) on the three large data sets pol, sarcos, and kin40k888pol: 15,000 26, kin40k: 40,000 8 (both from https://github.com/trungngv/fgp.git);
sarcos: 48,933 21 (http://www.gaussianprocess.org/gpml/data)
, again using 80%–20% train-test splits and ten iterations. The results are shown in Fig. 3. Here, we vary the number of inducing points . For modelling pol and kin40k, we use the SE-ARD kernel due to its better performance on these datasets, whereas we model sarcos without ARD (cf. Table 2 in App. G for the comparison ARD vs. non-ARD). The corresponding penalty terms for the three plots are and ; when compared to from Fig. 3, their contribution is largest for the pol dataset.

Our kl-PAC-SGP achieves significantly better upper bounds than VFE and FITC, by more than a factor of 3 on sarcos, a factor of roughly 2 on pol, and a factor between 1.3 and 2 on kin40k (Fig. 3, cf. also Table 2 in App. G). Also, the PAC-Bayes upper bound is much tighter for kl-PAC-SGP than for VFE or FITC, i.e. closer to the Gibbs risk, often by factors exceeding 3. Our kl-PAC-SGP behaves also more favorably in terms of generalization guarantee when inducing points are added and more complex models are allowed: our upper bound improves substantially with (kin40) or does at least not degrade (pol and sarcos), as opposed to VFE and FITC, whose complexities grow substantially with . Since very low training risks can already be achieved by a moderate number of inducing points for pol and sarcos, a growing with deteriorates the upper bound. Regarding the upper bound, the increased flexibility from larger only pays off for the kin40k dataset, whereas the MSE improves with increasing for all models and datasets. As above, kl-PAC-SGP is always slightly preferrable to sqrt-PAC-SGP, not only for the upper bound and Gibbs risks as expected but also for MSE (see Table 2 in App. G).

Similarly to the boston dataset, the higher test errors of kl-PAC-SGP compared to VFE and FITC can be explained by underfitting due to the stronger regularization, again shown by lower and significantly larger learned (by factors of 4–28 compared to VFE), cf. Table 2 in App. G. In fact, although our implementation of PAC-SGP employs the FITC parametrization, the PAC-(S)GP optimization is not prone to FITC’s well-known overfitting tendency bauer-understanding-sparse-GP-approximations , due to the regularization via the -divergence (see App. E, and in particular Supplementary Figure 7).

To investigate whether the higher test MSE of PAC-GP compared to VFE and FITC (and the full-GP above) is a consequence of the 0-1-loss used so far, we re-ran the PAC-SGP experiments for inducing inputs with the more distance-sensitive loss function (Eq. (20)), which is MSE-like for small deviations , i.e.  (Supplementary Figure 5). Our results are tabulated in Table 3 in App. G. The findings are inconclusive and range from an improvement w.r.t. MSE of 25% (pol) over little change (sarcos) to a decline of 12% (kin40k), showing that the effect of the loss function is smaller than might have been expected. Nevertheless, generalization guarantees of PAC-SGP remain much better than the ones of the other methods. While the MSE of our PAC-GPs would improve by choosing smaller (e.g., Fig. 2), this comes at the disadvantage of worse generalization bounds.

We further note that no method shows significant overfitting in Fig. 3, in the sense that the differences between test and training Gibbs risks are all rather small, despite the KL-complexity increasing with for VFE and FITC. This is unlike for Boston housing above, and may be due to the much larger training sets here. When comparing VFE and FITC, we observe that VFE consistently outperforms FITC in terms of both MSE as well as generalization guarantee, where VFE’s higher KL-complexity is offset by its much lower Gibbs risk. This fortifies the results in bauer-understanding-sparse-GP-approximations . We lastly note that, since for our PAC-SGP the obtained guarantees are much smaller than 1/2, we obtain strong guarantees even on the Bayes risk (Sect. 2.1).

## 5 Conclusion

In this paper, we proposed and explored the use of PAC-Bayesian bounds as an optimization objective for GP training. Consequently, we were able to achieve significantly better guarantees on the out-of-sample performance compared to state-of-the-art GP methods, such as VFE or FITC, while maintaining computational scalability. We further found that using the tighter generalization bound (5) based on the inverse binary kl-divergence leads to an increase in the performance on all metrics compared to a looser bound as employed in previous works (e.g. nonvacuous-generalization-bounds-snn ).

Despite the much better generalization guarantees obtained by our method, it often yields worse test error, in particular test MSE, than standard GP regression methods; this largely persists even when using more distance-sensitive loss functions than the 0-1-loss. The underlying reason could be that all loss functions considered in this work were bounded, as necessitated by our desire to provide generalization guarantees irrespective of the true data distribution. While rigorous PAC-Bayesian bounds exist for MSE-like unbounded loss functions under special assumptions on the data distribution pac-bayesian-theory-meets-bayesian-inference , it may nevertheless be worthwhile to investigate whether these training objectives lead to better test MSE in examples. A drawback is that those assumptions are usually impossible to verify, thus the generalization guarantees are not comparable. Note that the design of a loss function is dependent on the application domain and there is no ubiquitous choice across all settings. In many safety-critical applications, small deviations are tolerable whereas larger deviations are all equally catastrophic, thus a 0-1-loss as ours and a rigorous bound on it can be more useful than the MSE test error.

While in this work we focussed on regression tasks, the same strategy of optimizing a generalization bound can also be applied to learn GPs for binary and categorical outputs. Note that the true -term in this setting has so far been merely upper bounded by its regression proxy seeger-classification-paper , and it would be interesting to develop better bounds on the classification complexity term. Lastly, it may be worthwhile to use other or more general sparse GPs within our PAC-Bayesian learning method, such as free-form scalable-variational-gaussian-process-classification or even more general GPs more-general-than-free-form .

#### Acknowledgments

We would like to thank Duy Nguyen-Tuong, Martin Schiegg, and Michael Schober for helpful discussions and proofreading.

## References

• (1)

C. E. Rasmussen, C. K. I. Williams, “Gaussian Processes for Machine Learning”, The MIT Press (2006).

• (2) M. Bauer, M. v. d. Wilk, C. E. Rasmussen, “Understanding Probabilistic Sparse Gaussian Process Approximations”, In NIPS (2016).
• (3) S. Shalev-Shwartz, S. Ben-David, “Understanding Machine Learning: From Theory to Algorithms”, Cambridge University Press (2014).
• (4)

C. Zhang, S. Bengio, M. Hardt, B. Recht, O. Vinyals, “Understanding deep learning requires rethinking generalization”, In ICLR (2017).

• (5) M. Jordan, Z. Ghahramani, T. Jaakkola, L. Saul, “Introduction to variational methods for graphical models”, Machine Learning, 37, 183-233 (1999).
• (6) M. Titsias, “Variational Learning of Inducing Variables in Sparse Gaussian Processes”, In AISTATS (2009).
• (7) D. McAllester, “PAC-Bayesian model averaging”, COLT (1999).
• (8) D. McAllester, “PAC-Bayesian Stochastic Model Selection”, Machine Learning 51, 5-21 (2003).
• (9) O. Catoni, “Pac-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning”, IMS Lecture Notes Monograph Series 2007, Vol. 56 (2007).
• (10) M. Seeger, “PAC-Bayesian Generalization Error Bounds for Gaussian Process Classification”, Journal of Machine Learning Research 3, 233-269 (2002).
• (11) A. Ambroladze, E. Parrado-Hernández, J. Shawe-Taylor, “Tighter PAC-Bayes bounds”, In NIPS (2007).
• (12) J. Langford, J. Shawe-Tayor, “PAC-Bayes & margins”, In NIPS (2002).
• (13) P. Germain, A. Lacasse, F. Laviolette, M. Marchand, “PAC-Bayesian Learning of Linear Classifiers”, In ICML (2009).
• (14)

G. K. Dziugaite, D. M. Roy, “Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data”, In UAI (2017).

• (15) E. Snelson, Z. Ghahramani, “Sparse Gaussian Processes using Pseudo-inputs”, In NIPS (2005).
• (16) M. Seeger, C. K. I. Williams, N. Lawrence, “Fast Forward Selection to Seepd Up Sparse Gaussian Process Regression”, In AISTATS (2003).
• (17) P. Germain, F. Bach, A. Lacoste, S. Lacoste-Julien, “PAC-Bayesian Theory Meets Bayesian Inference”, In NIPS (2016).
• (18) R. Sheth, R. Khardon, “Excess Risk Bounds for the Bayes Risk using Variational Inference in Latent Gaussian Models”, In NIPS (2017).
• (19) V. Vapnik, “The Nature of Statistical Learning Theory”, Springer (1995).
• (20) A. Maurer, “A Note on the PAC Bayesian Theorem”, arXiv:cs/0411099 (2004).
• (21) L. Begin, P. Germain, F. Laviolette, J.-F. Roy, “PAC-Bayesian Bounds based on the Renyi Divergence”, In AISTATS (2016).
• (22) S. Kullback, R. Leibler, “On information and sufficiency”, Annals of Mathematical Statistics 22, 79-86 (1951).
• (23)

A. G. de G. Matthews, J. Hensman, R. Turner, Z. Ghahramani, “On Sparse Variational Methods and the Kullback-Leibler Divergence between Stochastic Processes”, In AISTATS (2016).

• (24) J. Quinonero-Candela, C. E. Rasmussen, “A Unifying View of Sparse Approximate Gaussian Process Regression”, Journal of Machine Learning Research 6, 1939-1959 (2005).
• (25) T. D. Bui, J. Yan, R. E. Turner, “A Unifying Framework for Gaussian Process Pseudo-Point Approximations using Power Expectation Propagation”, Journal of Machine Learning Research 18, 1-72 (2017).
• (26) J. Hensman, A. Matthews, Z. Ghahramani, “Scalable Variational Gaussian Process Classification”, In AISTATS (2015).
• (27)

A. Matthews, M. van der Wilk, T. Nickson, K. Fujii, A. Boukouvalas, P. León-Villagrá, Z. Ghahramani, J. Hensman, “GPflow: A Gaussian process library using TensorFlow”, Journal of Machine Learning Research 18, 1-6 (2017).

• (28) M. Abadi et al., “TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems”, https://www.tensorflow.org/ (2015).
• (29) C.-A. Cheng, B. Boots, “Variational Inference for Gaussian Process Models with Linear Complexity”, In NIPS (2017).

## Appendix A Inverse binary KL-divergence and its derivatives, Pinsker’s inequality

The function , defined in Eq. (3), can easily be computed numerically for any , to any desired accuracy via the bisection method, since the function is strictly monotonically increasing in from to (for or , we set ). Note that the monotonicity in implies further that is monotonically increasing in . Fig. 4 shows a plot of for various values of , and states a few special function values of . By Pinsker’s inequality, it holds that , which implies that .

When applying gradient descent on the RHS of the generalization bound (5) (which includes (4) as a special case), as we propose and do, one further needs, besides the evaluation of , also the derivatives of w.r.t. both of its arguments. These can be easily derived by differentiating the identity w.r.t.  and , plugging in the easily computed derivatives of . The result is:

 ∂kl−1(q,ε)∂q =ln1−q1−kl−1(q,ε)−lnqkl−1(q,ε)1−q1−kl−1(q,ε)−qkl−1(q,ε), (12) ∂kl−1(q,ε)∂ε =11−q1−kl−1(q,ε)−qkl−1(q,ε). (13)

The derivative of the RHS of (5) with respect to parameters (which may include the hyperparameters , the noise level , the inducing points , or any other parameters of and such as , or from Section 3.2) thus reads:

 ddξkl−1⎛⎜ ⎜⎝RS(Qξ),KL(Qξ∥Pξ)+ln1pξ+ln2√NδN⎞⎟ ⎟⎠==⎛⎜ ⎜ ⎜ ⎜⎝∂kl−1(q,ε)∂q∣∣∣q=RS(Qξ)ε=(KL(Qξ∥Pξ)+ln2√Nδpξ)/N⎞⎟ ⎟ ⎟ ⎟⎠⋅ddξRS(Qξ)    +⎛⎜ ⎜ ⎜ ⎜⎝∂kl−1(q,ε)∂ε∣∣∣q=RS(Qξ)ε=(KL(Qξ∥Pξ)+ln2√Nδpξ)/N⎞⎟ ⎟ ⎟ ⎟⎠⋅ddξKL(Qξ∥Pξ)+ln1pξ+ln2√NδN, (14)

using the partial derivatives of in parentheses from (12)–(13).

We use the expression (14) for our gradient-based optimization of the parameters in Sect. 4. Note that we treat all components of as continuous parameters during this optimization, despite the fact that the hyperparameters for the prior have to come from a countable set (see around Eq. (5) and App. B). It is only after the optimization that we discretize all of those parameters onto a pre-defined grid (chosen before seeing the training sample ), as described in Sect. 3.1.

Note that in (14) can be computed analytically in our proposed methods PAC-GP and PAC-SGP by using standard matrix algebra (e.g., (rasmussen-williams-book, , App. A)) for differentiating the matrix-analytic expressions of in (7) or (10) (possibly with the parametrization (11)). Furthermore, the derivative is easily computed for common distributions (Sect. 2.2), again treating first as a continuous parameter in the optimization as explained in the previous paragraph; in our paper, we always discretize the hyperparameter set to be finite and choose as the uniform distribution, so is independent of and . Lastly, we show in App. C how to effectively compute in the expression (14) for relevant loss functions .

To our knowledge, the parameter-free PAC-Bayes bound from Theorem 1 or Eq. (5) has never before been used for learning, as we do in our paper here, ostensibly due to the perceived difficulty of handling the derivatives of nonvacuous-generalization-bounds-snn . Instead, when a PAC-Bayes bound was used to guide learning in prior works pac-bayes-learning-of-linear-classifiers ; nonvacuous-generalization-bounds-snn , then a simple sum of and a penalty term involving and was employed as an upper bound, either obtained from alternative PAC-Bayes theorems catoni-thermodyn-of-ml ; pac-bayes-learning-of-linear-classifiers or from loosening the upper bound in Eq. (5) to an expression of the form by a use of Pinsker’s inequality nonvacuous-generalization-bounds-snn or by looser derivations (some of which are mentioned in pac-bayes-learning-of-linear-classifiers ; pac-bayesian-bounds-based-on-the-renyi-divergence ). We show in our work how to perform the learning directly with the -bound (5) using the derivative from Eq. (14), and demonstrate that its optimization is robust and stable and has better performance than the optimization of looser bounds (see Sect. 4).

## Appendix B Proof of Eq. (5) — KL-divergence inequality and union bound

Let be a countable set (i.e. a finite set or a countably infinite set), and let

be any probability distribution over its elements

. Further, let be a family of probability distributions indexed by the , and define their mixture . Then it holds for each and :

 KL(Q∥P) =∫dxQ(x)lnQ(x)P(x) (15) =∫dxQ(x)lnQ(x)∑θ′pθ′Pθ′(x) ≤∫dxQ(x)lnQ(x)pθPθ(x) (16) =∫dxQ(x)ln1pθ+∫dxQ(x)lnQ(x)Pθ(x) =ln1pθ+KL(Q∥Pθ). (17)

The inequality (16) follows from the simple fact that the sum contains only nonnegative terms and is therefore at least as large as any of its summands, , together with the monotonicity of the logarithm . This inequality would not generally hold when were replaced by an integral over a continuous index , which explains the requirement of a countable index set . The inequality holds also for with the interpretation .

The inequality from (15)–(17), together with fact that is monotonically increasing in its second argument, shows how to obtain Eq. (5) from Theorem 1.

###### Remark 2.

Using the value with directly in (4) would of course yield a better bound than (5), but this


text:
Use the midpoint rule with the given value of n = 6 to approximate the integral. Round the answer to 4 decimal places.

$$\int_{0}^{\pi} sec(x/3) dx$$


text:
# Why is globalString not being updated by localUpdate in this add-on?

From the print statements in localUpdate it appears that changing the value of localString in the Redo panel updates globalString but globalString is not actually updated. What am I missing? (This doesn't seem to be a Blender bug, but something I'm not understanding about StringProperty or properties in general.)

NOTE: This is a a question about why the update function doesn't work, not about how to update the global without using the update function. I've simplified a fairly complex setup that has mixins that modify the local to get to this example, so while updating the global in execute would work in the example, it won't work in the final system.

To see the problem, invoke the operator by using the button in the tla Panel. When the Last Operator Adjustment (redo) panel shows up, change the value of localString in the panel. Messages will appear on the system console showing that localUpdate has run and modified globalString but if you check bpy.context.scene.globalString in the Python console after making the change, it will still have its original value of "global". Further, setting its value in the Python console causes it to change in the panel.

Here is the add-on. Copy it into the text editor and hit run.

import bpy
from bpy.types import Operator, Panel
from bpy.props import StringProperty

bl_info = {
"name" : "Op Test",
"description" : "a test",
"author" : "Marty",
"version" : (0, 0, 1),
"blender" : (2, 80, 0),
"location" : "View3D",
"support" : "COMMUNITY",
"category" : "3D View"
}

class TLA_OT_message(Operator):
bl_idname = "tla.message"
bl_label = "An Op"
bl_options = {"REGISTER", "UNDO"}

def localUpdate(self, context):
print("localUpdate called")
print(self.localString)
print(f'before {bpy.context.scene.globalString}')
context.scene.globalString = self.localString
print(f' after {bpy.context.scene.globalString}')

localString : bpy.props.StringProperty(
name="localString",
default="local",
update=localUpdate)

def execute(self, context):
self.report({"INFO"}, f"local string is {self.localString}")
return {"FINISHED"}

class TL_PT_panel(Panel):
bl_space_type = "VIEW_3D"
bl_region_type = "UI"
bl_category = "tla"
bl_label = "Panel"
bl_options = set()

def draw(self, context):
col = self.layout.column()
col.operator(TLA_OT_message.bl_idname, text = "push me")
col.prop(context.scene, "globalString", text="Global")

def anUpdater(self, context):
print("an Updater called")

def register():
bpy.utils.register_class(TLA_OT_message)
bpy.utils.register_class(TL_PT_panel)
bpy.types.Scene.globalString = bpy.props.StringProperty(
name="globalString",
default = "global",
update=anUpdater,
)

def unregister():
del bpy.types.Scene.globalString
bpy.utils.unregister_class(TL_PT_panel)
bpy.utils.unregister_class(TLA_OT_message)

if __name__ == "__main__":
register()

Here is what the 3D Viewport looks like after installing the addon, opening the side panel, selecting the 'tla' tab, and pushing the button:

Change "local" to "other" and the info message in the info window changes:

bpy.ops.text.run_script()
bpy.ops.tla.message()
local string is local
bpy.data.window_managers["WinMan"].(null) = "other"
bpy.ops.tla.message(localString="other")
local string is other

(Icons don't copy so here's a screenshot)

and the content of the system console at this point:

Read prefs: C:\Users\stupi\AppData\Roaming\Blender Foundation\Blender\2.93\config\userpref.blend
Info: local string is local

localUpdate called
other
before global
an Updater called
after other
Info: local string is other

Finally, checking the value of bpy.context.scene.globalString after all of that:

PYTHON INTERACTIVE CONSOLE 3.9.2 (default, Mar  1 2021, 08:18:55) [MSC v.1916 64 bit (AMD64)]

Builtin Modules:       bpy, bpy.data, bpy.ops, bpy.props, bpy.types, bpy.context, bpy.utils, bgl, blf, mathutils
Convenience Imports:   from mathutils import *; from math import *
Convenience Variables: C = bpy.context, D = bpy.data

>>> bpy.context.scene.globalString
'global'

>>>

and for completeness: my test file:

• but why do you want to show 2 fields with the "same" value (global + local)? i don't really get it...? Nov 26, 2021 at 6:36
• @Chris because you can't display class properties in a panel. The workaround I'm working on is to keep global versions in sync and display the the global versions. Eventually, once that works I'll add presets to both the panel and the operator, at least in theory. So I need to keep the global/local in sync so I can use presets in the panel and presets in the operator. Nov 26, 2021 at 16:03

Although i am not the add-on-Pro....i think it is because you are showing the global variable field too. So it takes the value from that field. If you comment out

#        col.prop(context.scene, "globalString", text="Global")

it works.

But i am sure batfinger can explain this better ;)

• The value of bpy.context.scene.globalString isn't updated this way. Nov 26, 2021 at 15:59

It is because localUpdate is an instance method. localString is a class annotation adding a property to all instances but at the time is defined, instance methods are not yet registered in the class. (At least that's my guess)

So you have to move localUpdate out of the class definition :

This works :

import bpy
from bpy.types import Operator, Panel
from bpy.props import StringProperty

bl_info = {
"name" : "Op Test",
"description" : "a test",
"author" : "Marty",
"version" : (0, 0, 1),
"blender" : (2, 80, 0),
"location" : "View3D",
"support" : "COMMUNITY",
"category" : "3D View"
}

def localUpdate(self, context):
print("localUpdate called")
print(self.localString)
print(f'before {bpy.context.scene.globalString}')
context.scene.globalString = self.localString
print(f' after {bpy.context.scene.globalString}')

class TLA_OT_message(Operator):
bl_idname = "tla.message"
bl_label = "An Op"
bl_options = {"REGISTER", "UNDO"}

localString : bpy.props.StringProperty(
name="localString",
default="local",
update=localUpdate)

def execute(self, context):
self.report({"INFO"}, f"local string is {self.localString}")
return {"FINISHED"}

class TL_PT_panel(Panel):
bl_space_type = "VIEW_3D"
bl_region_type = "UI"
bl_category = "tla"
bl_label = "Panel"
bl_options = set()

def draw(self, context):
col = self.layout.column()
col.operator(TLA_OT_message.bl_idname, text = "push me")
col.prop(context.scene, "globalString", text="Global")

def anUpdater(self, context):
print("an Updater called")

def register():
bpy.utils.register_class(TLA_OT_message)
bpy.utils.register_class(TL_PT_panel)
bpy.types.Scene.globalString = bpy.props.StringProperty(
name="globalString",
default = "global",
update=anUpdater,
)

def unregister():
del bpy.types.Scene.globalString
bpy.utils.unregister_class(TL_PT_panel)
bpy.utils.unregister_class(TLA_OT_message)

if __name__ == "__main__":
register()

• python noob here: why can python access self.localString in a global func def localUpdate(self, context) ? I know from other programming languages that properties of classes "normally" cannot be accessed from outside the class - except class variables or global variables, but even then there should be the class instance written before like instance.property = blabla or Classname.property = blubb. Looks like i have a basic misunderstanding here... :( Nov 26, 2021 at 8:11
• Yeah that's because of the way properties are registered in the Blender API : they're not instance attributes (foo = "this is an attribute"), they are (type) class annotations (bar: bpy.props.StringProperty()), meaning that they are dynamically added to Operator class instances when the operator is created and executed at run time using a button in the layout or the search operator. In the process the update method's parameter are dynamically populated, whereas in a regular class instance attribute the self is implicitly added. eg if you have an instance method method on class A Nov 26, 2021 at 9:03
• Calling a = A() and then a.method() is the same as calling A.method(a) (Again that's how I understand it I may be totally wrong ><) Nov 26, 2021 at 9:03
• You also have to understand that we are using an API, meaning this is just an interface to the actual Blender codebase, you can see it as a keyboard and mouse peripherals, keyboard and mouse are just an interface to your computer, and you don't need to see or understand what signals goes to the computer and comes back to actually manage your computer. But the core of the computation is done in the computer, not the interface. So what you're defining is python, yes, but it's also calling a bunch of C / C++ code under the hood that you don't need to know about for it to work Nov 26, 2021 at 9:09
• ok, thank you. My misunderstanding was my assumption this would be a "normal" property. Thank you for clarification. Nov 26, 2021 at 9:11

In the end, the answer is "You can't get there from here". More precisely, when you add an update function to a property in a class, Blender massages that property at registration time, in such a way that the context argument to the update function becomes the window manager, and not the context you need to look up the property.

This is why the info window gets the message bpy.data.window_managers["WinMan"].(null) = "other" in my example.

It doesn't matter whether the update function is defined within the class or not, it just doesn't work. For now, I have a workaround that works for presets, although it does require a bit of excess cleverness.

import bpy
from bpy.types import Operator, Panel
from bpy.props import StringProperty

bl_info = {
"name" : "Op Test",
"description" : "a test",
"author" : "Marty",
"version" : (0, 0, 1),
"blender" : (2, 80, 0),
"location" : "View3D",
"support" : "COMMUNITY",
"category" : "3D View"
}

class TLA_OT_message(Operator):
bl_idname = "tla.message"
bl_label = "An Op"
bl_options = {"REGISTER", "UNDO", "PRESET"}

need_update = False

localString : bpy.props.StringProperty(
name="localString",
default="local",
)

def updateGlobal(self, context):
context.scene.globalString = self.localString

@classmethod
def requireUpdate(cls):
cls.need_update = True

def execute(self, context):
if TLA_OT_message.need_update:
self.localString = context.scene.globalString
self.report({"INFO"}, f"local string is {self.localString}")
self.updateGlobal(context)
# The call to updateGlobal will cause the global's anUpdater
# function to be called, causing need_update to be set to True
# but we don't need an update so we override that change before
# leaving the function.
TLA_OT_message.need_update = False
return {"FINISHED"}

class TLA_PT_panel(Panel):
bl_space_type = "VIEW_3D"
bl_region_type = "UI"
bl_category = "tla"
bl_label = "Panel"
bl_options = set()

def draw(self, context):
col = self.layout.column()
col.operator(TLA_OT_message.bl_idname, text = "push me")
col.prop(context.scene, "globalString", text="Global")

def anUpdater(self, context):
TLA_OT_message.requireUpdate()

def register():
bpy.utils.register_class(TLA_OT_message)
bpy.utils.register_class(TLA_PT_panel)
bpy.types.Scene.globalString = bpy.props.StringProperty(
name="globalString",
default = "global",
update=anUpdater,
)

def unregister():
del bpy.types.Scene.globalString
bpy.utils.unregister_class(TLA_PT_panel)
bpy.utils.unregister_class(TLA_OT_message)

if __name__ == "__main__":
register()
$$$$
`


text:
# Summer study abroad vs. engineering internship

1. Oct 21, 2012

### Null_

Hey guys,

I'm having difficulty deciding what I want to do next summer. I'm currently a junior, so this is the last opportunity I have to do an engineering internship. Last summer I did an REU. I know I want to go into the renewable energy field, but I don't know if I need to go to grad school. I think I want to just because the idea of working in a chemical plant (I'm a ChemE) kind of depresses me.

Anyway, I have several companies who want me to do an internship with them this summer. I'm not particularly interested in any of them as they are mainly manufacturing. I have been browsing other options and think studying abroad or working at a national park would be awesome. I am just wondering if doing one of these things would hinder my chances at getting a job if I decide to not go the grad school route. I have lots of research experience but no industry experience. I think it could help my grad school application since I can relate my intended research to real-world experiences.