text:
The database. One of the most boring yet most essential piece ever design by mankind. Its sole purpose, serve as a place where we store the data used by our uber-awesome-oh-so-incredible™ application. So long as it is online, that we can store our data in it, and that we can retrieve it, we tend not to concern ourselves too much with it. As stated by Patrick McFadin : “Is it scaling? Yep. Is it online? Yep. Boring”. When Bootstrapping a startup, one tends to have little time (unless you’ve quit your day job) and little resources. Getting to the point where you have a boring database would indeed be the dream so that you can focus on your app. To get there however, the very first step is picking the right one based on your application’s needs. There are many options out there. One that I have seen bee heavily recommended back when I was working on a side project was MongoDB.

# MongoDB

In my time scouring the web, I have come across many recommendations, some of which I have followed when working on a side project. Back in 2013, MongoDB was still the rage. All the cool kids were using it. Why not after all? Who could resist the promise of dumping all your nested data in a collection and retrieving it just as easily? Database schemas? Why use that when you can have a dynamic schema instead? Plus, it’s all asynchronous and fault tolerant. Everything is awesome….

Note to self: don’t believe every you read on the internet.

Well, not quite. Having played with MongoDB and having read the experiences of other (see McFadin’s, Mei’s, Emin’s and Morgan’s posts), I can attest that it is a good and still improving database that is lacking in a few areas, the most important of which being concurrency and fault tolerance. Plus the idea that you can just dump nested data in there is not a great one. I understood early on that retrieving segments of that data or updating it atomically can be quite painful the more nesting your data has. Also, there is a cost to having a dynamic schema vs a static one.

To be fair, I love MongoDB. It was fairly easy to get started with. It was awesome. The database was indeed boring…until the application’s complexity and modeling need started to increase.

It can be quite difficult to model a social network using MongoDb. Let’s take a naive example. Let’s say you have a User class defined as below:

A fairly simple model. What happens if user X requests the friendship of user Y? Add user X to the friendship to review list of user Y, AND add user Y to the requestedFriendships of user X. 2 spots needing to be changed without transactions. Should user Y decide to accept user X’s friendship? Now 4 spots would need to be updated, i.e. remove the users from their respective requested friendships and friendship to review lists, and add each other into their respective friends list.

In an ACID world, the multiple updates would not have bothered me that much. If one update failed, the other would not take place. With MongoDB however, due its fault tolerance woes, it could happen that in between requests to the database, something goes awry (a train passes over the datacenter where my mongodb server is located and causes a momentary loss of connection), if my write concern is not ‘Journaled’, i.e. if I go full async, I can find myself in a state where it would be impossible for me to detect that a failure has occured, and thus wouldn’t be able to “manually” reverse whatever changes I had made.

What if I wanted to find what the friends of my friends liked? What if I wanted to find what my network of friends (i.e. my friend, their friends, the friends of their friends) recommend as the best movie currently in theaters? That is not something that you could easily do with MongoDB.

What I’ve found MongoDB to be useful at is to store data with a minimal amount of nesting. It makes it easier to retrieve later. For more complex modeling, especially in the case of social networks, I have found Neo4J to be a much better choice. MongoDB for the writes. Neo4J for the reads and/or Elasticsearch if you need full text search capabilities.

Assuming you use a service like Compose.io to host, scale and back up your MongoDB instance’s for you, your are looking at least 18$/month. If you need to add more databases to complement Mongo’s shortcomings, using Neo4J in the cloud with a service like GrapheneDb will cost between 50$-400$/month, while Compose’s ElasticSearch would cost you north of 45$ a month. Add what you need an multiply by 12 month and that’s how much you need to set aside just for your database cost. You obviously could handle the hosting and scaling yourself to reduce that cost.

If you’re bootstrapping your startup and have limited time, but some resources, I could see how you could build your application with MongoDB initially to get a proof of concept and get funding, or even to get an MVP to test the market and fail fast. It is also possible like that your use case would work just fine with MongoDB like Server Density’s.

UPDATE: For more on MongoDb, please check out this comprehensive tutorial from Guru99.

# Cassandra

There are plenty of alternatives to MongoDB. Some of the choices out there range from the good ‘ol PostgreSql, Riak and Cassandra, to up and coming (and still improving) RethinkDb.

My personal criteria for determining which database to use are:

• it should be easy for me to set up a cluster with it, i.e. easy to automate, easy to maintain
• it should be easy for me to get started with it (docs, tutorials, good tooling)
• it should be fault tolerant and highly available
• it should be reasonably priced
• it should be boring

Based on that, Cassandra jumps out to me as a better choice. It is highly available and easy to scale, and well documented. It has a thriving community of users, and has been adopted by many dev shops I look up to like Netflix. It is also supported as a backend storage mechanism for Titan, meaning that in my previous scenario I wouldn’t need to rely on Neo4J, thus reducing expenses. I’ve been playing with it recently, and so far it’s been fairly painless. The only drawback: its cost.

UPDATE: For more on Cassandra, please check out this tutorial from Guru99.

If you care about using Cassandra as a service, you could use InstaClustr for a price range of 299$to 404$ a month per node. Setting up the cluster yourself on aws with minimum of 3 m3.large machine would cost you about 300\$ per month. That is more expensive than just MongoDB, less expensive than MongoDB with side databases. In theory, for just an MVP, you could use a smaller ec2 instance at the cost of performance, then switch to recommended configurations once you’ve validated your idea.

The database should be boring. It should at its best be a tool that facilitates building your application, and just a place to dump and retrieve data at its worst. It can help your business grow. It can cause it to fail. Choose wisely.

Tags:


text:
# Uniformly sample pieces of a rectangle

Say I have a rectangle $$R: \left[{0,W}\right] \times \left[{0,H}\right]$$ where $$W$$ is the width and $$H$$ is the height, with coordinates $$\left(x, y\right) \in \mathbb{R}^2$$.

I would like to randomly pick out (axis-aligned) rectangles $$r_s: \left[{x_s-\frac{w_s}{2},x_s+\frac{w_s}{2}}\right] \times \left[{y_s-\frac{h_s}{2},y_s+\frac{h_s}{2}}\right]$$ such that:

• every position in $$R$$ is equally likely to be picked (in the limit, if I overlapped all $$r_s$$, the density with which each point in $$\left(x, y\right) \in R$$ is sampled will be uniform)
• the sampled relative areas $$a_s= \frac{w_s \times h_s}{W \times H}$$ and aspect ratios $$\rho_s = \frac{H}{W} \frac{w_s}{h_s}$$ are also even (I'm not quite sure what the appropriate way to say this would be. But effectively, ideally, I'd like the algorithm to be "scale-free" with respect to $$a_s$$ if it can be. If it can't, then whatever closest notion it actually can be instead is fine. For $$\rho_s$$, I think some sort of cutoff is necessary to avoid divisions by 0, but that is fine. Let's just say there is a $$\rho_{max}$$ and a corresponding $$\rho_{min}=\frac{1}{\rho_{max}}$$)

Additionally, overscanning is allowed (the rₛ may land partially outside R), but at least half the area of the each rₛ must land within R. - If that helps, this also means the $$r_s$$ may actually occasionally be larger than $$R$$. I don't mind if they are but this is not a requirement. I think the largest possible $$r_s$$ would be $$r_{max}: \left[\frac{W}{2}+\frac{\sqrt{2}W}{2},\frac{W}{2}-\frac{\sqrt{2}W}{2}\right] \times \left[\frac{H}{2}+\frac{\sqrt{2}H}{2},\frac{H}{2}-\frac{\sqrt{2}H}{2}\right]$$ with relative area $$a_{max} = 2$$

Is it possible to sample in this manner? And how might one do so efficiently?

The use-case is machine learning and image processing using pytorch, so code is also welcome, however I should be fine if you give me a basic algorithm:

In particular, I have an AI that can process images of at most some fixed resolution. I am generating an image larger than that context size, and in order for the AI to still approximately get the full image, I am sending it pieces of the whole, scaled to fit the AI's context. If I do this unevenly, the AI over-focuses on parts of the image. I'd like it to consider the whole thing as evenly as possible. Every part of the image should be covered evenly, and every scale as well.
Technically, the varying aspect ratio isn't as necessary, however I found that this can help with the robustness of my results.

• Do you mean that $a_s$ and $\rho_s$ should be uniformly distributed? If so, do $a_s$ and $\rho_s$ need to be independent of $x_s$ and $y_s$? Could you also provide some context explaining why you need to do this? Nov 26, 2021 at 13:06
• @JarleTufto I believe independence of $x_s$ and $y_s$ would be desirable, yes Nov 26, 2021 at 13:11
• Then I don't think what you suggest is possible. If you cannot place the centers of the sampled rectangles outside R, then you will get an edge effect making the probability that a point is included in the sampled rectangle smaller towards the boundary of R. Except in the limit that the size of the sampled rectangles tends to zero. Nov 26, 2021 at 13:18
• If either the condition on the overscan or the midpoint independence were relaxed, would it be possible then? Nov 26, 2021 at 13:31
• Yes, if you sample rectangles uniformly from a larger region and reject the ones with no overlap, then there would be no edge effect. Alternatively, if you make the sample rectangles smaller and sample more frequently towards the boundary of R (dependency on $x_s,y_s$), you could maybe devise a method that makes every point in R equally likely to be picked, but that seems like a quite hard problem to solve. Nov 26, 2021 at 13:35

I will describe briefly the assumptions, the algorithm and its properties, and will leave the path for the full mathematical derivation for assertions.

For easy of writing, given $$m \in \, \mathbb{N}$$, consider the notation $$[m] = \{1,\ldots,m\}$$.
The assumptions were:

• We are sampling integer rectangles contained on the rectangle $$[W]\times[H]$$. This seems okay since you said you are working with images;

• The dimensions $$W$$ and $$H$$ are powers of $$2$$. This seems less feasible, but I believe you could scale your images so that this assumptions is satisfied. On the full derivation, it becomes clear why this assumptions is required.

To get an algorithm to sample rectangles, we actually just need an algorithm to sample intervals from an integer interval $$[2^{n}]$$. Fix $$\alpha \, \in \, (0,1)$$, I will now describe a "pseudocode" for $$H_\alpha(n)$$, a recursive method that receives an integer $$n$$ and returns $$[l, r]$$, the left and right index of integer interval from $$[2^{n}]$$:

1. If $$n = 0$$, return $$[1, 1]$$. If not, go to step (2);

2. With probability $$\alpha$$, return $$[1, 2^n]$$. Else, go to step (3);

3. Call $$H_\alpha(n-1)$$ recursively and store its output in $$[l_0, r_0]$$. With probability $$1/2$$, return $$[l_0, r_0]$$. Else, return $$[l_0 + 2^{n-1}, r_0 + 2^{n-1}]$$.

Note: In the algorithm above, assume independence between all random variables used to make decisions where to halt or not.

Let $$W = 2^n$$ and $$H = 2^m$$. To sample a rectangle contained in $$[W]\times[H]$$, let $$(x_1, x_2) = H_\alpha(n)$$ and $$(y_1, y_2) = H_\alpha(m)$$, and assume that $$(x_1, x_2)$$ and $$(y_1, y_2)$$ are independent. Your rectangle is $$R = [x_1, x_2]\times[y_1, y_2]$$.

Here is a python implementation for you:

from random import random

def sample_interval(k):
alpha = 0.4 # Can be any number in (0,1)
if k == 0:
return (0, 0)

# with prob alpha return the whole interval
if random() < alpha:
return (0, 2**k - 1)

l0, r0 = sample_interval(k-1)
# half the times, do not add 2**(k-1)
if random() < 1.0/2:
return (l0, r0)

# half the times, do add 2**(k-1)
else:
return (l0 + 2**(k-1), r0 + 2**(k-1))

# remember that W = 2**n and H = 2**m
def sample_rectangle(n, m):
x1, x2 = sample_interval(n)
y1, y2 = sample_interval(m)

upper = (x1, y1)
lower = (x2, y2)

return (upper, lower)

Now you are surely asking: why sample it like this? The reason is that this algorithm has the properties you want:

(P1) Every integer point (pixel) on $$[W]\times[H]$$ has the same probability of appearing in the sampled rectangle. This probability is constant for all points, but depends on $$n$$ and $$m$$. Asymptotically, if $$W$$ and $$H$$ go to infinite, this probability converges to $$(\frac{2\alpha}{1+\alpha})^2$$;

(P2) The limit average rectangle area divided by the area of the big rectangle is scale free. That is, let $$A_{nm}$$ be the random variable associated with area a rectangle sampled from $$[2^n]\times[2^m]$$ according to this algorithm, then

$$\begin{equation*} a_s = \lim_{n\rightarrow\infty}\lim_{m\rightarrow\infty} \frac{E[A_{nm}]}{W H} = \left(\frac{2\alpha}{1+\alpha}\right)^2 \quad. \end{equation*}$$

Since these are the properties you asked, this sampling method solves your problem. Note that you can change $$\alpha$$ freely. Increasing $$\alpha$$ makes you sample the whole rectangle more. Decreasing it makes you sample smaller rectangles more. If $$\alpha$$ is very close to $$0$$, you will probably end up sampling lone pixels.

Mathematical Proofs The proofs are based on mathematical induction since the algorithm is inherently recursive. We also focus on the proof on the interval case. For the rectangles, it follows trivially from the interval case and independence.

Lets prove all points have equal probability of appearing in the random interval. For $$n = 0$$, it is trivial. Assume that all points in $$[2^{n-1}]$$ have constant probability $$p_{n-1}$$ to appear in a random interval (this obviously depends on $$n$$, but it can not depend on the point).

Now we prove for $$k = n$$. Consider a point in $$[2^k]$$ that is smaller or equal to $$2^{k-1}$$. There are two ways that a random interval can contain this point. First, in the case we sample the whole interval $$[2^k]$$, which has probability $$\alpha$$. Second, if, after not sampling in the first step, the interval from recursive call contains the point AND we do not add $$2^{k-1}$$. This second event has probability $$(1-\alpha)\times p_{n-1}\times\frac{1}{2}$$ (just use independence and the induction hypothesis). Therefore

$$p_n = \alpha + \frac{(1-\alpha)}{2}p_{n-1} \quad.$$

You can prove that the probability is the same if you consider a point above $$2^{k-1}$$. This finishes the proof.

For the average size of the interval, writing $$E_n$$ as the expected interval size, the same idea gives you the recursion

$$E_n = \alpha 2^n + (1-\alpha)E_{n-1} \quad.$$

Now divide both sides by $$2^n$$, we have

$$\frac{E_n}{2^n} = \alpha + \frac{1-\alpha}{2}\frac{E_{n-1}}{2^{n-1}} \quad.$$

Taking the limit and calling it $$e_s$$, we have

$$e_s = \alpha + \frac{1-\alpha}{2}e_s \quad,$$

and a bit of algebra gives you $$e_s = \frac{2\alpha}{1+\alpha}$$. Since the average area of the rectangle is the product of the average size (again, independence), it follows that

$$a_s = e_s^2 \quad,$$

giving you your scale free algorithm.

• If I see that right, you are assuming that the minimum coordinate is (1, 1) and the maximum one is (W = 2^w, H = 2^h)? Very minor thing that's gonna vary between languages and such, but most of the time (python included), you'd want to start with (0, 0) and end with (W-1, H-1) - thanks, this looks very promising. I would prefer if the power-of-2 requirement were dropped for a less stringent rational aspect ratio (which is always possible with integer-dimensioned images) Technically I want this to work for floats, but that might be more trouble than it's worth, so your assumption is fine there Nov 30, 2021 at 21:53
• That is not a problem, just subtract $1$ at the end and you will be fine. I implemented it as $1$ to $W$ just because the recursion is easier to write. I will update the python code to make it range from $0$ to $W-1$. Nov 30, 2021 at 21:54
• Just some quick observations: You can use different $\alpha$ when sampling from intervals from $[W]$ and $[H]$. By selecting the right constants, you can get whichever aspect ratio $\rho_s$ or $a_s$ you want. I considered the same $\alpha$ just for ease of understanding. Moreover, even if you use the same $\alpha$ for both, you can make the asymptotic area ratio $a_s$ be whatever value you want since $f(\alpha) = 2\alpha/(1-\alpha)$ is a bijection from $[0,1]$ to $[0,1]$. Nov 30, 2021 at 22:21
• Ok, I really like, that there is no overscan at all here. I guess if the AI can see an area $h w$ and my image has area $H W$ I'd likely want $a_s$ to be $\frac{h w}{H W}$ giving me $\alpha = \frac{1}{2 \sqrt{\frac{H W}{hw}} - 1}$ as a solid starting point. I can make do with powers of 2 for $H$ and $W$ for now, so I'll accept this answer. If somebody found a way to generalize this to arbitrary (rational) aspect ratios, I'd probably switch to that answer instead. For now this will work though. thank you! Nov 30, 2021 at 22:29
• Yeah that $\alpha$ was meant as an initial guess. Hyperparameter search would definitely be a more rigorous way to figure out a good value for it. Thanks :) Nov 30, 2021 at 22:45

format: plain


text:
0. But in a Gaussian Process (GP), the model will look like this y^ { (i)} = f (x^ { (i)}) + \epsilon^ { (i)} or in matrix form \vec {y} = f (X) + \vec {\epsilon} because the point with GP to find a distribution over the possible functions f that are consistent with the observed data. In Section 2, we brieﬂy review Bayesian methods in the context of probabilistic linear regression. What else can we use GPs for? If we represent this Gaussian Process as a graphical model, we see that most nodes are “missing values”: This is probably a good time to refactor our code and encapsulate its logic as a class, allowing it to handle multiple data points and iterations. In this sessions I will introduce Gaussian processes and explain why sustaining uncertainty is important. What might lead a data scientist to choose a non-parametric model over a parametric model? The key variables here are the βs- we “fit” our linear model by finding the best combinations of β to minimize the difference between our prediction and the actual output: Notice that we only have two β variables in the above form. The prior mean is assumed to be constant and zero (for normalize_y=False) or the training data’s mean (for normalize_y=True).The prior’s covariance is specified by passing a kernel object. Let’s assume a linear function: y=wx+ϵ. Every finite set of the Gaussian process distribution is a multivariate Gaussian. Gaussian process is a generic term that pops up, taking on disparate but quite specific... 5.2 GP hyperparameters. Our aim is to understand the Gaussian process (GP) as a prior over random functions, a posterior over functions given observed data, as a tool for spatial data modeling and surrogate modeling for computer experiments, and simply as a flexible nonparametric regression. This post has hopefully helped to demystify some of the theory behind Gaussian Processes, explain how they can be applied to regression problems, and demonstrate how they may be implemented. That, in turn, means that the characteristics of those realizations are completely described by their 1.7.1. Gaussian Process models are computationally quite expensive, both in terms of runtime and memory resources. The code to generate these contour maps is available here. We have only really scratched the surface of what GPs are capable of. We’ve all heard about Big Data, but there are often times when data scientists must fit models with extremely limited numbers of data points (Little Data) and unknown assumptions regarding the span or distribution of the feature space. One of the most basic parametric models used in statistics and data science is the OLS (Ordinary Least Squares) regression. We could perform grid search (scikit-learn has a wonderful module for implementation), a brute force process that iterates through all possible hyperparameter values to test the best combinations. For the sake of simplicity, we’ll use the Radial Basis Function Kernel, which is defined below: In Python, we can implement this using NumPy. Gaussian Process Regression. It’s important to remember that GP models are simply another tool in your data science toolkit. It is fully determined by its mean m(x) and covariance k(x;x0) functions. Medium’s site status, or find something interesting to read. A simple, somewhat crude method of fixing this is to add a small constant σ² (often < 1e-2) multiple of the identity matrix to Σ. There are a variety of algorithms designed to improve scalability of Gaussian Processes, usually by approximating K(X,X) matrix, with rank N, to a smaller matrix of rank P, with P significantly smaller than N. One technique for addressing this instability is to perform a low-rank decomposition of the covariance kernel. If you have just 3 hyperparameters to tune, each with approximately N possible configurations, you’ll quickly have an O(N³) runtime on your hands. Unlike many popular supervised machine learning algorithms that learn exact values for every parameter in a function, the Bayesian approach infers a probability distribution over all possible values. We can represent these relationships using the multivariate joint distribution format: Each of the K functions deserves more explanation. One of the beautiful aspects of GP is that we can generalize to any dimension data, as we’ve just seen. GPs work very well for regression problems with small training data set sizes. In our Python implementation, we will define get_z() and get_expected_improvement() functions: We can now plot the expected improvement of a particular point x within our feature space (orange line), taking the maximum EI as the next hyperparameter for exploration: Taking a quick ballpark glance, it looks like the regions between 1.5 and 2, an around 5 are likely to yield the greatest expected improvement. It’s simple to implement and easily interpretable, particularly when its assumptions are fulfilled. So how do we start making logical inferences with as limited datasets as 4 games? They’re used for a variety of machine learning tasks, and my hope is I’ve provided a small sample of their potential applications! Gaussian processes are the extension of multivariate Gaussians to inﬁnite-sized collections of real- valued variables. It is fully determined by its mean m(x) and covariance k(x;x0) functions. Limit turnovers, attack the basket, and get to the line. In other words, the number of hidden layers is a hyperparameter that we are tuning to extract improved performance from our model. For that case, the following properties hold: The idea of prediction with Gaussian Processes boils down to, Because that is the most common prior, the poterior is normally this one, The mean is approximately the true value of y_new, http://cs229.stanford.edu/section/cs229-gaussian_processes.pdf, https://blog.dominodatalab.com/fitting-gaussian-process-models-python/, https://github.com/fonnesbeck?tab=repositories, http://fourier.eng.hmc.edu/e161/lectures/gaussianprocess/node7.html, https://www.researchgate.net/profile/Rel_Guzman, Marginalization: The marginal distributions of $x_1$ and $x_2$ are Gaussian, Conditioning: The conditional distribution of $\vec{x}_i$ given $\vec{x}_j$ is also normal with. Gaussian Distributions and Gaussian Processes • A Gaussian distribution is a distribution over vectors. We have only really scratched the surface of what GPs are capable of. This approach was elaborated in detail for the matrix-valued Gaussian processes and generalised to processes with 'heavier tails' like Student-t processes. Names Similar To Snow, Cinnamon Stick In Coffee, Hyaluronic Acid Serum The Ordinary, Camellia Cuttings Australia, Selena Gomez And The Scene, Mobile Homes For Rent In Lecanto, Fl, Pecan Tree Scab, ">
RheumInfo Blog

# gaussian process explained

Typically, when performing inference, x is assumed to be a latent variable, and y an observed variable. They rely upon a measure of similarity between points (the kernel function) to predict the value for an unseen point from training data. GAUSSIAN PROCESSES 3 be constructed from i.i.d. GPs are used to define a prior distribution of the functions that could explain our data. We are interested in generating f* (our prediction for our test points) given X*, our test features. The covariance function determines properties of the functions, like smoothness, amplitude, etc. It is defined by the following attributes: K here is the kernel function (in this case, a Gaussian): Clearly, as the number of data points (N) increases, the more computations are necessary within the kernel function K, and the more summations of each data point’s weighted contribution are needed to generate the prediction y*. Notice that Rasmussen and Williams refer to a mean function and covariance function. We have a prior set of observed variables (X) and their corresponding outputs (y). Off the shelf, without taking steps … Gaussian process regression (GPR) is an even ﬁner approach than this. Moreover, they can be used for a wide variety of machine learning tasks- classification, regression, hyperparameter selection, even unsupervised learning. And conditional on the data we have observed we can find a posterior distribution of functions that fit the data. A Gaussian is defined by two parameters, the mean μ μ, and the standard deviation σ σ. μ μ expresses our expectation of x x and σ σ our uncertainty of this expectation. Since the 3rd and 4th elements are identical, we should expect to see the third and fourth row/column pairings to be equal to 1 when executing RadialBasisKernel.compute(x,x): Now, we can start with a completely standard unit Gaussian (μ=0, σ=1) as our prior, and begin incorporating data to make updates. This brings benefits, in that uncertainty of function estimation is sustained throughout inference, and some challenges: algorithms for fitting Gaussian processes tend to be more complex than parametric models. The areas of greatest uncertainty were the specific intervals where the model had the least information (x = [5,8]). I compute the Σ (k_x_x) and its inversion immediately upon update, since it’s wasteful to recompute this matrix and invert it for each new data point of new_predict(). A Gaussian process is a distribution over functions fully specified by a mean and covariance function. For instance, sometimes it might not be possible to describe the kernel in simple terms. This post has hopefully helped to demystify some of the theory behind Gaussian Processes, explain how they can be applied to regression problems, and demonstrate how they may be implemented. Here’s a quick reminder how long you’ll be waiting if you attempt a native implementation with for loops: Now, let’s return to the sin(x) function we began with, and see if we can model it well, even with relatively few data points. As luck would have it, both the marginal and conditional distribution of a subset of a multivariate Gaussian distribution are normally distributed themselves: That’s a lot of covariance matrices in one equation! We assume the mean to be zero, without loss of generality. Row reduction is the process of performing row operations to transform any matrix into (reduced) row echelon form. The explanation for Gaussian Processes from CS229 Notes is the best I found and understood. This identity is essentially what scikit-learn uses under the hood when computing the outputs of its various kernels. Moreover, in the above equations, we implicitly must run through a checklist of assumptions regarding the data. Chapter 5 Gaussian Process Regression. Gaussian distribution (also known as normal distribution) is a bell-shaped curve, and it is assumed that during any measurement values will follow a normal distribution with an equal number of measurements above and below the mean value. Gaussian process (GP) is a very generic term. Image Source: Gaussian Processes for Machine Learning, C. E. Rasmussen & C. K. I. Williams Gaussian Process Regression has the following properties: GPs are an elegant and powerful ML method; We get a measure of (un)certainty for the predictions for free. ), a Gaussian process can represent obliquely, but rigorously, by letting the data ‘speak’ more clearly for themselves. With this article, you should have obtained an overview of Gaussian processes, and developed a deeper understanding on how they work. Note: In this next section, I’ll be utilizing a heavy dose of Rasmussen & Willliams’ derivations, along with a simplified and modified version of Chris Follensbeck’s “Fitting Gaussian Process Models in Python” toy examples in the following walkthrough. ×.. To overcome this challenge, learning specialized kernel functions from the underlying data, for example by using deep learning, is an area of … It is for these reasons why non-parametric models and methods are often valuable. In this method, a 'big' covariance is constructed, which describes the correlations between all the input and output variables taken in N points in the desired domain. Here the goal is humble on theoretical fronts, but fundamental in application. If we plot this function with an extremely high number of datapoints, we’ll essentially see the smooth contours of the function itself: The core principle behind Gaussian Processes is that we can marginalize over (sum over probabilities associated with the possible instances and state configurations) of all the unseen data points from the infinite vector (function). Let’s say we receive data regarding brand lift metrics over the winter holiday season, and are trying to model consumer behavior over that critical time period: In this case, we’ll likely need to use some sort of polynomial terms to fit the data well, and the overall model will likely take the form. This leaves only a subset (of observed values) from this infinite vector. For solution of the multi-output prediction problem, Gaussian process regression for vector-valued function was developed. The Gaussian process regression (GPR) is yet another regression method that fits a regression function to the data samples in the given training set. • … Gaussian Processes are non-parametric models for approximating functions. This “parameter sprawl” is often undesirable since the number of parameters within the model itself is a parameter, depending upon the dataset at hand. For instance, while creating GaussianProcess, a large part of my time was spent handling both one-dimensional and multi-dimensional feature spaces. However, the linear model shows its limitations when attempting to fit limited amounts of data, or in particular, expressive data. • A Gaussian process is a distribution over functions. Laplace Approximation for GP Probit regression likelihood A slight alteration of that system (for example, changing the constant term “7” in the third equation to a “6”) will illustrate a system with infinitely many solutions. I followed Chris Fonnesbeck’s method of computing each individual covariance matrix (k_x_new_x, k_x_x , k_x_new_x_new)independently, and then used these to find the prediction mean and updated Σ (covariance matrix): The core computation in generating both y_pred (the mean prediction) and updated_sigma (the covariance matrix) is inverting np.linalg.inv(k_x_x). x ∼ N (μ,σ) x ∼ N (μ, σ) A multivariate Gaussian is parameterized by a generalization of μ μ and σ σ … I’ve only barely scratched the surface of the applications for Gaussian Processes. This post is primarily intended for data scientists, although practical implementation details (including runtime analysis, parallel computing using multiprocessing, and code refactoring design) are also addressed for data and software engineers. A real-valued mathematical function is, in essence, an infinite-length vector of outputs. The following example shows that some restriction on the covariance is necessary. The book is also freely available online. What if instead, our data was a bit more expressive? ... A Gaussian Process … Chapter 5 Gaussian Process Regression 5.1 Gaussian process prior. From the above derivation, you can view Gaussian process as a generalization of multivariate Gaussian distribution to infinitely many variables. When computing the Euclidean distance numerator of the RBF kernel, for instance, make sure to use the identity. Comments Source: The Kernel Cookbook by David Duvenaud It always amazes me how I can hear a statement uttered in the space of a few seconds about some aspect of machine learning that then takes me countless hours to … In this post, we discuss the use of non-parametric versus parametric models, and delve into the Gaussian Process Regressor for inference. We assume the mean to be zero, without loss of generality. We see, for instance, that even when Steph attempts many free throws, if his turnovers are high, he’ll likely score below average points per page. What are some common techniques to tune hyperparameters? Since this is an Nx N matrix, runtime is O(N³), more specifically O(N³/6) using Cholesky decomposition instead of directly inverting the matrix ,as outlined by Rasmussen and Williams. 1 Bayesian linear regression as a GP The Bayesian linear regression model of a function, covered earlier in the course, is a Gaussian process. This led to me refactoring the Kernel.get() static method to take in only 2D NumPy arrays: As a gentle reminder, when working with any sort of kernel computation, you will absolutely want to make sure you vectorize your operations, instead of using for loops. For this, the prior of the GP needs to be specified. We’ll put all of our code into a class called GaussianProcess. Intuitively, in relatively unexplored regions of the feature space, the model is less confident in its mean prediction. It takes hours to train this neural network (perhaps it is on an extremely compute-heavy CNN, or is especially deep, requiring in-memory storage of millions and millions of weight matrices and gradients during backpropagation). Gaussian Process, not quite for dummies. Exercise1.3. Gaussian Processes. As we have seen, Gaussian processes offer a flexible framework for regression and several extensions exist that make them even more versatile. In order to understand normal distribution, it is important to know the definitions of “mean,” “median,” and “mode.” There are times when Σ is by itself is a singular matrix (is not invertible). The central ideas under-lying Gaussian processes are presented in Section 3, and we derive the full Gaussian process … Off the shelf, without taking steps … That, in turn, means that the characteristics of those realizations are completely described by their The idea of prediction with Gaussian Processes boils down to "Given my old x, and the y values for those x, what do I expect y to be for a new x? Consistency: If the GP speciﬁes y(1),y(2) ∼ N(µ,Σ), then it must also specify y(1) ∼ N(µ 1,Σ 11): A GP is completely speciﬁed by a mean function and a Keywords Covariance Function Gaussian Process Marginal Likelihood Posterior Variance Joint Gaussian Distribution Do (updated by Honglak Lee) May 30, 2019 Many of the classical machine learning algorithms that we talked about during the rst half of this course t the following pattern: given a training set of i.i.d. Even without distributed computing infrastructure like MapReduce or Apache Spark, you could parallelize this search process, of course, taking advantage of multi-core processing commonly available on most personal computing machines today: However, this is clearly not a scalable solution- even assuming perfect efficiency between processes, the reduction in runtime is linear (split between n processes, while the search space increases quadratically. Then, in section 2, we will show that under certain re-strictions on the covariance function a Gaussian process can be extended continuously from a countable dense index set to a continuum. All it means is that any finite collection of r ealizations (or observations) have a multivariate normal (MVN) distribution. of multivariate Gaussian distributions and their properties. Rather than claiming relates to some speciﬁc models (e.g. Similarly, K(X*, X*) is a n* x n* matrix of covariances between test points, and K(X, X) is a n x n matrix of covariances between training points, and frequently represented as Σ. The next step is to map this joint distribution over to a Gaussian Process. Figure: A key reference for Gaussian process models remains the excellent book "Gaussian Processes for Machine Learning" (Rasmussen and Williams (2006)). Gaussian process models are an alternative approach that assumes a probabilistic prior over functions. For instance, let’s say you are attempting to model the relationship between the amount of money we spend advertising on a social media platform, and how many times our content is shared- at Operam, we might use this insight to help our clients reallocate paid social media marketing budgets, or target specific audience demographics that provide the highest return on investment (ROI): We can easily generate the above plot in Python using the Numpy library: This data will follow a form many of us are familiar with. All it means is that any finite collection of r ealizations (or observations) have a multivariate normal (MVN) distribution. However, after only 4 data points, the majority of the contour map features an output (scoring) value > 0. But in a Gaussian Process (GP), the model will look like this y^ { (i)} = f (x^ { (i)}) + \epsilon^ { (i)} or in matrix form \vec {y} = f (X) + \vec {\epsilon} because the point with GP to find a distribution over the possible functions f that are consistent with the observed data. In Section 2, we brieﬂy review Bayesian methods in the context of probabilistic linear regression. What else can we use GPs for? If we represent this Gaussian Process as a graphical model, we see that most nodes are “missing values”: This is probably a good time to refactor our code and encapsulate its logic as a class, allowing it to handle multiple data points and iterations. In this sessions I will introduce Gaussian processes and explain why sustaining uncertainty is important. What might lead a data scientist to choose a non-parametric model over a parametric model? The key variables here are the βs- we “fit” our linear model by finding the best combinations of β to minimize the difference between our prediction and the actual output: Notice that we only have two β variables in the above form. The prior mean is assumed to be constant and zero (for normalize_y=False) or the training data’s mean (for normalize_y=True).The prior’s covariance is specified by passing a kernel object. Let’s assume a linear function: y=wx+ϵ. Every finite set of the Gaussian process distribution is a multivariate Gaussian. Gaussian process is a generic term that pops up, taking on disparate but quite specific... 5.2 GP hyperparameters. Our aim is to understand the Gaussian process (GP) as a prior over random functions, a posterior over functions given observed data, as a tool for spatial data modeling and surrogate modeling for computer experiments, and simply as a flexible nonparametric regression. This post has hopefully helped to demystify some of the theory behind Gaussian Processes, explain how they can be applied to regression problems, and demonstrate how they may be implemented. That, in turn, means that the characteristics of those realizations are completely described by their 1.7.1. Gaussian Process models are computationally quite expensive, both in terms of runtime and memory resources. The code to generate these contour maps is available here. We have only really scratched the surface of what GPs are capable of. We’ve all heard about Big Data, but there are often times when data scientists must fit models with extremely limited numbers of data points (Little Data) and unknown assumptions regarding the span or distribution of the feature space. One of the most basic parametric models used in statistics and data science is the OLS (Ordinary Least Squares) regression. We could perform grid search (scikit-learn has a wonderful module for implementation), a brute force process that iterates through all possible hyperparameter values to test the best combinations. For the sake of simplicity, we’ll use the Radial Basis Function Kernel, which is defined below: In Python, we can implement this using NumPy. Gaussian Process Regression. It’s important to remember that GP models are simply another tool in your data science toolkit. It is fully determined by its mean m(x) and covariance k(x;x0) functions. Medium’s site status, or find something interesting to read. A simple, somewhat crude method of fixing this is to add a small constant σ² (often < 1e-2) multiple of the identity matrix to Σ. There are a variety of algorithms designed to improve scalability of Gaussian Processes, usually by approximating K(X,X) matrix, with rank N, to a smaller matrix of rank P, with P significantly smaller than N. One technique for addressing this instability is to perform a low-rank decomposition of the covariance kernel. If you have just 3 hyperparameters to tune, each with approximately N possible configurations, you’ll quickly have an O(N³) runtime on your hands. Unlike many popular supervised machine learning algorithms that learn exact values for every parameter in a function, the Bayesian approach infers a probability distribution over all possible values. We can represent these relationships using the multivariate joint distribution format: Each of the K functions deserves more explanation. One of the beautiful aspects of GP is that we can generalize to any dimension data, as we’ve just seen. GPs work very well for regression problems with small training data set sizes. In our Python implementation, we will define get_z() and get_expected_improvement() functions: We can now plot the expected improvement of a particular point x within our feature space (orange line), taking the maximum EI as the next hyperparameter for exploration: Taking a quick ballpark glance, it looks like the regions between 1.5 and 2, an around 5 are likely to yield the greatest expected improvement. It’s simple to implement and easily interpretable, particularly when its assumptions are fulfilled. So how do we start making logical inferences with as limited datasets as 4 games? They’re used for a variety of machine learning tasks, and my hope is I’ve provided a small sample of their potential applications! Gaussian processes are the extension of multivariate Gaussians to inﬁnite-sized collections of real- valued variables. It is fully determined by its mean m(x) and covariance k(x;x0) functions. Limit turnovers, attack the basket, and get to the line. In other words, the number of hidden layers is a hyperparameter that we are tuning to extract improved performance from our model. For that case, the following properties hold: The idea of prediction with Gaussian Processes boils down to, Because that is the most common prior, the poterior is normally this one, The mean is approximately the true value of y_new, http://cs229.stanford.edu/section/cs229-gaussian_processes.pdf, https://blog.dominodatalab.com/fitting-gaussian-process-models-python/, https://github.com/fonnesbeck?tab=repositories, http://fourier.eng.hmc.edu/e161/lectures/gaussianprocess/node7.html, https://www.researchgate.net/profile/Rel_Guzman, Marginalization: The marginal distributions of $x_1$ and $x_2$ are Gaussian, Conditioning: The conditional distribution of $\vec{x}_i$ given $\vec{x}_j$ is also normal with. Gaussian Distributions and Gaussian Processes • A Gaussian distribution is a distribution over vectors. We have only really scratched the surface of what GPs are capable of. This approach was elaborated in detail for the matrix-valued Gaussian processes and generalised to processes with 'heavier tails' like Student-t processes.


text:
### Home > INT2 > Chapter 2 > Lesson 2.3.1 > Problem2-79

2-79.

Copy each of the area models below and fill in the missing dimensions and areas. Then write the entire area as a product equivalent to the area as a sum.

1.  generic rectangle interior left $2xy$ interior right $8y$ bottom right edge $x$ bottom right edge is blank

Try to find a way to factor what is inside of the boxes, then it is possible to write the area as a product of its sum.

$2xy+8y=2y(x+4)$

1.  generic rectangle interior top left $x^2$ interior top right is blank interior bottom left $8x$ interior bottom right is blank bottom edge left is blank bottom edge right $+5$

$(x+8)(x+5)=x^2+13x+40$

1.  generic rectangle left edge top is blank interior top left is blank interior top middle $-3xy$ interior top right is blank left edge bottom $-4$ interior bottom left$-8z$ interior bottom middle is blank interior bottom right$-20$ bottom edge left is blank bottom edge middle $-3y$ bottom edge right is blank

$(x−4)(2z−3y+5)=2xz-3xy+5x-$
$8z+12y−20$.

1.  generic rectangle left edge right $x$ interior top right $x^2$ interior top right is blank left edge bottom is blank interior bottom left is blank interior bottom right $6$


text:
To submit this assignment, upload the full document on blackboard, including the original questions, your code, and the output. Submit your assignment as a knitted .pdf (preferred) or .html file.

1. In this exercise, we will continue to use the vector community and malaria survey data collected by Mbogo et al. (2003) (i.e., kenya.wide.csv). We will inspect whether spatial autocorrelation affects our inference of the effects of vector abundance, species richness, and composition, on malaria prevalence. We will also investigate which environmental factors underpin the distribution of mosquitoes, all in the context of space. (4 marks).

1. Compute Moran’s autocorrelation statistic to assess whether mosquito abundance and species richness, and malaria prevalence are correlated in space. (1 mark)

2. Extract annual average temperature and rainfall data from WorldClim2 using the raster files provided in class. Create maps (see appendix to lecture notes) to show the variation in these climatic factors across the sites. (1 mark)

3. Investigate whether rainfall influence mosquito abundance across sites. Your complete analysis should include formally testing whether the temperature and rainfall patterns across sites are correlated in space (construct a variogram and interpret when neccessary), regression models with the appropriate autocorrelation structure, and an interpretation of your model outputs. Feel free to make use of additional plots to help explain your findings (2 mark)

2. Simulating data (2 marks)

1. Generate a gamma distribution by randomly sampling 30 points from a distribution with shape parameter equal to 1.35 and rate parameter equal to 0.5. Plot this distribution. Set a seed of 42. (0.5 mark).

2. Plot the distribution of sample means obtained by generating 5000 gamma distributions with the same parameters as in (a). In other words, the distribution should be made up of 5000 means, each from a different simulated gamma distribution. Set a seed of 43. What do you notice about this distribution when compared to the original distribution in (a)? Why would we expect this? (0.5 marks)

3. In this exercise you will simulate a multiple regression. Remember, multiple regression means that there is more than one explanatory (aka predictor, independent) variable for a given response variable. Multiple regression thus estimates a separate effect (i.e. beta) for each explanatory variable in the model, while holding the other variables constant. This exercise is only a slight extension of the model that we simulated in lecture. Simulate a model that satisfies the conditions below and show the model output using summary(). Set a seed of 44. (1 mark).

1. x1 is an explanatory variable with sequence from 51 to 70 with 1 unit intervals between each value (i.e. 20 values total).
2. x2 is an explanatory variable of length 20 randomly drawn for a normal distribution with mean equal to 62 and standard deviation equal to 2.7.
3. x3 is an explanatory variable of length 20 randomly drawn for a gamma distribution with shape equal to 5 and rate equal to 0.5.
4. the y_intercept is 22
5. The beta associated with x1 is 0.62.
6. The beta associated with x2 is 0.047
7. The beta associated with x3 is 0.185
8. The error is drawn from a normal distribution with mean equal to 0 and standard deviation equal to 1.65.
9. y is a linear combination of x1, x2 and x3. There are no interations.
3. Randomization test (2 marks)

Run the code chunk below to load the data that will be used in this exercise.

library(tidyverse)
df <- "https://uoftcoders.github.io/rcourse/data/Assign05_Question3.csv"
glimpse(df)
## Observations: 60
## $x <dbl> 6.426000, 5.120825, 5.525578, 5.067441, 4.877366, 5.581507, 5.3… ##$ group <chr> "One", "One", "One", "One", "One", "One", "One", "One", "One", …
1. Generate a histogram showing the null distribution of t-statistics between groups one and two from the df dataframe that you just loaded. The null distribution should be based 5,000 reshufflings of the data. (1 mark). Overlay onto this histogram the observed t-statistic as a dashed vertical line. Set a seed of 45. Hint: t-tests return list objects that can be indexed using \$`


text:
# Sigma-Congruence

2010 Mathematics Subject Classification: Primary: 68P05 [MSN][ZBL]

A $\Sigma$-congruence is a congruence relation defined on a $\Sigma$-algebra. They provide a method to represent term-generated $\Sigma$-algebras using quotient algebras of the ground term algebra $T(\Sigma)$. Such methods are important for getting an overview of the (isomorphism classes of) possibly existing term-generated $\Sigma$-algebras, and thus for getting an overview of the possible semantical behaviours associated with the signature $\Sigma=(S,F)$.

### Definition of $\Sigma$-congruences

Let $A$ be a $\Sigma$-algebra defined over a signature $\Sigma=(S,F)$. A $\Sigma$-congruence is an $S$-sorted equivalence relation $(\sim_s)_{s\in S}$ defined on $A$ with $\sim_s\subseteq s^A\times s^A$, which is compatible with the operations $f^A$, $f\in F$ of $A$. Compatibility means in this case that for each $f\in F$ with $\mathrm{type}(f)= s_1\times\cdots\times s_n \longrightarrow s$ and for each $x_i,y_i\in A_{s_i}$ with $x_i \sim_{s_i} y_i$ it holds $f^A(x_1,\ldots,x_n) \sim_s f^A(y_1,\ldots,y_n)$. If no reference to a specific $\Sigma$-algebra $A$ is made, the ground term algebra $T(\Sigma)$ is considered (under the assumption of a sensible signature $\Sigma$). The relation $\sim_s$ designates the restriction of $\sim$ to the sort $s\in S$.

For a $\Sigma$-algebra $A$, the set $C(A)$ of all $\Sigma$-congruences for $A$ forms a complete lattice w.r.t. set-theoretic inclusion [EM85][W90]. Its least element is the identity congruence $\sim^{T(A)} := \{(a,a)\mid a\in A\}$ over $A$. Its greatest element is the universal congruence $\sim^{U(A)} := \{(a,a')\mid a,a'\in s^A, s\in S\}$ over $A$. The least element $\sim^{T(A)}$ corresponds to the initial algebra $T(\Sigma)$ (i.e. the ground term algebra) of $\mathrm{Alg}(\Sigma)$ and $\mathrm{Gen}(\Sigma)$. The greatest element $\sim^{U(A)}$ corresponds to the terminal algebra $U(\Sigma)$ of $\mathrm{Alg}(\Sigma)$ and $\mathrm{Gen}(\Sigma)$ [W90].

For a $\Sigma$-algebra $A$ and a family $K=\{\sim_i\}_{i\in I}\subseteq C(A)$ of $\Sigma$-congruences defined on $A$, the infimum of $K$ coincides with the set-theoretic intersection, i.e. $(\bigcap\limits_{i\in I} (\sim_i)_s)_{s\in S} =\inf_{i\in I} \sim_i$ [EM85]. As an immediate consequence, the set-theoretic intersection of a family $\{\sim_i\}_{i\in I}$ of $\Sigma$-congruences is again a $\Sigma$-congruence defined on $A$. Furthermore, for an $S$-sorted binary relation $\approx\subseteq A\times A$ defined on $A$ there exists a least (with respect to $\subseteq$) $\Sigma$-congruence $\sim \in C(A)$ defined on $A$ whith $\approx\subseteq\sim$ [ST99].

### Construction of $\Sigma$-Congruences

$\Sigma$-Congruences are directly related to $\Sigma$-algebra-morphism. It is possible to construct a $\Sigma$-congruence $\sim^m$ on a $\Sigma$-algebra $A$ using a $\Sigma$-algebra-morphism $m\colon A\longrightarrow B$ between $A$ and another $\Sigma$-algebra $B$. The $\Sigma$-congruence $\sim^m = (\sim^m_s)_{s\in S}$ is defined via $x\sim^m_s y :\Longleftrightarrow m_s(x)=m_s(y)$ for $x,y\in A$. It is called the $\Sigma$-congruence induced by $m$ [W90].

In the following, we consider a sensible signature $\Sigma$ for assuring the existence of the corresponding ground term algebra $T(\Sigma)$. For a $\Sigma$-algebra $A$, one can define an associated $\Sigma$-congruence $\sim^A\in C(T(\Sigma))$ by $t_1\sim^A t_2 \colon\Longleftrightarrow t_1^A = t_2^A$ for $t_1,t_2\in T_s(\Sigma)$, $s\in S$. In particular, any $\Sigma$-congruence $\sim\in C(X)$ is associated with $T(\Sigma)/\sim$ [W90].

### Application I: Quotient Algebras

The identification of terms $t,t'\in T(\Sigma)$ related to each other by a $\Sigma$-congruence leads to so-called quotient $\Sigma$-algebras of the ground term algebra $T(\Sigma)$. Each term-generated $\Sigma$-algebra can be represented in this way. Formally, a quotient algebra is defined ion the following way.

Let $\sim \in C(A)$ be a $\Sigma$-congruence defined on a $\Sigma$-algebra $A$. Then the quotient $\Sigma$-algebra $A/\sim$ is defined as follows [M89].

• $s^{A/\sim} :=\{[a]_\sim\mid a\in s^A\}$
• $f^{A/\sim} := [f^A]_\sim$ for $f\in F$ with $\mathrm{type}(f)=\,\,\rightarrow s\}$
• $f^{A/\sim}([a_1],\ldots,[a_n]) := [f^A(a_1,\ldots,a_n)]$, $f\in F$, with $\mathrm{type}(f)= s_1\times\cdots\times s_n \longrightarrow s$ and for $a_i\in s_i^A$.

$A/\sim \in \mathrm{Alg}(\Sigma)$ is a $\Sigma$-algebra. Its definition is well-defined because of the congruence property of $\sim$ [EM85]. Corresponding to $A/\sim$, one can define mappings $m_s\colon s^A \longrightarrow s^A/\sim_s; a \mapsto [a]_{\sim_s}$ for $s \in S$. Then $m=(m_s)_{s\in S} \colon A \longrightarrow A/\sim$ is a surjective $\Sigma$-algebra-morphism [M89]. It has the following universal property: Let $B$ be a $\Sigma$-algebra and $f\colon A\longrightarrow B$ be a $\Sigma$-algebra-morphism with $\sim \subseteq \sim_f$. Then there is a unique $\Sigma$-algebra-morphism $\bar f \colon A/\sim\longrightarrow B$ such that $f_s(a) = \bar f_s([a]_{\sim_s})$ for all $s \in S$ and $a \in s^A$. If $\sim = \sim_f$ then $\bar f$ is injective [EM85]. If $f$ is surjective, then $B\cong A/\sim^m$ [M89].

The above property characterizes quotient algebras up to isomorphism. It follows in particular that for any $\Sigma$-algebra-morphism $m\colon A \longrightarrow B$, $A/\sim_m$ is isomorphic to the image $m(A)$ of $A$ under $m$ [ST99].

### Application II: Term-generated $\Sigma$-Algebras

An application of $\Sigma$-congruences is the representation of a term-generated $\Sigma$-algebra using the ground term algebra $T(\Sigma)$ in the case of a sensible signature $\Sigma$. Together with $\Sigma$-algebra-morphism, one has two different options to describe a term-generated $\Sigma$-algebra $A$ in this way. More precisely, we can state that a $\Sigma$-algebra $A$ is term-generated iff it is isomorphic to a quotient algebra $T(\Sigma)/\sim$ of the ground term algebra $T(\Sigma)$ with $\sim=\sim^A$ [W90]. This is the case, in turn, iff it is the image of $T(\Sigma)$ under a $\Sigma$-algebra-morphism.

It follows that there is a one-to-one correspondence between isomorphism classes of term-generated $\Sigma$-algebras and congruences on $T(\Sigma)$ [ST99]. Especially, for term-generated $\Sigma$-algebras $A,B$ it holds $A\cong B$ iff $\sim^A= \sim^B$ [W90]. For a term-generated $\Sigma$-algebra $A$ and for a $\Sigma$-algebra $B$, it exists a $\Sigma$-morphism $m\colon A\longrightarrow B$ iff $\sim^A\subseteq \sim^B$ [W90].

### References

 [EM85] H. Ehrig, B. Mahr: "Fundamentals of Algebraic Specifications", Volume 1, Springer 1985 [EM90] H. Ehrig, B. Mahr: "Fundamentals of Algebraic Specifications", Volume 2, Springer 1990 [M89] B. Möller: "Algorithmische Sprachen und Methodik des Programmierens I", lecture notes, Technical University Munich 1989 [ST99] D. Sannella, A. Tarlecki, "Algebraic Preliminaries", in Egidio Astesiano, Hans-Joerg Kreowski, Bernd Krieg-Brueckner, "Algebraic Foundations of System Specification", Springer 1999 [W90] M. Wirsing: "Algebraic Specification", in J. van Leeuwen: "Handbook of Theoretical Computer Science", Elsevier 1990
How to Cite This Entry:
Sigma-Congruence. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Sigma-Congruence&oldid=29449


text:
## Monday, May 30, 2011

### WSOP Utility Analysis revisited, part 1: How much of an edge is necessary to overcome tax and utility effects in the WSOP Main Event?

A few months ago, I looked at the true costs of playing the WSOP Main Event for the typical player after adjusting for the effects of tax and risk aversion. It's worth a read if you missed it. Overall, we found that there are significant tax and utility effects that a player must overcome, and thus that there is significant extra effective rake in playing the event.

Exactly how much of a skill advantage does a prospective WSOP Main Event player need in order to overcome this effective rake? Can we... quantify it?

The old model was built on the assumption that the average player was equally likely to finish in any of the 7,319 places in the tournament. To allow for our player in question to have a level of skill different from that of the rest of the field, we need a way to map player skill to a specific finish probability distribution, a specification for the probabilities of finishing in each of the 7,319 different places.

Connecting skill edge to a finish probability distribution

If we generalize our scope to a tournament with N players, then we know that, when all players are equally skilled, each player will finish in each place with probability 1/N, as we've stuck to in the old model. If a specific player has a different strategy than the other players (whom we will assume to all still be uniformly skilled), then what does his finish probability distribution look like?

We quantify skill through the typical tournament results convention of raw ROI, which we define as the player's pure return on investment in the absence of tax and utility considerations, but including the rake. For example, in the WSOP main event, since $600 of the$10,000 entry fee goes to rake, the average player's raw ROI is -6%. This is ROI as it is commonly used in discussions and in tracking software; we add "raw" to convey that it is in pure dollar terms, without utility or tax effects. Since this is the measure of skill edge that is commonly used, it is desirable for us to define our correspondence between player strategy and finish probability distribution by creating a mapping between raw ROI and a probability distribution.

My first naïve method of constructing such a family of finish probability distributions was to start from the uniform 1/N distribution, but to perturb the terms such that the probability of finishing in each place was equal to a uniform constant plus the probability of finishing in the prior place. In math, this family of distributions looks like:

In addition to the necessary properties of probability distributions (nonnegative probabilities which sum to 1), this naïve distribution has a basic property that would likely be desirable in any probability distribution for tournament finishes: the distribution is increasing in that, when the player's skill edge is positive, he has a higher probability of finishing in each place than he does the next-worst place. (Similarly, when the player's skill edge is negative, he has a higher probability of finishing in each place than he does the next-higher place.)

However, there is no reason that the increasing increments between each place should be equal throughout the entire distribution, as they are here. Our simple guess may not approximate reality very well. There's also another problem with this family of distributions: it turns out that we can't capture every possible ROI (from -100% to a certain 1st place) through this type of distribution.

Note that this model, as well as all of the forthcoming models, produces the desired result of uniform probabilities of 1/N when we set the player's skill to zero.

A second naïve guess for developing a family of finish probability distributions is to reframe the tournament as a series of heads-up matches, and to give our player a specific probability for winning each heads-up match. This generalizes through logarithms to tournament field sizes that are not powers of 2. In this approach, we get a different probability distribution depending on whether or not we start from the probability of getting 1st place and use conditional probabilities downward through the places, or whether we instead start from the bottom and "condition upwards". If we condition downwards, this distribution looks like:

This is again an increasing distribution, and one that should make sense for a bona fide heads-up tournament with 2^k players, but other than that, there is no intuition as to how it might apply to a non-heads-up tournament.

The most elegant and accurate approach that I've come across is one based on the following foundation: we assume that a single player who is superior to his uniform opponents and who is playing in a tournament with equal starting stacks (as is the case in real poker tournaments) might have a similar finish probability distribution to a player who is not superior to his opponents, but instead starts the tournament with a larger chip stack than the rest of the field. (Thanks to Aaron Brown for this idea for modeling finish probability distributions, and if you enjoy both poker and finance and have not read his excellent book The Poker Face of Wall Street, you are missing out.)

To reiterate:

A superior player's skill edge in a tournament could be approximated in a model that removes his strategic advantage but instead gives him a larger starting chip stack.

From this point, we just need a way of mapping one's chip stack to one's finish probability distribution. The most popular method of this is the Independent Chip Model, i.e. the Malmuth-Harville tournament chip valuation algorithm, and that's what I've chosen to use, as it happens to produce an identical result to instead parameterizing the player's skill edge by starting with his probability of finishing in 1st place and then conditioning downwards. We don't get a closed-form formula, but we get an iterative formula that is easy to implement in Excel:

See The Mathematics of Poker for a discussion of other methods of tournament chip stack valuation; it seems that Malmuth-Weitzman is the only reasonable competing theory to ICM out there, and it only differs from ICM in how a busted player's chips are distributed among the remaining players on average. I haven't spent too much time thinking about the differences between these models. My understanding is that each of them diverges from real historical tournament results, though I do not know if anybody has analyzed this rigorously.

Adding this finish probability distribution to the WSOP expected utility analysis

The hard part's done! Now we can just take this parameterized finish probability distribution and plug it into our good old WSOP Main Event expected utility analysis and see what we get.

We see that, under this model, the relationship between the CE payoff and the player's raw ROI is close to linear. Examining the data confirms that this visual intuition is accurate.

In particular, we see that, for our typical player ($80k net worth,$50k income with at least $10k from poker, risk aversion of 0.8), the ROI needed to simply break even after tax and utility considerations is 86%. So that answers the question we were left with when we first looked at expected utility analysis for the WSOP Main Event. After correcting for tax effects and risk aversion, the typical player needs to have a raw ROI of 86% in order to break even in certainty equivalent by playing the WSOP Main Event. Having higher net worth helps alleviate this high threshold. A player with a net worth of$500,000 and a YTD salary of $100,000 needs a 42% ROI to break even. A player with a net worth of$5,000,000 and a YTD salary of $1,000,000 needs only a 7% ROI. Again, we see that the WSOP Main Event is best suited towards the wealthy, despite its "everyman" appeal... though it is precisely the fact that the event appeals to so many everymen that causes the risk to be too great for them. Being less naturally risk-averse also brings down this threshold. The typical player with$80,000 net worth and a YTD salary of $50,000 needs only a 61% ROI if we reduce his ρ from 0.8 to 0.5. Further reducing ρ to 0.2 still leaves him needing a 33% ROI. Reducing it all the way to 0 (i.e. no risk-aversion, and utility is realized on the full amount of dollars remaining after taxes) brings it down to a 11% ROI. Risk aversion is demanding a higher minimum skill level than tax effects are. Coming up next... That's all for today, since building the finish probability distribution took so long. But now that the hard part's out of the way, we can play around with our expanded model in some other practical ways. Note that I realize that this year's WSOP Main Event is likely to have far fewer than 7,319 competitors. For a smaller tournament, both tax and utility effects will be lessened, and lower skill edge will be necessary to overcome these. It would be interesting to generalize this model to an arbitrary N-player tournament, if there were an algorithmic, standardized payout formula that covered all possible field sizes. (Does one exist for any popular tournament series? Drop me a comment if there is one.) For now, knowing that a player with typical risk aversion and tax effects will need to have a pure expectation of$8,600 in the WSOP Main Event is a pretty valuable baseline that can guide decisions. This again illustrates how the large field size and high buyin of the WSOP Main Event effectively crowds out the average player form participating — unless that player is willing to pay a high effective cost.

But what if the player could reduce the size of the buyin for this event?

Next time, I look at the possibility of the player being able to sell off some of his action at 1-to-1 (i.e. no markup), which effectively reduces the buyin from $10,000 to something more manageable for less wealthy players. Indeed, doing this can change an unprofitable opportunity into a profitable opportunity for the risk-averse tournament player. For different levels of raw ROI, we will solve for optimal percentages of one's action to take in the idealized WSOP Main Event. This should be valuable information not only for prospective tournament players, but also those that might buy shares in them. Stay tuned. ## Saturday, May 7, 2011 ### To play or not to play: Optimal game selection with risky operators There are few certainties in the post-Black Friday online poker world. One fact that we are all still sure of is that nothing has changed with respect to the fact that playing online poker is legal on the federal level in the U.S. If an American player finds a poker site willing to take his business, and if he can manage to get his money to and from that site, he is not violating any federal law by doing so. So while the remaining U.S.-facing online poker sites are unlikely to be anywhere near as large, reputable, or financially liquid as what players are used to, as long as the risk of losing one's funds is small enough, there may still be some (severely-reduced) profit opportunities for American poker players, or, at the very least, a means of continuing to stay competitive at poker by practicing one's skills at one's leisure. The remaining U.S. sites should be expected to be different than PokerStars and Full Tilt Poker in at least a few incredibly important ways: • Since the subset of former American players which chooses to move to these sites will be highly skewed towards serious, professional players, all players should expect their winrates to drop significantly. • Deposits and withdrawals will be more costly and more unstable, and players should account for some nonzero probability of never receiving a cashout. • In the event of either voluntary or government-induced site closure, due to liquidity issues and the fact that these sites are less reputable, there is some probability that U.S. players would never get their account balances returned to them. Not too comforting. To be sure, even if playing on the remaining smaller sites is otherwise acceptable and a reasonable substitute for the experience of pre-Black Friday online poker (which will not be the case for all poker players), these issues are serious and will annihilate a lot of utility. These added risks cause players to have to make tradeoffs involving their profit potential and the amount of money they risk in their account balances at these sites. Putting it all together, how big are these costs? How bad do these risks have to be before it's not worth even trying to continue to play online? We can quantify this with a model which can estimate the effects of these risks on expected utility through Monte Carlo simulation. Model inputs We start by making assumptions about various aspects of the risks and costs of playing on these sites. Some of these are deterministic, and others will be uncertain. Once we have settled upon reasonable estimates of these values for all of these parameters, we can vary the most critical parameters to find break-even thresholds for expected utility, which can guide player decisions. • Fees associated with deposits and withdrawals — Deposits and withdrawals at smaller sites are costly, in both inconvenience and fees, so managing account balances carefully will be important to avoid incurring too many of these expenses. Our model will consider fixed fees for depositing or withdrawing, which we can expand to include intangible costs that reflect the inconveniences of these money transfers. • Deposit/withdrawal strategies — The simplest way to describe a rule that guides when to cash out or deposit is a set of four numbers. When the player's account balance is below some critical level (such as when it is too low to play his chosen stakes and number of tables), he should redeposit to bring his account balance up to some higher threshold level. Similarly, since he doesn't want to keep an unnecessary amount of money in a risky account, when his account balance hits some upper critical level, he should withdraw to bring his account balance down to some lower threshold level (which might be close to, if not exactly the same as, the threshold level for deposits). • Winrate, standard deviation, and play volume — The model will approximate poker results by increments of the appropriate normal distribution. To match the rest of the model, rather than looking at winrate and standard deviation per hand, we can look at these on a per-day basis by factoring in the amount of hands the player plans to play each day. The number of days remaining in the year will be one of the inputs. • Per-day probability of site closure — In our model, at the end of each day, we will assume that there is a fixed probability that the site will close forever. Each day will be independent of the last. • Probability of getting paid if the site closes — When the site closes, there is a chance that all player balances will be lost. • Probability of getting paid on each cashout — For each cashout prior to closure, there is a chance that the player will never see his money (or never be able to cash out in the first place). We can assume that this probability is less than that of the probability of getting paid when the site closes. • Tax and utility functions That's a lot of inputs, and a lot of inputs that we can't necessarily get great estimates of. Since the non-standard parts of this model are those pertaining to the risks of having money with the online site, we can ignore the lesser (or at least more standard) uncertainty on personal game performance parameters and instead assume that we know the player's exact winrate. Parameter choices We'll again work with our typical poker player:$80k net worth, $40k non-poker income,$10k year-to-date poker winnings, and isoelsatic utility with ρ=0.8, paying both federal and NJ income taxes. For simplicity, we'll assume that any money lost due to site-specific risks is treated the same as a poker loss and directly deductible against poker winnings, though I believe this is not exactly true.

UPDATE 06/18/2011: The above assumption may only be valid for those who file their taxes as professional poker players. Amateur poker players likely cannot deduct these losses at all in most cases, and this has serious implications for the model. See Update/correction to risky site model: Casualty losses and tax effects.

I'm not entirely familiar with costs of deposit and withdrawal at all of the remaining U.S.-facing poker sites, but for Carbon Poker, it looks like roughly $17 in costs to make a deposit, and about$5 per withdrawal for a medium-volume player.

We'll look at two possible levels of stakes for our player: multitabling $0.25/$0.50 NL at an hourly winrate of $10 with a standard deviation of about$70, or multitabling $0.50/$1.00 NL with an hourly winrate of $15 and a standard deviation of about$140. His $0.50/$1 winrate is higher in dollars, but lower relative to the stakes, which introduces not only the usual higher relative risk to his results, but also a need to keep a higher balance with the site. Keep in mind that he will have a much tougher time achieving these winrates on a remaining U.S.-facing website, since the player pools will be significantly tougher and it may not always be possible to play as many tables as he would normally be accustomed to. In the post-Black Friday market, I would expect winrates to be significantly lower than the good old days, and most players should probably drop down at least a level or two.

We assume that, for $0.25/$0.50 NL, he will redeposit when his balance falls below $800, and he will redeposit up to$1,200. He will withdraw down to $1,200 when his balance hits$2,000. For $0.50/$1 NL, we will double each of these deposit/withdrawal thresholds. Once we settle upon the other parameters, we can play with this to see which withdrawal strategy is optimal.

As a default, based on no science at all and simply my gut assessment of the risks of the current poker market, we'll assume that the per-day probability of site closure is 0.002 (i.e. the site lasts, on average, 500 days), that there is a 50% probability of players getting paid if the site closes, and a 75% probability of getting paid on any given cashout prior to closure.

We'll have him start playing in early May, so there's about N=240 days left in the year.

Algorithm

To calculate the expected utility of playing with these risks, these winrate parameters, and this utility function, we will simulate the system through the following steps:
1. Initialize the player's starting bankroll by him making his first deposit, tracking the costs of doing so in a running net total starting from his year-to-date winnings. This running net will NOT include his day-to-day poker results; money on the site is not counted as a gain or loss until it is successfully withdrawn.
2. At the start of each day, the player plays his daily poker session, and we adjust his site balance by a normal random variable with appropriate mean and variance. Since he can't lose more than he has on the site, we truncate this normal distribution on both tails by preventing the magnitude of the swing from exceeding his existing balance.
3. After his session, if his bankroll is below his deposit threshold, he deposits according to his strategy. We track both the deposit itself and the costs of doing so in the running net.
4. Then, if his bankroll is above his withdrawal threshold, he withdraws according to his strategy. He ends up receiving the cashout according to the chosen probability, which will be added to the running net, less the costs. If he gets unlucky and misses on the cashout, we assume it is lost forever.
5. At the end of each day, the site closes down according to the chosen per-day probability. If the site shuts down, the player's balance is returned to him according to the probability of getting paid if the site closes. Either way, if the site closes, we exit the loop and go directly to step 7, as there's no longer any poker to be played (we neglect the possibility of choosing another remaining site for the rest of the year).
6. Repeat steps 2-5 for each of the remaining N days.
7. At the end of the year, if the site is still open, for the purposes of evaluating his year-end utility, the player withdraws his balance (and receives it according to the chosen probability). This gives his final net winnings for the year, and we evaluate the after-tax utility of this amount.
8. Repeat steps 1-7 in a Monte Carlo simulation to simulate the average expected utility.

Some results

For the parameters we chose, we can look at how the results change as we perturb the most uncertain parameters, those related to site-specific risks.

First, if we disregard the assumption of getting paid 50% of the time if the site closes, and instead vary that, we can see what the effects of additional liquidity are and find the break-even liquidity level. Since this liquidity and the probability of successful cashouts are linked, it is desirable to adjust both at the same time, so as we vary the liquidity level, we will assume that the risk of losing a cashout is always half the risk of losing a bankroll in the event of closure.

The rightmost point is when the site is fully secure, which is what decision-makers have been roughly used to in the pre-Black Friday environment. In this case, the player prefers to play his more pure-EV-profitable stake of 100NL. As the site gets less and less secure, the need to keep a higher bankroll at the site for 100NL will create more and more risk, and 50NL becomes better when the site liquidity falls below about 38%. For less than 5% liquidity, the increase in the player's utility by playing either stake is negative, so the player should refrain from playing at all, unless the entertainment value or the value of being able to practice and work on his game is worth the cost.

If we return the liquidity probability to its original default rate of 50%, we can instead look at how expected utility varies with the per-day probability of site closure.

When changing the average lifetime of the poker site, we see that the effect is less linear. Again, the rightmost point corresponds to perfect safety, a site that has no risk of closing. As the probability of closing is increased (and we assume a 50% chance of not being able to get money back after closure), the expected utility drops off significantly. 50NL overtakes 100NL around a per-day closure probability of 0.004 (i.e. a mean lifetime of 250 days). Not playing at all becomes the best choice at a per-day closure probability of around 0.01 (i.e. a mean lifetime of 100 days).

If we return to the original, fixed best estimates of these parameters (50% liquidity, average site lifetime of 500 days), we can tweak the deposit and withdrawal strategies to see which one works best. We'll stick with just 50NL here, since it seems to be the better choice. We need to keep the lower deposit threshold at $800 in order for the player to have enough bankroll to be able to play a bunch of tables of 50NL during his sessions, but we can vary the other three account balance strategy parameters. We see that we can actually do better than the deposit and withdrawal strategy that we initially chose. It turns out to be better to wait to withdraw until at a higher balance, but still to deposit up to just$1,200. I suppose that this asymmetry comes about due to our utility function; we have a higher relative risk tolerance when we have earned more money on the year. We see that the "tightest" deposit and withdrawal thresholds do not do well here. This is all due to the interplay between the site-specific risks and the costs of moving money, and this behavior will probably change when any of these are modified.

Conclusions

If we compare the middle parts of each of the graphs to the rightmost points (which correspond to perfect safety), we can really see how much our utility suffers under these new risks. Players will need to have significant edges over their competition to overcome this.

In these results, the "shape" of the results is no surprise. We're not seeing anything we wouldn't have been able to guess without doing the math, but quantifying it provides a useful framework for guiding our play decisions under the uncertainty of the site-specific risks.

For our example player here, we see that, under the default assumptions with 50% liquidity and an average site lifetime of 500 days, playing 100NL will be a better risk-adjusted value than 50NL, though it's close enough that the player should move down if he feels the liquidity risk is greater, or that the sites have a significantly shorter expected lifetime. To dissuade him from playing entirely, there would have to be either a very low probability of getting paid back if the site closed, or withdrawals while the site is still operating would have to be less than 50% likely to go through. So, for this winning player, it looks like playing on a remaining U.S.-facing website should be better than quitting entirely as long as he has at least some faith in the current market. Many less skilled players with thinner winrates will be forced out of the market entirely from these additional risks.

This model is well-suited to being dynamically updated as the year goes on. The time horizon and year-to-date winnings will change constantly, which will shape bankroll decisions. Also, it should be useful to update the site-specific risks with better estimates as time goes on and as more information develops in the wake of Black Friday, or as the market positioning of the remaining U.S.-facing sites change.

While it's easy to see results by varying the site-specific parameters in this model when the player-specific variables (utility, income, winrate, etc.) are fixed, it's hard to draw broader conclusions over a more general player base. This is the sort of model that is best applied on a case-by-case basis, with each user's particular play variables fixed and known. If enough people are interested in using the spreadsheet I wrote for this, I might consider cleaning it up and hosting it somewhere.


text:
# Rotational Dynamics

1. Jan 12, 2013

### golanor

1. The problem statement, all variables and given/known data

A hollow cylinder of internal radius r and external radius R and mass M is connected by a string to a weight m.
What are the angular and linear acceleration of the cylinder? Assume that the cylinder is rolling without slipping.
What is the acceleration of the weight and what is the tension on the string?

2. Relevant equations
*everything*

3. The attempt at a solution
First, by using dimensional analysis i can see that the solution should be something along the lines of:
$$a=\frac{m*r}{M*R}g$$
I tried to do newton's second law, for the cylinder i get that:
$$\sum F=T=\text{Ma}$$
torque:
$$\sum \tau =T*R=\text{I\alpha }$$
moment of inertia around the center of mass:
$$I=M\left(R^2-r^2\right)$$
and the relation between the angular and linear acceleration:
$$\alpha =\frac{a}{r}$$

I have no idea what i did wrong or what do i need to do next.
1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution

#### Attached Files:

• ###### Untitled.jpg
File size:
5.9 KB
Views:
101
2. Jan 12, 2013

### haruspex

Because the cylinder is rolling, you need to be a bit careful about the moments. If you take moments about the centre of mass of the cylinder then you have to include the torque from friction at the point of contact. Alternatively, you can take moments about the point of contact and use the parallel axis theorem for the moment of inertia.
You've left friction out of the linear acceleration equation for the cylinder.
You also need a linear acceleration equation for the mass m.

Last edited: Jan 12, 2013
3. Jan 13, 2013

### golanor

$$\sum F=m*g-T=m*a$$

Shouldn't the friction be 0, since the cylinder is rolling without slipping?

4. Jan 13, 2013

### haruspex

Yes.
If the friction is zero it's sure to slip. 'Rolling' tells you that static friction is enough to prevent slipping.

5. Jan 13, 2013

### golanor

I understand..just got confused by something we proved in class.
So, the linear acceleration should be: $$\sum F=T-f=M*a_1$$
and the torque around the center of mass: $$\sum \tau =R(T+f)=\text{I\alpha }$$
Around the point of contact: $$\sum \tau =2R*T=\text{I\alpha }$$
And in this case, the moment of inertia will be $$I=M\left(R^2-r^2\right)+M\left(R^2\right)$$

6. Jan 13, 2013

### haruspex

A couple of problems with the first term on the RHS there. What would the MI be about the cylinder's centre if r were only a little less than R?

7. Jan 13, 2013

### golanor

Well, i forgot the 1/2 there. it's basically the MI of the large cylinder minus the one we took out. They are co-centric so there is no distance to add. if i look at extreme cases - r<<R it's as if the cylinder is complete, r=R - there is no mass. = the equation makes sense.
$$I=\frac{1}{2}M(2R^{2}-r^{2})$$ - this is relative to the contact point.
i know it's wrong tho, since when i put it into the equation i get $$r^{2}=0$$
the thing is, i don't know what i'm doing wrong.

8. Jan 13, 2013

### MrWarlock616

How do you know the mass of the cylinder you took out is the equal to the mass of the original cylinder?

9. Jan 13, 2013

### golanor

They have the same density.
$$I=\rho \left(\int _0^h\int _0^{2\pi }\int _0^Rr^3drd\phi dz+\int _0^h\int _0^{2\pi }\int _0^rr^3drd\phi dz\right)=\frac{M}{\pi *h\left(R^2-r^2\right)}h*\frac{\pi }{2}\left(R^4-r^4\right)=\frac{M}{2}\left(R^2+r^2\right)$$

10. Jan 13, 2013

### haruspex

That's better. (And of course +MR2 for parallel axis.)

11. Jan 14, 2013

### golanor

The point I missed was the relation between the cylinder's acceleration and the weight's acceleration.


text:
# If $(\mathcal D(A),A)$ is a linear operator on a Hilbert space and $\alpha\ge0$, then $\mathcal D(A^{-\alpha})=\mathcal D(A^{\alpha})'$

Let

• $H$ be a $\mathbb R$-Hilbert space
• $(\mathcal D(A),A)$ be a densely-defined, linear, positive definite and symmetric operator on $H$
• $(e_n)_{n\in\mathbb N}\subseteq\mathcal D(A)$ be an orthonormal basis of $H$ with $$Ae_n=\lambda_ne_n\tag1$$ for some $(\lambda_n)_{n\in\mathbb N}\subseteq(0,\infty)$ with $$\lambda_n\le\lambda_{n+1}\;\;\;\text{for all }n\in\mathbb N\tag2$$

Moreover, let $$\mathcal D(A^\alpha):=\left\{x\in H:\sum_{n\in\mathbb N}\lambda_n^{2\alpha}\langle x,e_n\rangle_H^2<\infty\right\}$$ and $$A^\alpha x:=\sum_{n\in\mathbb N}\lambda_n^\alpha\langle x,e_n\rangle_He_n\;\;\;\text{for }x\in\mathcal D(A^\alpha)$$ for $\alpha\in\mathbb R$.

Now, let $\alpha\ge0$. I've read that $\mathcal D(A^{-\alpha})$ can be "identified" with the topological dual space $\mathcal D(A^\alpha)'$ of $\mathcal D(A^\alpha)$. How is this identification been done?

Note that $\mathcal D(A^\alpha)$ equipped with $$\langle x,y\rangle_\alpha:=\langle A^\alpha x,A^\alpha y\rangle_H\;\;\;\text{for }x,y\in\mathcal D(A^\alpha)$$ is a $\mathbb R$-Hilbert space and hence $\mathcal D(A^\alpha)'\cong\mathcal D(A^\alpha)$ in the sense of Riesz' representation theorem.

Moreover, $$\langle x,y\rangle_H=\langle A^\alpha x,A^{-\alpha}y\rangle_H\;\;\;\text{for all }x\in\mathcal D(A^\alpha)\text{ and }y\in H\subseteq\mathcal D(A^{-\alpha})\tag3\;.$$

You basically have everything. We just need to extend $(3)$ to all of $\mathcal{D}(A^{\alpha}) \times \mathcal{D}(A^{-\alpha})$.

We endow $\mathcal{D}(A^{\alpha})$ with the inner product $\langle\,\cdot\,,\,\cdot\,\rangle_{\alpha}$ and obtain a Hilbert space that is in an obvious way isometrically isomorphic to the weighted sequence space

$$\ell^2((\lambda_n^{2\alpha}),\mathbb{N}) = \Biggl\{ x \in \mathbb{R}^{\mathbb{N}} : \sum_{n\in\mathbb{N}} \lambda_n^{2\alpha}\lvert x_n\rvert^2 < +\infty\Biggr\}.$$

We can also consider the weighted sequence space

$$\ell^2((\lambda_n^{-2\alpha}),\mathbb{N}) = \Biggl\{ y \in \mathbb{R}^{\mathbb{N}} : \sum_{n\in\mathbb{N}} \lambda_n^{-2\alpha}\lvert y_n\rvert^2 < +\infty\Biggr\}.$$

We have a natural bilinear pairing

$$\langle\,\cdot\,,\,\cdot\,\rangle_{\alpha,-\alpha} \colon \ell^2((\lambda_n^{2\alpha}),\mathbb{N}) \times \ell^2((\lambda_n^{-2\alpha}),\mathbb{N}) \to \mathbb{R};\quad \langle x,y\rangle_{\alpha,-\alpha} = \sum_{n\in \mathbb{N}} x_n y_n.$$

One verifies easily that this bilinear pairing gives isometric isomorphisms $$\ell^2((\lambda_n^{-2\alpha}),\mathbb{N}) \to \ell^2((\lambda_n^{2\alpha}),\mathbb{N})'$$ and $$\ell^2((\lambda_n^{2\alpha}),\mathbb{N}) \to \ell^2((\lambda_n^{-2\alpha}),\mathbb{N})'.$$

On the other hand, we can identify $\mathcal{D}(A^{-\alpha})$ with $\ell^2((\lambda_n^{-2\alpha}),\mathbb{N})$, since we can write

$$\mathcal{D}(A^{-\alpha}) = \Biggl\{ \sum_{n\in\mathbb{N}} y_n e_n : y \in \ell^2((\lambda_n^{-2\alpha}),\mathbb{N})\Biggr\}.$$

Note: the sum is formed in $\mathcal{D}(A^{-\alpha})$, where $\lVert e_n\rVert = \lambda_n^{-\alpha}$, not in $H$, where $\lVert e_n\rVert_H = 1$.

The situation is analogous to the case of Sobolev spaces. We have $H^{-s} = (H^s)'$ by definition for $s > 0$, and the chain of inclusions (where each inclusion is not only strict as an inclusion of sets, also the topology on each space is strictly finer than the subspace topology induced by a larger space in the chain)

$$H^t \subsetneq H^s \subsetneq H^0 = L^2 \subsetneq H^{-s} \subsetneq H^{-t}$$

for $0 < s < t$, but as Hilbert spaces, all the $H^r$ are of course also isometrically isomorphic to their duals. Here, we have for $0 < \alpha < \beta$ the chain of inclusions

$$\mathcal{D}(A^{\beta}) \subset \mathcal{D}(A^{\alpha}) \subset \mathcal{D}(A^0) = H \subset \mathcal{D}(A^{-\alpha}) \subset \mathcal{D}(A^{-\beta}),$$

and if $\lambda_n \to +\infty$, all inclusions are strict and the topology on each space is strictly finer than the subspace topology induced by a larger space in the chain. And like for the Sobolev spaces, we have $\mathcal{D}(A^{-\alpha}) \cong \mathcal{D}(A^{\alpha})'$ by one natural bilinear pairing, and $\mathcal{D}(A^{\alpha}) \cong \mathcal{D}(A^{\alpha})'$ by the Riesz map.

• By the principle of "make the domain as large as possible", if $\lambda_n \to +\infty$, we must go beyond $H$ for the domain of $A^{-\alpha}$ when $\alpha > 0$. If we don't, then the assertion is wrong and we can't (naturally) identify $\mathcal{D}(A^{-\alpha})$ with $\mathcal{D}(A^{\alpha})'$, since $H$ isn't complete with respect to the $A^{-\alpha}$-norm. – Daniel Fischer Jan 13 '17 at 14:04
• Consider the sequence space $$U_0 = \Biggl\{ x\in \mathbb{R}^{\mathbb{N}} : \sum_{n\in \mathbb{N}} \lambda_n^{2\alpha} \lvert x_n\rvert^2 < +\infty\Biggr\},$$ endowed with the inner product $$\langle x, y\rangle_{U_0} = \sum_{n\in\mathbb{N}} \lambda_n^{2\alpha} x_n y_n.$$ This is a Hilbert space, and $x \mapsto (\mu^n)_{n\in\mathbb{N}}$ is an isometric embedding $(H,\langle\cdot,\cdot\rangle_{\alpha}) \to U_0$. The image of that embedding is dense, so $U_0$ is a completion. Now if $U \supset H$ is a completion of $(H,\langle\cdot,\cdot\rangle_{\alpha})$, then – Daniel Fischer Jan 15 '17 at 21:29
• (a) The isometry is linear, but that's not important for the reassociation. At that point we're working with elements of $U$, which is assumed to be a completion of $H$ (for the $\alpha$ norm) that contains $H$, so $e_n \in U$ for all $n$. And since $\xi_n$ and $\lambda_n^{-\alpha}$ are real numbers, we have $\xi_n(\lambda_n^{-\alpha} e_n) = (\xi_n\lambda_n^{-\alpha})e_n$ just from the vector space axioms. – Daniel Fischer Jan 16 '17 at 21:56
• Sorry, I'll have to think about how to explain that, will take a while. But as for why we can always have a completion such that the isometry is the inclusion: Let $j \colon X \hookrightarrow Y$ be an isometric embedding with dense image, where $Y$ is a Banach space. Let $T$ be a set with $T\cap X = \varnothing$ that has the same cardinality as $Y\setminus j(X)$, and $t\colon T \to Y\setminus j(X)$ a bijection. Let $Z = X \cup T$, and $h\colon Z \to Y$ the bijection such that $h(z)= j(z)$ if $z\in X$ and $h(z) = t(z)$ if $z\in T$. Transport the Banach space structure from $Y$ to $Z$ using $h$, – Daniel Fischer Jan 17 '17 at 20:05
• The existence of such a $T$ is guaranteed by the axioms of set theory. At least if one uses a sensible set theory. The standard is $\mathsf{ZFC}$. The cardinality of a set $S$ (in $\mathsf{ZFC}$; things get weird without choice) is the smallest ordinal $\kappa$ such that there is a bijection $\kappa \to S$. – Daniel Fischer Jan 17 '17 at 21:32