Por que a análise de Fourier das funções booleanas "funciona"?

60

Ao longo dos anos, me acostumei a ver muitos teoremas do TCS provados usando análise discreta de Fourier. A transformação Walsh-Fourier (Hadamard) é útil em praticamente todos os subcampos do TCS, incluindo testes de propriedades, pseudo-aleatoriedade, complexidade da comunicação e computação quântica.

Embora eu tenha me acostumado a usar a análise de Fourier das funções booleanas como uma ferramenta muito útil quando estou enfrentando um problema, e mesmo tendo um palpite bastante bom para os casos em que a análise de Fourier provavelmente produziria bons resultados; Devo admitir que não tenho muita certeza do que torna essa mudança de base tão útil.

Alguém tem uma intuição de por que a análise de Fourier é tão proveitosa no estudo da TCS? Por que tantos problemas aparentemente difíceis são resolvidos escrevendo a expansão de Fourier e realizando algumas manipulações?

Nota: minha principal intuição até agora, por mais escassa que seja, é que temos um bom entendimento de como os polinômios se comportam e que a transformação de Fourier é uma maneira natural de encarar uma função como um polinômio multilinear. Mas por que especificamente essa base? o que há de tão único na base das paridades?

Kristoffer Arnsfelt Hansen
fonte
8
Paging @ ryan-odonnell
Suresh Venkat
3
Uma idéia que flutuava nos anos 90 é que talvez outras bases de funções também funcionem, imitando talvez o sucesso das wavelets na análise harmônica clássica. Mas não vi essa ideia sendo perseguida.
Gil Kalai

Respostas:

63

Aqui está o meu ponto de vista, que aprendi com Guy Kindler, embora alguém mais experiente provavelmente possa dar uma resposta melhor: Considere o espaço linear das funções , e considere um operador linear da forma (para ), que mapeia uma função como acima para a função . Em muitas das questões do TCS, existe uma necessidade subjacente de analisar os efeitos que esses operadores têm em determinadas funções.σ w w { 0 , 1 } n f ( x ) f ( x + w )f:{0,1}nRσww{0,1}nf(x)f(x+w)

Agora, o ponto é que a base de Fourier é a base que diagonaliza todos esses operadores ao mesmo tempo, o que torna a análise desses operadores muito mais simples. De maneira mais geral, a base de Fourier diagonaliza o operador de convolução, que também subjaz a muitas dessas perguntas. Portanto, é provável que a análise de Fourier seja eficaz sempre que for necessário analisar esses operadores.

A propósito, a análise de Fourier é apenas um caso especial da teoria de representação de grupos finitos. Essa teoria considera o espaço mais geral das funções onde é um grupo finito e operadores da forma (para ) que mapeia para , a teoria permite que você encontre uma base que facilite a análise de tais operadores - embora para grupos gerais você não consiga realmente diagonalizar os operadores. G σ h h G f ( x ) f ( x h )f:GCGσhhGf(x)f(xh)

Ou Meir
fonte
6
Esta é uma excelente resposta.
Suresh Venkat
2
Ótima maneira de colocá-lo. Continuando na mesma linha, se você quiser olhar para as tuplas , a análise padrão de Fourier geralmente não é por mais tempo e pode ser útil mudar para a análise de Fourier de ordem superior . (f(x),f(x+w1),f(x+w2),f(x+w1+w2))
arnab
3
O que você quer dizer com "diagonalizar um operador"?
31712 John Moeller
10
John - Se você visualizar as funções como vetores em um subespaço, o operador é uma operação linear nos vetores e pode ser visualizado como uma matriz. Diagonalizar esse operador significa diagonalizar a matriz. f
Ou Meir
11
é interessante que mesmo aplicativos para o aprendizado de juntas possam ser entendidos em termos de operadores de convolução: uma junta é igual à sua imagem sob o operador que calcula a média das entradas que discordam de coordenadas irrelevantes. esse operador é um operador de convolução e é escasso no domínio fourier. este é um tema geral: quando uma função é "correlacionada com ela mesma" ele implora por uma abordagem baseada Fourier
Sasho Nikolov
6

Aqui pode haver outra opinião sobre essa questão.

Supondo que a função pseudo-booleana esteja limitada a k, a representação polinomial de Walsh da função pode ser decomposta em k subfunções. Todos os termos lineares são coletados em uma subfunção, todas as interações aos pares em uma subfunção, depois as interações de três vias, etc.

Cada uma dessas subfunções é uma "paisagem elementar" e, portanto, cada uma das subfunções é um vetor próprio da matriz de adjacência do Laplaciano (ou seja, a vizinhança da distância 1 de Hamming). Cada subfunção possui uma "Equação de Onda" correspondente ao tipo encontrado em todas as paisagens elementares. Exceto agora, existem k Equações de Ondas que atuam em combinação.

Conhecer as equações de onda torna possível caracterizar estatisticamente o espaço de pesquisa correspondente de maneiras bastante precisas. Você pode calcular média e variação e inclinar-se sobre bolas de Hamming arbitrárias (exponencialmente grandes) e sobre hiperplanos arbitrários do espaço de pesquisa.

Veja o trabalho de Peter Stadler sobre Paisagens Elementares.

Andrew Sutton e eu (Darrell Whitley) trabalhamos usando esses métodos para entender e melhorar os algoritmos de busca local para otimização pseudo-booleana. Você pode usar os polinômios de Walsh para identificar automaticamente movimentos aprimorados para algoritmos de pesquisa local. Nunca há necessidade de enumerar aleatoriamente vizinhanças do espaço de pesquisa. A análise de Walsh pode dizer diretamente onde estão os movimentos de melhoria.

Darrell Whitley
fonte
4
Você poderia fornecer algumas dicas para o trabalho que você cita?
András Salamon
2

uma ótima resposta para essa pergunta provavelmente ainda não existe porque é uma área de pesquisa relativamente jovem e muito ativa. por exemplo, o livro abrangente de Ingo Wegeners sobre funções booleanas de 1987 não tem nada sobre o assunto (exceto para analisar a complexidade do circuito da DFT).

uma intuição ou conjectura simples é que parece que grandes coeficientes de Fourier de ordem superior indicam a presença de subfunções que devem levar em conta muitas variáveis ​​de entrada e, portanto, requerem muitos portões. isto é, a expansão de Fourier é aparentemente uma maneira natural de medir quantitativamente a dureza de uma função booleana. não vi isso diretamente comprovado, mas acho que está sugerido em muitos resultados. por exemplo, o limite inferior de Khrapchenkos pode estar relacionado aos coeficientes de Fourier. [1]

outra analogia aproximada pode ser emprestada da EE ou de outros campos de engenharia até certo ponto, onde a análise de Fourier é usada extensivamente. é frequentemente usado para filtros EE / processamento de sinal . os coeficientes de Fourier representam uma "banda" específica do filtro. a história também é de que o "ruído" parece se manifestar em faixas particulares de frequências, por exemplo, baixa ou alta. no CS, uma analogia com o "ruído" é a "aleatoriedade", mas também é claro em muitas pesquisas (atingindo um marco em, por exemplo, [4]) que a aleatoriedade é basicamente o mesmo que complexidade. (em alguns casos, a "entropia" também aparece no mesmo contexto.) A análise de Fourier parece ser adequada para estudar o "ruído", mesmo nas configurações de CS. [2]

outra intuição ou imagem vem da teoria do voto / escolha. [2,3] é útil analisar funções booleanas como tendo subcomponentes que "votam" e influenciam o resultado. isto é, a análise da votação é uma espécie de sistema de decomposição para funções. isso também aproveita alguma teoria do voto que alcançou alturas de análise matemática e que aparentemente antecede o uso de muitas análises de Fourier de funções booleanas.

Além disso, o conceito de simetria parece ser primordial na análise de Fourier. quanto mais "simétrica" ​​a função, mais o coeficiente de Fourier cancela e também mais "simples" a função é calcular. mas também quanto mais "aleatória" e, portanto, mais complexa a função, menos os coeficientes se cancelam. em outras palavras, simetria e simplicidade e, inversamente, assimetria e complexidade na função parecem ser coordenadas de uma maneira que a análise de Fourier pode medir.

[1] Na análise de Fourier das funções booleanas de Bernasconi, Codenotti, Simon

[2] Uma breve introdução à análise de Fourier no cubo booleano (2008) por De Wolf.

[3] Alguns tópicos sobre a análise de funções booleanas por O'Donnell

[4] Provas naturais de Razborov & Rudich

vzn
fonte
3
veja também livro online Análise de funções booleanas por O'Donnell
vzn 22/09/12
re-conjectura sobre complexidade do booleano fn refletida no "espectro de potência" sobre os coeficientes de Fourier - uma extensão natural dos famosos resultados no artigo de Linial Mansour Nisan, circuitos de profundidade constante, transformada de Fourier e capacidade de aprendizagem . resumo: "o principal resultado é que um f ^ booleano AC ^ 0 tem a maior parte de seu 'espectro de potência' nos coeficientes de ordem baixa"
vzn
2
existe um bom levantamento da análise de fourier no ch2 do livro juknas, complexidade da função booleana, avanços e fronteiras , que aponta os coeficientes de fourier correlacionados às funções de paridade calculadas sobre subconjuntos de variáveis ​​de entrada.
vzn
2
Por que essa resposta é tão criticada?
user834