decision problem:$L\subset \{ 0,1 \}^*$
不存在一个算法判定$x$是否属于$L$

如何证明Komogorov Complexity是不可计算问题？
给定一个bit 串，找出生成该比特串的最小程序长度

$\exists$ program $p$, $\forall s\in \{0,1\}^*$, $p(s)=K(s)$ ,其中K表示串s的Komogorov Complexity
Then $\exists \tilde{p}$ output the first string s such that

$$l(\tilde p) \leq l(p)+\log(10^{100}) + const.$$

随着串复杂度增加，s的$K(s)$总会大于$l(\tilde p)$，从而$l(\tilde p)$成为表示s的最小串长度，因而产生矛盾

Lecture 8 Max Entrpoy

在求解欠定方程的时候，我们无法在许多解中确定所需的那个，有时我们会取解的模长最小的那个。在概率分布中有时也会面临同样的问题。
probability distribution estimation with partial information

1. Let f be a probability distribution with constraints:
   • $f(x)\geq 0,\forall x$
   • $\int_{0}^\infty f(x)\mathrm{d}x = 1$
   • $\int_{-\infty}^\infty g_{i}(x) f(x)\mathrm{d}x=r_{i}, for\ \ i=1,2,\dots,n$
     用熵最大的依据是：最大熵对应的分布通常没有额外的约束，而熵不是最大的概率分布往往会有其他的约束。
     例子：已知连续概率分布f满足$E(X)=0,Var(X)=1$，求最大熵对应的分布？
     也就是

     $$\arg\min _{f} \int_{-\infty}^\infty -f\log f\mathrm{d}x$$

     constraints:
     $$
     \begin{align}
     \int _{-\infty}^\infty f(x), dx=1 \

\int_{-\infty}^\infty xf(x) , dx =0 \
\int _{-\infty}^\infty x^2f(x), dx = 1
\end{align}

$$变分法：$$

\int _{-\infty}^\infty \delta(f\log f)+\lambda\delta f+\mu x\delta f+\nu x^2\delta f, dx = 0
$
$

$$\int (\log f+1+\lambda+\mu x+\nu x^2)\delta f \, dx = 0$$

得到$f(x)=e^{-\nu(x-x_{0})^2-\lambda'}$
作业：证明正态分布$N(0,\sigma^2)$是在给定限制$E(X)=0,Cov(X)=\sigma^2$情形下的最大熵分布。![[src/Pasted image 20230410204048.png]]

证明：
计算任意满足条件的分布$f$与gaussian distribution$g(x) = C e^{-\frac{x^2}{2\sigma^2}}$的交叉熵：

$$\begin{align} D(f\mid\mid g) &= \int f(x)\log \frac{f(x)}{g(x)} \, d x \\ & = \frac{1}{2} -H(f) - \log(C) \\ &= H(g)-H(f) \geq 0 \end{align}$$

得证

Leave a Comment

Plain Markdown

Post Comment

Markdown Preview