Multilayer (vanilla) RNN.

hₜˡ = tanh[ Wˡ ⋅ (hₜˡ⁻¹, hₜ₋₁ˡ)ᵀ ].

Assume that (Y₁, Y₂) follows a bivariate distribution with mean vector (μ₁, μ₂) and covariance matrix with entries σ₁², σ₂², σ₁₂, and let ρ=Cor(Y₁,Y₂).

If we collect i.i.d. observations (Yᵢ₁, Yᵢ₂) from this bivariate distribution, then the expected squared perpendicular distance of each such point from the 45 degree line in 2d plane is given by

E[(Y₁-Y₂)²] =
E[((Y₁-μ₁) - (Y₂-μ₂) + μ₁-μ₂)²] =
E[((Y₁-μ₁) - (Y₂-μ₂))²] + (μ₁-μ₂)² =
(μ₁-μ₂)²+σ₁²+σ₂²-2σ₁₂ =

Another elegant bound that's stronger for small x is

P(|X| > x) ≤ exp(-x² / 2)

for X ~ N(0, 1) and x >0.

(but I'm not aware of a proof quite as short as the previous one)

Let \(X \sim \mathcal{N}(0, 1)\) and \(x > 0\).

\mathbb{P}(X > x)
\leq \frac{1}{\sqrt{2\pi}} \int_x^\infty \frac{t}{x} e^{-t^2/2} \,\mathrm{d}t
= \frac{e^{-x^2/2}}{x \sqrt{2\pi}}.

Quite elegant!


@11011110 @axiom I agree with you for statements involving a function on the left hand side, such as f(x) = O(g(x)), as I mentioned before.
But do you not think that it’s confusing to write “O(log(n)) = O(n)”, when what meant is “f(n) = O(log(n)) implies that f(n) = O(n)”?
What notation would you have used for the chain of strict subset relationships in my original post?

This one is interesting too:

∀ a>0, b>1: O(log_b(n)) ⊂ O(nᵃ).

@axiom @11011110 Exactly. I used "<" in the sense of "strict subset" (maybe I should have used "⊂").

Saying something like
O(log(n)) = O(n) seems too much of an abuse of notation for my taste (because O(n) = O(log(n)) is false).

Not sure if "=" is always an abuse of notation for Landau symbols, but at least it's convenient for things like f(x) = g(x) + O(x²). In the previous case, I would prefer it meant equivalence.

< O(log(n))
< O(sqrt(n))
< O(n)
< O(n log(n))
< O(n²)
< O(2ⁿ)
< O(n!)

Differential privacy [5/n]




Differential privacy [4/n]

What does a differentially private data access mechanism look like?

The simplest example is the Laplace Mechanism:

The Laplace Mechanism, given by



Differential privacy [3/n]




This holds:

M is (ε, δ)-differentially private if
P(privacy loss ≤ ε) ≥ 1 - δ.



Differential privacy [2/n]

The defining inequality
has an intuitive meaning.


Differential privacy [1/n]



Let Zᵐ be a space of datasets with m rows.
M is called (ε, δ)-differentially private if


Convergence in distribution

A seq. X₁, X₂, ... of R-valued random vars. converges in distribution (or converges weakly, or in law) to a random var. X
⇔ lim Fₙ(x) = F(x) as n→∞ for all continuity points x of F
⇔ E(f(Xₙ))→E(f(X)) for all bounded Lipschitz f
⇔ liminf E(f(Xₙ))≥E(f(X)) for all non-negative continuous f
⇔ liminf P(Xₙ∈G)≥P(X∈G) for every open set G
⇔ limsup P(Xₙ∈F)≤P(X∈F) for every closed set F
⇔ P(Xₙ∈B)→P(X∈B) for all continuity sets B of X (i.e., P(X∈∂B)=0)

How many can you prove?

Var(X) = E((X - E(X))²)
= E(X²) - E(2XE(X)) + E(X)²
= E(X²) - E(X)².

Probability distribution trivia:

If X ~ Beta(α, β), then
E(Xᵏ) = (α + k - 1) / (α + β + k - 1) E(Xᵏ⁻¹).

[cont.] Kullback–Leibler divergence.

Following that line of thought, the Kullback-Leibler divergence between p and q is simply the difference between cross-entropy(p, q) and entropy(p):

D(p||q) =
= ∑ᵢ pᵢ log₂(pᵢ / qᵢ)
= ∑ᵢ pᵢ log₂(1/qᵢ) - ∑ᵢ pᵢ log₂(1/pᵢ)
= H(p, q) - H(p)

[cont.] Cross-entropy.

By that interpretation, in contrast to entropy, cross-entropy is the expected number of bits per transmission under a potentially suboptimal encoding {log₂(1/q₁), log₂(1/q₂), ...}, which is based on a potentially inaccurate distribution {q₁, q₂, ...} for the symbols. That is, mathematically cross-entropy is given by:

H(p, q) = ∑ᵢ pᵢ log₂(1/qᵢ).

(my understanding of information theory is very rudimentary)

Let's say you want to send symbols as messages through a binary channel (0s and 1s). Let pᵢ denote the relative frequency of i'th symbol. Then, to use the smallest number of bits per transmission on average, you should assign log₂(1/pᵢ) bits to the i'th symbol (afaik; don't know if fully correct, or how to prove...).
The entropy is just the expected number of bits per transmission under this optimal encoding:
∑ᵢ pᵢ log₂(1/pᵢ).

Law of total probability/expectation

The probability of an event can be written as a weighted sum of conditional probabilities.

The expected value of a random variable can be written as a weighted sum of conditional expected values.

If {Aᵢ}ᵢ is a finite or countably infinite partition of the sample space, then

P(B) = ∑ᵢ P(B | Aᵢ) P(Aᵢ)

E(X) = ∑ᵢ E(X | Aᵢ) P(Aᵢ)

Show more

A Mastodon instance for maths people. The kind of people who make \(\pi z^2 \times a\) jokes. Use \( and \) for inline LaTeX, and \[ and \] for display mode.