Ентропія Фур'є

Ентропія Фур'є (англ. Fourier entropy) або спектральна ентропія (англ. spectral entropy)[1] для функції $f:\{-1,1\}^{n}\to \mathbb {R}$ визначається як

E(f)=-\sum _{S\subseteq \{1,...,n\}}{\hat {f^{2}}}(S)\log _{2}{\hat {f^{2}}}(S)=\sum _{S\subseteq \{1,...,n\}}{\hat {f}}(S)^{2}\log _{2}{\frac {1}{{\hat {f}}(S)^{2}}}

,

де ${\hat {f}}:2^{\{1,...,n\}}\to \mathbb {R}$ [2] позначає перетворення Фур'є від $f$ [3].

Нагадаємо що ентропія Шеннона для серії випадкових подій $x$ має аналогічний вигляд:

\mathrm {H} (X)=-\sum _{i=1}^{n}{\mathrm {P} (x_{i})\log _{2}\mathrm {P} (x_{i})},

Розклад Фур'є булевої функції

Для позначення булевих значень 0 і 1, вибирають кодування -1, 1[4]. Кожна функція $f:\{-1,1\}^{n}\to \mathbb {R}$ може бути однозначно виражена як мультилінійний многочлен (многочлен від багатьох змінних лінійний по кожній з них):

f(x)=\sum _{S\subseteq \{1,...,n\}}C_{S}\prod _{i\in S}x_{i}

,

де кожен $C_{S}$ є дійсним числом[2]. ( $\forall x:\prod _{i\in \emptyset }x_{i}=1$ ) Це розклад Фур'є такої функції.

Коефіцієнт $C_{S}$ зазвичай позначають як ${\hat {f}}(S)$ , $\{1,...,n\}$ як $[n]$ , а одночлен $\prod _{i\in S}x_{i}$ як $\chi _{S}(x)$ , тому часто можна бачити запис:

f(x)=\sum _{S\subseteq [n]}{\hat {f}}(S)\chi _{S}(x)

Приклади

Функція що повертає найменший з двох аргументів (по суті кон'юнкція):

min_{2}(x)=-{\frac {1}{2}}+{\frac {1}{2}}x_{1}+{\frac {1}{2}}x_{2}+{\frac {1}{2}}x_{1}x_{2}

[4]

E(min_{2})=-4\cdot {\frac {1}{2^{2}}}\log _{2}{\frac {1}{2^{2}}}=-\log _{2}{\frac {1}{4}}=2

Функція від однієї змінної що завжди повертає 1:

f(x)=1

E(f)=-1\log _{2}1=0

Властивості

З нерівності Єнсена можна вивести що найменше значення ентропії Фур'є - нуль[1].

Посилання

Kalai, Gil (17 серпня 2007). The entropy/influence conjecture. What's new. Процитовано 29 січня 2017.
O'Donnell, Ryan (2008). Some Topics in Analysis of Boolean Functions. Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing. STOC '08. New York, NY, USA: ACM. с. 569–578. ISBN 978-1-60558-047-0. doi:10.1145/1374376.1374458. Процитовано 29 січня 2017.
Chakraborty, Sourav; Kulkarni, Raghav; Lokam, Satyanarayana V.; Saurabh, Nitin (22 листопада 2016). Upper bounds on Fourier entropy. Theoretical Computer Science. Computing and Combinatorics 654: 92–112. ISSN 0304-3975. doi:10.1016/j.tcs.2016.05.006. Процитовано 29 січня 2017.
O'Donnell, Ryan (5 червня 2014). Analysis of Boolean Functions (вид. 1 edition). New York, NY: Cambridge University Press. ISBN 978-1-107-03832-5.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[gil-1] Kalai, Gil (17 серпня 2007). The entropy/influence conjecture. What's new. Процитовано 29 січня 2017.

[some_topics-2] O'Donnell, Ryan (2008). Some Topics in Analysis of Boolean Functions. Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing. STOC '08. New York, NY, USA: ACM. с. 569–578. ISBN 978-1-60558-047-0. doi:10.1145/1374376.1374458. Процитовано 29 січня 2017.

[upper_bounds-3] Chakraborty, Sourav; Kulkarni, Raghav; Lokam, Satyanarayana V.; Saurabh, Nitin (22 листопада 2016). Upper bounds on Fourier entropy. Theoretical Computer Science. Computing and Combinatorics 654: 92–112. ISSN 0304-3975. doi:10.1016/j.tcs.2016.05.006. Процитовано 29 січня 2017.

[odonnel_analysis-4] O'Donnell, Ryan (5 червня 2014). Analysis of Boolean Functions (вид. 1 edition). New York, NY: Cambridge University Press. ISBN 978-1-107-03832-5.