Матеріал з Вікіпедії — вільної енциклопедії.
Ентропія Фур'є (англ. Fourier entropy ) або спектральна ентропія (англ. spectral entropy )[1] для функції
f
:
{
−
1
,
1
}
n
→
R
{\displaystyle f:\{-1,1\}^{n}\to \mathbb {R} }
визначається як
E
(
f
)
=
−
∑
S
⊆
{
1
,
.
.
.
,
n
}
f
2
^
(
S
)
log
2
f
2
^
(
S
)
=
∑
S
⊆
{
1
,
.
.
.
,
n
}
f
^
(
S
)
2
log
2
1
f
^
(
S
)
2
{\displaystyle 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}}}}
,
де
f
^
:
2
{
1
,
.
.
.
,
n
}
→
R
{\displaystyle {\hat {f}}:2^{\{1,...,n\}}\to \mathbb {R} }
[2] позначає перетворення Фур'є від
f
{\displaystyle f}
[3] .
Нагадаємо що ентропія Шеннона для серії випадкових подій
x
{\displaystyle x}
має аналогічний вигляд:
H
(
X
)
=
−
∑
i
=
1
n
P
(
x
i
)
log
2
P
(
x
i
)
,
{\displaystyle \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
→
R
{\displaystyle f:\{-1,1\}^{n}\to \mathbb {R} }
може бути однозначно виражена як мультилінійний многочлен (многочлен від багатьох змінних лінійний по кожній з них):
f
(
x
)
=
∑
S
⊆
{
1
,
.
.
.
,
n
}
C
S
∏
i
∈
S
x
i
{\displaystyle f(x)=\sum _{S\subseteq \{1,...,n\}}C_{S}\prod _{i\in S}x_{i}}
,
де кожен
C
S
{\displaystyle C_{S}}
є дійсним числом[2] . (
∀
x
:
∏
i
∈
∅
x
i
=
1
{\displaystyle \forall x:\prod _{i\in \emptyset }x_{i}=1}
) Це розклад Фур'є такої функції.
Коефіцієнт
C
S
{\displaystyle C_{S}}
зазвичай позначають як
f
^
(
S
)
{\displaystyle {\hat {f}}(S)}
,
{
1
,
.
.
.
,
n
}
{\displaystyle \{1,...,n\}}
як
[
n
]
{\displaystyle [n]}
, а одночлен
∏
i
∈
S
x
i
{\displaystyle \prod _{i\in S}x_{i}}
як
χ
S
(
x
)
{\displaystyle \chi _{S}(x)}
, тому часто можна бачити запис:
f
(
x
)
=
∑
S
⊆
[
n
]
f
^
(
S
)
χ
S
(
x
)
{\displaystyle f(x)=\sum _{S\subseteq [n]}{\hat {f}}(S)\chi _{S}(x)}
Приклади
Функція що повертає найменший з двох аргументів (по суті кон'юнкція ):
m
i
n
2
(
x
)
=
−
1
2
+
1
2
x
1
+
1
2
x
2
+
1
2
x
1
x
2
{\displaystyle 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
(
m
i
n
2
)
=
−
4
⋅
1
2
2
log
2
1
2
2
=
−
log
2
1
4
=
2
{\displaystyle 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
{\displaystyle f(x)=1}
E
(
f
)
=
−
1
log
2
1
=
0
{\displaystyle 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 (PDF) . Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing . STOC '08. New York, NY, USA: ACM. с. 569—578. doi :10.1145/1374376.1374458 . ISBN 978-1-60558-047-0 . Процитовано 29 січня 2017 .
↑ Chakraborty, Sourav; Kulkarni, Raghav; Lokam, Satyanarayana V.; Saurabh, Nitin (22 листопада 2016). Upper bounds on Fourier entropy (PDF) . Theoretical Computer Science . Computing and Combinatorics. 654 : 92—112. doi :10.1016/j.tcs.2016.05.006 . ISSN 0304-3975 . Процитовано 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 .