delta2323 / ml-formulas Goto Github PK
View Code? Open in Web Editor NEW機械学習・統計学・理論計算科学などに出てくる等式・不等式を集めていきます
License: MIT License
機械学習・統計学・理論計算科学などに出てくる等式・不等式を集めていきます
License: MIT License
関数$f\colon{-1,1}^n \to \mathbb{R}$と実数$\rho \in [-1,1]$に対し,
$$
T_\rho f(x)=\mathbb{E}{y∼N\rho(x)}[f(y)]
$$
と定義する.
ここで$y∼N_\rho(x)$とは,各$i \in {1,\ldots,n}$について独立に
$$
y_i = \begin{cases}
x_i & \text{確率 } \frac{1+\rho}{2}\
-x_i & \text{確率 } \frac{1-\rho}{2} \
\end{cases}
$$
と選ぶことを指す.
このとき関数$f: {-1,1}^n \to \mathbb{R}$と,$0 \leq \rho \leq \sqrt{\frac{p-1}{q-1}}$なる実数$1 \leq p \leq q \leq \infty$に対して,
$$
|T_\rho f|_q \leq |f|_p
$$
が成り立つ.
R. O'Donnell. Analysis of Boolean Functions (2014).
$$
\psi_{Y} (\lambda) = v\phi(\lambda),
$$
ここで,$\phi(u) := e^u-u-1$である.さらに,$\psi_Y$のCramer変換,$\psi_Y^{\ast}(t) := \sup_{\lambda>0} e^{\psi_Y (\lambda) -\lambda t}$ は
$$
\psi_Y^{\ast}(t) = vh\left(\frac{t}{v}\right)
$$
である,ここで$h(u) := (1+u)\log (1+u) - u (u>0)$である.
Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)
$$
\mathbb{P} \{|X - \mathbb{E}| \geq t\} \leq \frac{\mathrm{Var}(X)}{t^2}
$$
が成り立つ.
Markovの不等式(#1)から証明可能
Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)
確率分布間距離の比較についてのエントリが複数あるため (Le Camの不等式,Pinskerの不等式),距離尺度の定義の一覧と,それらの強弱関係をまとめたページがあると良いかもと思いました.
Gibbs and Su (2002) Figure 1が有益
$$
\mathbb{P}\{ |X - \mathbb{E}X| \geq t\} \leq e^{\psi_{X}(\lambda)-\lambda t}.
$$
ここで,$\psi_{X}$は$X$の生成母関数の対数,$\psi_{X}(\lambda):=\log \mathbb{E}\left[e^{\lambda X} \right]$.
Markovの不等式(#1)から証明できる
この不等式により,期待値周りの確率集中は生成母関数の対数$\psi_X$を評価することに帰着される
Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)
が成立する.ここで,$\psi_S$は確率変数の生成母関数の対数,すなわち$\psi_S(\lambda) := \mathrm{\log} \mathbb{E}\left[ e^{\lambda S} \right]$,$v := \sum_{i=1}^N \mathbb{E}[X_i^2]$,$\phi(u)$は$Z$をパラメータ$1$のポアソン分布とした時,$Z-1$の生成母関数の対数,すなわち$\phi(u) := e^u-u-1$である.
さらに,任意の$t>0$に対して,
が成立する.ここで,$h(u) := (1+u)\log (1+u) - u (u>0)$である.
Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)
この定理と「sub Gaussian性の必要十分条件」から,有界で独立な確率変数達の和はsub Gaussianであることがわかる.
Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)
$$
\mathbb{P} (X \geq t) \leq \frac{\mathbb{E}\left[X\right]}{t}
$$
が成り立つ.
任意の$t\geq 0$に対して,
$$
X \geq t\mathbb{1}_{\{X\geq t\}}
$$
が成り立つので,期待値を取って,
両辺を$t$で割れば不等式が得られる.
Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)
@book{boucheron2013concentration,
title={Concentration inequalities: A nonasymptotic theory of independence},
author={Boucheron, St{\'e}phane and Lugosi, G{\'a}bor and Massart, Pascal},
year={2013},
publisher={Oxford university press}
}
が成立する.ここで,$h(u) = (1+u)\log (1+u) - u (u>0)$である.
Bennettの不等式(#5)と不等式
$$
h(u) \geq \frac{u^2}{2(1 + \frac{u}{3})}
$$
から導かれる.
Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.