User matus telgarsky - MathOverflow

Answer by Matus Telgarsky for How to compute KL-divergence when PMF contains 0s?

2011-08-11T10:48:15Z

I'll give a short answer and a long answer.

The short answer is that the KL divergence on multinomials is defined when they have only nonzero entries. When there are zero entries, you have two choices. (1) Smooth the distributions in some way, for instance with a Bayesian prior, or (similarly) taking the convex combination of the observation with some valid (nonzero) distribution. (The standard Bayesian approach is to use a Dirichlet prior, which amounts to treating each entry as a fraction $n_i / m$ where $m=\sum_i n_i$, and $n_i$ should be integer (but with your provided data this may get messy), and replacing these fractions with for instance $(n_i + 1) / (m+|x|)$ where $|x|$ is the number of atoms in the discrete distribution; the "convex combination" smoothing choice is similar, if $x$ is your observation and $\alpha \in (0,1]$, return $\alpha U_{|x|} + (1-\alpha)x$ where $U_{|X|}$ is the uniform distribution on $|x|$ points.) (2) Employ heuristics throwing out all the values that do not make sense, as suggested above. While I acknowledge that (2) is a convention, it doesn't really fit with the nature of these distributions, as I will explain momentarily.

The longer answer is the mathematical reason why KL divergence can't handle these zeros, which requires information about Exponential family distributions (multinomial, gaussian, etc). Every exponential family distribution is defined relative to some base measure, and it must be nonzero everywhere on that base measure: this is true with multinomials, it is true with gaussians (covariance matrix must be full rank), etc. This arises because these distributions are the solution to an optimization problem which breaks down in the presence of those zeros. Anyway, so what needs to happen is that the relative base measure is the "tightest possible": in the case of multinomials, it is the uniform distribution on the nonzero entries, and in the Gaussian case, it is Lebesgue measure restricted to the affine subspace corresponding to the eigenspace of the provided covariance, shifted by the provided mean. The KL divergence (written as an integral) only makes sense if both distributions are relative to the same "tightest fit" measure.

To summarize, the invalidity of the formula in the presence of zeros isn't just some unfortunate hack, it is a deep issue intimately tied to how these distributions behave. The smoothing/Bayesian solution is thus better motivated: it nudges the distributions into validity. But many people simply choose to throw out those values (i.e., by erasing $0\ln(0)$ or $a\ln(a/0)$ and writing $0$ in its place).

Answer by Matus Telgarsky for Conic hulls and cones

2011-07-12T09:02:10Z

Question 1.

Usually, finding the convex hull means finding the vertices on each face of the convex hull; in this case, there are algorithms with running time $\mathcal O(n^{d/2})$ (where $n$ is the number of points, each in $\mathbb{R}^d$), and polytopes providing a lower bound (some of this is in the qhull material mentioned in the comments; I also found it in matousek's book "lectures on discrete geometry", specifically in the bibliographic remarks of section 5.5).

For your scenario of just finding the list of vertices, It seems like you can take $d$ out of the exponent. I'm not finding references on this which makes me a little nervous, but I'll give the algorithm in a second and you can decide how you feel about it.

Question 2.

I'm not sure what you mean because your example of the PSD cone is not polyhedral; that is, it is not an intersection of finitely many halfspaces, equivalently (by what is sometimes called the Minkowski-Weyl theorem) there does not exist a finite set of points generating it. If your $C$ were finitely generated, then I'd say run the conic hull algorithm for the union of both point sets, but I'm hoping you'll comment to clarify..

Algorithm.

The algorithm is greedy. It starts with all points in the conic hull, and greedily removes points that can be represented as conic combinations of other points. Thus it attempts to remove points $n$ times, and each iteration must try to rewrite each of the $ < n$ points using the others; it terminates when passing over the remaining vertices finds no rewrites, meaning there are $\mathcal O(n^2)$ total iterations.

Each iteration solves a linear program of the following form. The goal is to rewrite some vertex $b$ using the other remaining vertices, collected as columns into the matrix $A$ (let $|A|$ denote the number of columns). This is a linear feasibility problem $$ \textrm{find } x \in \mathbb{R}^{|A|} \textrm{ such that } Ax = b, x \geq 0. $$ A standard linear programming solver can do this in time $\mathcal O(m^{3.5} \ln(1/\epsilon))$ (where $m:=\max\{n,d\}$), where $\epsilon > 0$ will depend on how close some points are to being vertices of the cone. These algorithms will either find a satisfactory $x$, or will terminate with a dual certificate. Actually the duality is strong here; by Farkas's lemma you either can write a point in the desired way (it is in the cone), or you can separate it from the cone by a hyperplane.

To see that this algorithm is correct. First note that it never terminates when there are points that are conic combinations of others. Next note that it never removes a vertex of the conic hull, because these points can not be written as conic combinations of the other points.

Answer by Matus Telgarsky for Existence of nonnegative solutions to an underdetermined system of linear equations

2011-04-06T10:55:48Z

This scenario is explicitly handled by Gordan's theorem, which states $$ \text{either} \quad \exists x \in \mathbb{R}_+^m\setminus\{0\} \centerdot Ax = 0, \quad\text{or}\quad \exists y\in\mathbb{R}^n\centerdot A^\top y > 0, $$

where $\mathbb{R}_+$ denotes nonnegative reals. (Like Farkas's Lemma, this is a "Theorem of Alternatives"; furthermore, it can be proved from Farkas's lemma.)

A nice way to prove this is, as in Theorem 2.2.6 of Borwein & Lewis's text "Convex Analysis and Nonlinear Optimization", to consider the related optimization problem $$ \inf_y \quad\underbrace{\ln\left(\sum_{i=1}^m \exp(y^\top A \textbf e_i)\right)}_{f(y)}; $$ as stated in that theorem, $f(y)$ is unbounded below iff there exists $y$ so that $A^\top y > 0$. As such, this also gives an unconstrained optimization problem you can plug into your favorite solver to determine which of the two scenarios you are in. Alternatively, you can explicitly solve for either the primal variables $x$ or the dual variables $y$ by considering a similar max entropy problem (i.e. $\inf_y\sum_i \exp(y^\top A\textbf{e}_i)$, which approaches 0 iff the desired $y$ exists) or its dual (you can find this in the above book, as well as papers by the same authors).

Anyway, considering Gordan's theorem, your condition on the columns (which can be written $\textbf{1}^\top A = 0$) has no relationship to the question at hand. In one of your comments you mentioned wanting to generate these matrices. To pick positive examples, fix a satisfying $x$, and construct rows $b_i'$ by first getting some $b_i$ and setting $b_i' := b_i - (x^\top b_i)x / (x^\top x)$; to pick negative examples, by Gordan's theorem, choose some nonzero $y$, and then consider adding to $A$ a column $a_i$, including it if it satisfies $a_i^\top y > 0$.

Answer by Matus Telgarsky for Why were matrix determinants once such a big deal?

2010-08-19T03:00:39Z

I think the multivariate change-of-variable formula in integration (i.e. involving the determinant of the Jacobian) is still rather indispensable. The treatment I'm most familiar with is in Folland, where, as far as I recall, it is only used to construct integration in polar coordinates (and I think there was only one exercise, concerning a further extension).

One could perhaps say that the trick of computing the normalization to a Gaussian random variable, by way of passing through polar coordinates, uses determinants. EDIT: this fact also provides an immediate explanation for the presence of the determinant in the denominator of a multivariate Gaussian (and by positive semi-definiteness of the covariance, that the square root makes sense).

Answer by Matus Telgarsky for Is quadratic programming still NP-hard if you have bounds and a feasible point?

2010-07-23T05:29:43Z

No; I think what you're observing is a side effect of reducing from deicision problems; if you tried to encode an NP optimization problem, you'd end up using more than just the feasibility machinery.

Take MAX-CUT, with variables $x_i\in\{-1,+1\}$ indicating taking a vertex or not, and $W\in\mathbb{R}^{n\times n}$ a matrix of edge weights. Since cut capacity can be written as $\frac 1 2\sum_{i<j} W_{ij}(1-x_ix_j)$ , the optimization problem has form $$ \min\ x^TWx \quad\quad \textrm{subject to} \quad \forall i\centerdot x_i^2 = 1. $$ Even the real-valued relaxation $x_i\in [-1,+1]$ is problematic since $W$ is in general indefinite. Like I said above, since we're trying to solve an NP optimization problem, we are definitely relying on the optimization machinery.

As a final point, I'm not sure why you brought duality into the picture, since the usual guarantees of strong duality are murky once nonconvexity enters the picture ....

Answer by Matus Telgarsky for Are Bregman divergences quasi-convex?

2010-03-17T12:45:28Z

The answer is: yes, it is always quasi-convex! I'll show this by first proving a stronger characterization, from which the other facts follow. Please bear with me as I first make a few definitions.

Let convex $S \subseteq \mathbb{R}$ and a function $f:S\to \mathbb{R}$ be given. To avoid existence of derivatives, let $f'(v)$ refer to any subgradient of $f$ at $v$, and say $f$ is convex if for any $x,v \in S$, $f(x) \geq f(v) + f'(v)(x-v)$. (This is an equivalent formulation of convexity, and when $f$ is differentiable, gives the 'first-order' definition of convexity.) Note critically that for $u,v\in S$ with $u\leq v$, it follow that $f'(u) \leq f'(v)$. (This is sort of like the mean value theorem, though not exactly since those subgradients are technically sets; I think all of I've said so far may appear in the thesis of Shai Shalev-Shwartz.) Define $$b_x(v) = f(x) - f(v) - f'(v)(x-v)$$ to be the Bregman divergence of $f$ at the point $x$, taking the linear approximation at $v$. By the definition of convexity, if follows that $b_x(v) \geq 0$ for all $x,v\in S$.

Fact: $b_x(\cdot)$ is decreasing up to $x$, exactly zero at $x$, and increasing after $x$.

Proof. $b_x(x) = f(x)-f(x) - f'(x)(0) = 0$. Now consider $u\leq v \leq x$; we'd like to show $b_x(u) \geq b_x(v)$. To start, write $$ b_x(u)-b_x(v) = f(v) + f'(v)(x-v) - f(u) - f'(u)(x-u). $$ Now, using $f(v) \geq f(u) + f'(u)(v-u)$ yields $$ b_x(u)-b_x(v) \geq f'(v)(x-v) + f'(u)(v-x) = (f'(v) - f'(u))(x-v), $$ and $b_x(u)-b_x(v)\geq 0$ follows since $f'(v) \geq f'(u)$ and $x-v\geq 0$. To show the last case, that $x\leq v\leq u$ gives $b_x(u) \geq b_x(v)$, the proof is analogous. QED.

Some remarks:

To see that this means $b_x(\cdot)$ is quasi-convex, take any $y\leq z$ and any $\lambda \in [0,1]$. Then the point $w:=\lambda y + (1-\lambda)z$ lies on the line segment $yz$, and $b_x(\cdot)$ must be increasing in the direction of at least one of these endpoints.
This also gives a strong idea of how convexity breaks down for $b_x(\cdot)$. In particular, let $f= \max\{0, |x|-1\}$ (a 1-insensitive loss for regression). Then the function $b_0(\cdot)$ is 0 on $(-1,1)$ and 1 everywhere else except $\{-1,+1\}$ (those points are different since, by using subgradients, these functions have sets as output; but if you took a differentiable analog to this loss, something like a Huber loss, you'd get basically the same effect, and $b_0(\cdot)$ is a vanilla continuous (non-convex) function).

Answer by Matus Telgarsky for Counting trailing zeros for factorials

2010-02-24T12:12:02Z

Take any integer $x$, and let $t,f$ represent the highest integers such that $2^t | x$ and $5^f | x$. Then the number of trailing zeros in the base 10 representation of $x$ is $z := \min\{t,f\}$. (One way to see this is to note it must be at least z since you have $(2*5)^z | x$, so you can write $x = 10^z * y$ where not both $2,5|y$, and so $y$ can't have any trailing zeros.)

Going back to factorials, $n!$ will always have $t > f$, so to count the zeros, you just have to count the fives. The expression you want is $$ f = \sum_{i=1}^\infty \lfloor n / 5^i\rfloor. $$ But maybe there's a cleaner form.

(for 1990! this gives 495, not 494 as you said. I checked this numerically as well, I guess you have a bug.)

Answer by Matus Telgarsky for unbiased estimate of the variance of a weighted mean

2010-01-15T15:25:35Z

First some notation. Each example is drawn from some unknown distribution $Y$ with $E[Y] = \mu$ and $\textrm{Var}[Y] = \sigma^2$. Suppose the weighted mean consists of $n$ independent draws $X_i\sim Y$, and $\{w_i\}_1^n$ is in the standard simplex. Finally define the r.v. $X = \sum_i w_i X_i$. Note that $E[X] = \sum_i w_i E[X_i] = \mu$ and $\textrm{Var}[X] = \sum_i w_i^2 \textrm{Var} [X_i] = \sigma^2\sum_i w_i^2$.

Generalizing the standard definition of sample mean, take $$ \hat \mu(\{x_i\}_1^n) := \sum_i w_i x_i. $$ Note that $E[\hat \mu(\{x_i\}_1^n)] = \sum_i w_i E[x_i] = \mu = E[X]$, so $\hat \mu$ is an unbiased estimator.

For the sample variance, generalize the sample variance as $$ \hat \sigma^2_b(\{x_i\}_1^n) := \sum_i w_i (x_i - \hat \mu({x_i}_1^n))^2, $$ where the subscript foreshadows this will need a correction to be unbiased. Anyway, $$ E[\hat \sigma^2_b] = \sum_i w_i E[(x_i - \hat \mu)^2] = \sum_i w_i E\left[\left(\sum_j w_j (x_i - x_j)\right)^2\right]. $$ The term in the expectation can be written as $$ \sum_{j,k} w_j(x_i - x_j)w_k(x_i - x_k) = \sum_jw_j^2(x_i - x_j)^2 + \sum_{j\neq k} w_j w_k(x_i - x_j)(x_i - x_k). $$ Passing in the expectation, the first term (when $x_i\neq x_j$, which would yield 0) is $$ E[(x_i-x_j)^2] = 2E[x_i^2] - 2\mu^2 = 2\sigma^2, $$ whereas the second (when $x_i \neq x_j$ and $x_i \neq x_k$, which would yield 0) is $$ E[x_i^2 - x_ix_j - x_ix_k + x_jx_k] = E[x_i^2] - \mu^2 = \sigma^2. $$ Combining everything, $$ \sum_i w_i \left(2\sigma^2\sum_{j\neq i}w_j^2 + \sigma^2\sum_{j\neq k\neq i} w_j w_k\right) = \sigma^2( 1 - \sum_j w_j^2). $$ Therefore $E[\hat \sigma_b^2] - \sigma^2 = -\sigma^22\sum_j w_j^2$, i.e. this is a biased estimator. To make this an unbiased estimator of $Y$, divide by the excess term derived above: $$ \hat \sigma_u^2(\{x_i\}_1^n) := \frac {\hat \sigma_b^2(\{x_i\}_1^n)}{1- \sum_j w_j^2} = \frac {\sum_i w_i(x_i - \hat \mu)^2}{1- \sum_j w_j^2 } $$ This matches the definition you gave (and a sanity check $w_i = 1/N$, recovering the normal unbiased estimate).

Now, if one instead were to seek an unbiased estimator of $X=\sum_i X_i$, the formula would instead be $\hat \sigma_b^2(\{x_i\}_1^n)(\sum_j w_j^2) / ( 1 - \sum_j w_j^2)$.

It is very odd for me that the documents you refer to are making estimators of $Y$ and not $X$; I don't see the justification of such an estimator. Also it is not clearly how to extend it to samples that don't have length $n$, whereas for the estimator of $X$, you simply have some number $m$ of $n$-samples, and averaging everything above makes things work out. Also, I didn't check, but it's my suspicion that the weighted estimator for $Y$ has higher variance than the usual one; as such, why use this weighted estimator at all? Building an estimator for $X$ would seem to have been the intent..

Answer by Matus Telgarsky for limsup and liminf for a sequence of sets

2010-01-21T02:27:07Z

As Johannes stated, the Borel-Cantelli lemmas (there are two) are the primary way in which these quantities (referred to as "infinitely often" and "almost always") appear.

The most common use is to prove things about limits of random variables. To see why this is the case, suppose you can show that, for any $\epsilon > 0$, $$ P([|X_n| > \epsilon]\textrm{ i.o.}) = 0. $$ (To show this with the first Borel-Cantelli lemma, you would establish $\sum_n P([|X_n| > \epsilon]) < \infty$.) From here, it follows that $P([\lim X_n = 0]) = 1$, because $$ P([\lim X_n = 0]) = P(\cap_i \cup_N \cap_{n\geq N} [|X_n| > 1/i]) =: P(A) $$ by definition of limit, but $$ P(A^c) =1-P(\cup_i \cap_N \cup_{n\geq N} [|X_n| \leq 1/i]) \geq 1- \sum_i P([|X_n| > \epsilon]\textrm{ i.o.}) = 1, $$ where the union bound (subadditivity) and definition of infinitely often were employed. Note that i worked out a bunch of symbols to make sure the math was correct, but you can see it in words: if, for every $\epsilon >0$, you have the property that probability of infinitely many of your random variables exceeding $\epsilon$ is zero, then it is intuitive that the limit of this sequence is 0 with probability 1.

To get a feel for more details (and the relationship to specific probabilistic quantities), maybe try using this technique to prove certain limiting properties of certain sequences of random variables (any probability textbook will have many, for instance the excellent book by Resnick).

I'll also add that you can prove a weakened form of the SLLN (weakened means you need some extra assumptions on which moments are finite) using Chebyshev's inequality and the limiting technique above. As you can guess, Chebyshev allows you to say something of the form $\sum_n P([|X_n| > \epsilon) < \infty$, where $X_n$ is something fancier as needed for the SLLN (a normalized sum).

Answer by Matus Telgarsky for Heuristically false conjectures

2010-01-16T11:59:26Z

CS theory has a slew of these examples. In particular, take any problem which is known to be in $RP$, but its membership in $P$ is (currently) unknown.

Example: is it possible, using walks consisting of polynomially many steps, to estimate the volume of a convex body?

In the terminology of your question, the answer is 'yes' if you say that random steps are a reasonable model of the steps made by a smart algorithm. On the other hand, a deterministic method of choosing the steps is unknown.

(PS the reference on this particular problem is "A random polynomial-time algorithm for approximating the volume of convex bodies" by Dyer, Frieze, Kannan.)

Answer by Matus Telgarsky for Building a multi-variable regression model

2010-01-16T14:22:37Z

The input dimension being 18 is a little problematic, so I have a few suggestions. I'm putting the statistical approach first due to your choice of tags and terminology..

Linear regression can be made to fit polynomials by simply explicitly creating all the monomial terms; ie for an input with two dimensions $x= (x_1,x_2)$, for a quadratic you'd instead use $x' = (1,x_1,x_2,x_1x_2,x_1^2,x_2^2)$. Notice that this means, to add all $d$th order terms, you would create $O(18^d)$ dimensions! Notice furthermore that your regression model has equivalently many parameters! Therefore, it may be beneficial to try to simplify the model a little with some regularization, maybe use lasso (l1-regularization). Note that, as specified, the degree of the polynomial is not being minimized. The regularization I mentioned only minimizes the l1 length, and even putting a sparsity constraint on the weights alone (which is simpler than minimizing degree) is nonconvex. To find the degree, you could binary search; ie try degrees $1,2,4,8,\ldots$ until you get zero error, and then binary search within the last interval to find the exact order.

Another approach is to directly use polynomial interpolation. Simply grow $d$, building an interpolating polynomial at each iteration, and stopping when the one built on the provided points fits all other points. For univariate data, the Lagrange Polynomial[1] is the way to go. I don't know your case offhand but just noticed wikipedia has a "polynomial interpolation" page which should be helpful.

anything you try will be slow due to the dimension, your stipulation that you necessarily find the absolute smallest degree, and the vast number of parameters in any such polynomial.

[1] lagrange interpolation

Answer by Matus Telgarsky for Entropy of Random Signal

2010-01-08T10:12:37Z

Ok first, the entropy you're talking about is the differential entropy $-\int f(x) \ln f(x) d\mu(x)$. The problem is that $\mu$ is Lebesgue measure. The set of continuous probability distributions is the set of distributions that have a density (i.e. radon-nikodym derivative) wrt Lebesgue measure. As such, if your distribution does NOT have such a density, then there isn't really a meaningful interpretation of the above quantity. Not only that, if your distribution had a density $f$ wrt to some other measure $\nu$, and you plugged $f$ into the above, you'd accidentally be computing the differential entropy of some completely different distribution $f d\mu$, which is a continuous distribution.

So to answer the question: if you want to deal with non-continuous distributions, you have to tweak your definition of differential entropy. if the only difference you make is to substitute in some well-behaved measure $\nu$, even if the derivation goes through the same, the distribution you get out will be wrt $\nu$, ie not the same as $\phi d\mu$ where $\phi$ is the density of the gaussian. (how much of that derivation you can re-use depends on the measure you choose.)

PS a good reference on this stuff is cover&thomas's information theory book, which has a derivation of gaussian being the max (differential) entropy (continuous) distribution with constant variance.

EDIT I misunderstood the question; I thought it was asking about entropy for distributions without a density wrt Lebesgue; all it is asking for is a proof without any conditions on the density. Deane Yang provides such a proof in his answer to the question.

Answer by Matus Telgarsky for Get rid of tr() in SVM kernel trick

2010-01-14T09:28:35Z

If $A,B$ are arbitrary $n\times n$ matrices, by definition of trace, $\textrm{tr}(AB) = \sum_{i,j} A_{ij}B_{ji}$. This is $O(n^2)$, but just reading the entries of $A$ is $\Omega(n^2)$. Without any special structure on $A,B$, you probably can't do better.

If $A,B$ are (column) vectors, you probably mean the outer product $\textrm{tr}(AB^T) = \sum_i A_i B_i$.

Edit: andinos clarified to say he wants to know about the implicit mapping of the kernel function. Well I have bad news: It does not exist!! The proof works by showing there exist matrices $A,B$ such that the corresponding kernel matrix is not positive semi-definite. To finish, apply Mercer's theorem.

In particular, set $A = \left(\begin{array}{cc}1 & 1 \\ -1 & 1\end{array}\right)$ and $B = A^T = \left(\begin{array}{cc}1 & -1 \\ 1 & 1\end{array}\right)$. Therefore $\textrm{tr}(AB) = \textrm{tr}(AA^T) = 4$, and $\textrm{tr}(BA)$ is identical. On the other hand, $\textrm{tr}(AA) = \textrm{tr}(BB) = 0$. therefore, the kernel matrix $K$ is $\left(\begin{array}{cc}0 & 4 \\ 4 & 0\end{array}\right)$. Set $x = \left(\begin{array}{c} 1 \\ -1\end{array}\right)$, and observe that $x^T K x = -8 < 0$, and therefore $K$ is not PSD, so the kernel $k(A,B) = \textrm{tr}(AB)$ is not PSD.

On the other hand! If you had instead defined your kernel to be $k'(A,B) = \textrm{tr}(AB^T)$, notice that $k'(A,B) = \sum_{i,j}A_{ij}B_{ij} = \Phi(A)^T\Phi(B)$ where $\Phi$ simply takes its input matrix and outputs it as a column vector.

Answer by Matus Telgarsky for What is the first interesting theorem in (insert subject here)?

2010-01-14T16:30:38Z

Measure theory: the Hahn decomposition theorem.

If one were to attempt to simply union together all positive sets, one may end up with an uncountable union, which is thus not necessarily measurable. The fact that you can decompose the space into a positive and negative set is therefore a little surprising. The constructions in the proof of this theorem are typically delicate.

Answer by Matus Telgarsky for What's the use of a complete measure?

2010-01-13T04:53:45Z

In light of the comments here, I'm going to show why completeness can be a pain. In exercise 9 of section 2.1 of Folland, he develops a function $g: [0,1] \to [0,2]$ by $g(x) = f(x) + x$ where $f : [0,1] \to [0,1]$ is the Cantor function. In that exercise it is established that $g$ is a (monotonic increasing) bijection, and that its inverse $h = g^{-1}$ is continuous from $[0,2]$ to $[0,1]$.

Since $h$ is continuous, it is Borel measurable. On the other hand, $h$ is not $(\mathcal{L}, \mathcal{L})$-measurable!! In particular, let $C$ be the Cantor set; $m(g(C)) = 1$, but this means there is a subset $A \subseteq g(C)$ which is not Lebesgue measurable. On the other hand $B := g^{-1}(A) \subseteq C$ whereas $m(C) = 0$; thus this preimage $B$ is Lebesgue measurable (with measure zero). But therefore $h^{-1}(B) = A$ is not Lebesgue measurable, meaning $h$ is not $(\mathcal{L}, \mathcal{L})$-measurable.

On one hand, this function is contrived. On the other hand, it shows that completing measures can mess things up. The typical definition of "measurable function" is a Borel measurable function, and I suppose reasons like the above led to this convention. I do not know the material Bridge references above, and so can't say what breaks when completeness is dropped. Although it seems mathematically convenient to throw in completeness, I don't know any examples in basic probability theory where it helps. For instance, Fubini-Tonelli can be formulated just fine without completeness. Your statement of the theorem only need mention completeness if your measures happen to be complete!

EDIT I corrected the nonsense in the second paragraph; also I meant to talk about $(\mathcal L, \mathcal L)$-measurable functions, which I accidentally refered to as Lebesgue measurable (which means $(\mathcal L, \mathcal B)$-measurable). My whole point is that if you take completion in $\sigma$-algebra of the range space, the extra sets you added could map back to basically anything. IE it is somewhat nonsensical to add in all sorts of null sets, but not all sorts of finite measure sets. Sometimes completion gives you something you want, but sometimes it does not, as I showed here--the function is better behaved wrt the non-completed measure.

Answer by Matus Telgarsky for What are the most attractive Turing undecidable problems in mathematics?

2010-01-13T14:05:02Z

Well if we're going to give easy ones, then: checking if two real numbers are equal. As if you needed more reasons to be disturbed by the reals!

A special case of: checking if a vector $v$ in a finite dimensional vector space over the reals is linearly independent of a set of vectors $\{u_i\}$.

(almost equivalently: checking equality (in the sense of extensionality) of $k\geq 2$ bounded integer-valued functions. the output of such functions can be written as real numbers in $[0,1]$, but you have to have to pad each integer so that you don't accidentally call two different outputs the same real number (due to $0.99\ldots = 1.00$ etc). How to solve the halting problem: have a function $f(n) = 1$. Given some arbitrary program/function, nest it in a function $g(n)$ which runs it for $n$ cycles, and outputs $1$ if it halted, $0$ otherwise. $f$ and $g$ are equivalent iff the program does not halt.)

Answer by Matus Telgarsky for Regression problem/detect outliers

2010-01-12T10:22:50Z

If you are committed to linear regression, there are two choices--regularization, and changing the loss function (linear regression usually means least squares, which (without regularization) can be solved conveniently with a line of matrix manipulation in matlab).

As far as regularization goes, the two techniques which get lots of attention are ridge regression (l2-regularization) and lasso (l1-regularization). These days, l1-regularization gets more attention due to connections to sparsity and also its use in compressed sensing.

If you don't have many variables, i.e. model complexity isn't the problem and you just have some outliers really messing with the hyperplane, you can use a more insensitive loss function, for instance absolute loss or huber loss (huber loss is similar to absolute loss in terms of sensitivity to outliers, but is also differentiable).

Answer by Matus Telgarsky for Why isn't Likelihood a Probability Density Function?

2010-01-08T09:44:02Z

A few questions were asked, so a few answers will be given. (main point: likelihood is not necessarily a product density, though this is the common interpretation.)

Frequently, the likelihood is the product of densities over some provided set of examples. The examples are drawn i.i.d., and therefore this product density is the density for the corresponding product measure over the product space. What I'm saying is that yes, from this perspective, you have constructed a product density.

Since you are dealing with densities, not probabilities, values are not constrained to [0,1], and your density can easily be greater than one. In fact, if you are dealing with dirac measure (which puts all mass on one point on the real line), you essentially have "infinite" density. I put that in quotes since this is not a continuous probability measure, ie it does not have a density wrt to Lebesgue measure, let alone one with infinite mass on a point. (A quick fact check: the corresponding integral wrt lebesgue measure would have value zero since it is off zero only on a set of lebesgue measure zero, which means it is not a probability distribution; but it was, which contradicts this being its density.) perhaps a more apt example: any (continuous) distribution on [0,0.5] will have to have density greater than one on a set of nonzero lebesgue measure. (you can try to construct a sequence of these which convergence to something which violates what i said, but that will be the density of something which is not continuous!)

things can get a little confusing because you can write discrete probability distributions as densities wrt a measure putting 1 on each point in the support set of the probability (ie it is counting measure wrt that set). NOTE that this is a density wrt a measure which is NOT a probability measure. But anyway, the density values at each point are exactly the probability values. This allows an interchanging probability masses and densities, which can be confusing.

I'll close with some further reading. A good book on machine learning is "A probabilistic Theory of Pattern Recognition" by Devroye, Gyorfi, Lugosi. Chapter 15 is on maximum likelihood and you'll notice they do NOT define likelihood as being a product probability or density, but rather as a product of functions. This is because they are careful to encompass the differing interpretations; rather, they ignore the interpretations there and work out the math.

Comment by Matus Telgarsky

2011-07-21T21:13:30Z

For the relevant material I know of, the natural measures are all countably additive. However I acknowledge that I may have misinterpreted Valerio's intent, and my answer is not helpful.

Comment by Matus Telgarsky

2011-07-13T09:42:37Z

BTW I believe there is a typo in your description: primal certificates mean no extreme point, and dual certificates mean some extreme point amongst the remaining input points.

Comment by Matus Telgarsky

2011-07-13T09:39:07Z

Welcome to MO! That is a very nice algorithm! Just a note--I can't figure out how to directly convert this to conic hulls, so it seems necessary to use a conic-to-convex reduction as remarked by Jean-Marc Schlenker in the comments above. (To be specific about the problem: it is possible that a non-extremal point has the largest projection onto the dual certificate, simply because it is "farthest down" that polyhedral face. I tried a couple quick fixes, but all failed. Anyway, the projection solution by Jean-Marc is fast and sufficient.)

Comment by Matus Telgarsky

2010-08-28T01:08:05Z

A related quantity is $\sup_{B\in \mathcal B} |int_B f - \int_B g| = \int|f-g|/2$; this is called Scheffe's identity ($\mathcal B$ is the $\sigma$-algebra over $\mathbb R$). I.e., by expanding what you consider in the $\sup$, you get $L^1$ distance on densities. as such, this quantity upper bounds yours, and provides a tighter estimate than what was posted in comments already, where it was verified it is a norm. Your norm is a little unusual; maybe $L^1$ is more useful to you.

Comment by Matus Telgarsky

2010-08-22T13:26:06Z

About using neighbors--although this seems like a reasonable idea, there is very little work in this direction. Luc Devroye has a few papers on this topic http://cg.scs.carleton.ca/~luc/devs.html , and you'll see that just looking at the closest is inadequate. In general, cross-validation is the standard technique. If you are interested in L1 density estimates, there is an excellent book by Devroye and Lugosi titled "Combinatorial Methods in Density Estimation".

Comment by Matus Telgarsky

2010-07-29T22:54:59Z

certain probability 'paradoxes' are completely defanged when put in the context of measure theory. Even if you disagree with the way this was done (i.e. the specific tenets if measure), it is nice to make systematic progress.. (as with russell's paradox and ZFC, even if you prefer other systems..)

Comment by Matus Telgarsky

2010-07-23T19:20:18Z

thanks eric! my punishment for staying up all night..

Comment by Matus Telgarsky

2010-03-18T09:42:37Z

(and set $x= (0,0)$.) in the bad example, since $f$ is linear along $x-y$ and $x-z$, then $b_x(y) = b_x(z) = 0$. On the other hand, since it is quadratic along $x-w$, the Bregman divergence is nonzero; in fact, it is $1/2$. I have an argument that $f$ is convex, but it is vague. I have to run, but tomorrow hopefully I can come back with something better.

Comment by Matus Telgarsky

2010-03-18T09:39:54Z

thanks for clarifying. If you can verify the following example (in cylindrical coordinates) is convex, then the general case does not work. Set $\lambda(\theta) = \frac {4}{\pi}\left | \theta - \frac \pi 4\right|$, $S= [0,1] \times [0,\pi/2]$, and $f : S\to \mathbb{R}$ to $f(r,\theta) = \lambda(\theta)r + (1-\lambda(\theta))r^2$. Since $\lambda(\cdot)$ goes between 0 (at $\theta \in \{0,\pi/2\}$) and 1 (at $\theta = \pi/4$), $f$ interpolates (rotationally) between linear and quadratic. The bad choice is $y = (1,0)$, $z =(1,\pi/2)$, and $w = (y+z)/2 = (\sqrt{2}/2,\pi/4)$.

Comment by Matus Telgarsky

2010-02-09T06:26:47Z

I should add that the feasibility set can also be the empty set, or it can be unbounded (but still an intersection of halfplanes)

Comment by Matus Telgarsky

2010-02-09T06:25:42Z

A couple things wrong here. first, the feasible set is a convex polytope, not necessarily a simplex. the simplex algorithm indeed walks the vertices, however there are many algorithms which behave otherwise (for instance en.wikipedia.org/wiki/Interior_point_method)

Comment by Matus Telgarsky

2010-02-08T21:57:19Z

@Harald: Sums are not always the same as integrals with counting measure: take any sum which converges nonabsolutely as an example. For instance define $f(n) := (-1)^nn^{-1}$ for $n\in\{1,2,3,\ldots\}$. The integral does not exist but the sum converges; this is remark 3.46 in baby rudin.

Comment by Matus Telgarsky

2010-01-25T07:00:12Z

I edited my answer a little bit. It seems the documents you point to make a weighted estimator of the sampled random variable, rather than estimating the weighted mean random variable. This is weird for me.

Comment by Matus Telgarsky

2010-01-16T16:39:24Z

@Anonymous Rex, YES, thank you, also have you thought about using the dinosaur from qwantz.com as your avatar? hopefully i don't get banned from mathoverflow for the non-mathematical nature of this comment. i'll point out that maybe the problem i should have given is the primality testing one, where the deterministic solution was found apparently by derandomizing some other randomized strategy for it (but not the miller-rabin primality test).

Comment by Matus Telgarsky

2010-01-16T13:51:19Z

@Anweshi: yes, i saw already, i didn't know about the stuff you mentioned! thanks! Actually I asked an expert I know about this question, his response was that there are some stochastic processes where the $\sigma$-algebra constructed is a disaster and completion is an approach to cleaning things up. I didn't post this though because I myself lack the background. I've thought about this question and still don't know of a situation where Lebesgue measure is preferable to Borel measure (on the reals). In general, is borel nice on topological spaces?