Estimando a média no tempo polinomial

20

Seja uma função. Queremos estimar a média de ; ou seja: .f E [ f ( n ) ] = 2 - nx { 0 , 1 } n f ( x )f:{0,1}n(2n,1]fE[f(n)]=2nx{0,1}nf(x)

NOTE: In the OP, the range of f was [0,1]. I changed this a bit for technical reasons. (This should simplify the problem; if not, forget it!)

Seja o algoritmo estimador (randomizado). Suponha que tenha acesso à caixa preta para . Denotamos isso por .E f E fEEfEf

Existem duas condições:

1) tempo de funcionamento da Estimador: Existe um único polinómio de tal modo que para todos os e todos , o tempo de execução do é delimitada por .n f E f ( 1 n ) p ( n )p()nfEf(1n)p(n)E[f(n)]

2) Precisão do estimador com confiança :δ q ( ) n f 1 existe um único polinômio , tal que para todo e todo , temos com probabilidade de pelo menos .q()nfδ1q(n)<Ef(1n)E[f(n)]<q(n)δ

NOTE: The confidence δ was not in the OP. The parameter δ is in (0,1), and may depend on n. For instance, it may be 1-1/2^n.

Existem tais estimadores?

Antecedentes e Motivação

Eu não mencionei minha motivação no início, pois requer muito conhecimento prévio. De qualquer forma, para os entusiastas, descrevo-o brevemente: A necessidade de tais estimadores surge no contexto de "Provas de capacidade", conforme definido no seguinte artigo:

Mihir Bellare, Oded Goldreich. Proving Computational Ability , 1992. Manuscrito não publicado.

Especificamente, na parte inferior da página 5, os autores assumiram implicitamente a existência de tais estimadores (não há menção à precisão e o tempo de execução não é definido com precisão; ainda assim, o contexto define tudo claramente).

Minha primeira tentativa foi ler " Uma amostra de amostradores - uma perspectiva computacional sobre amostragem ". Pertence a um problema muito semelhante, mas a probabilidade de erro definida é aditiva, enquanto a nossa é multiplicativa. (Eu não li completamente o artigo, talvez ele mencione o que eu preciso em algum lugar.)

EDIT (conforme solicitação de Tsuyoshi): De fato, a definição de "Provas de Habilidade Computacional" requer a existência de um "extrator de conhecimento" cujo tempo de execução (esperado) seja . Como não conhecemos , queremos estimar isso; no entanto, isso não deve alterar o tempo de execução consideravelmente: deve ser alterado para um fator polinomial. A condição de precisão tenta capturar esse requisito. E[f(n)]p(n)E[f(n)]E[f(n)]

MS Dousti
fonte
Não consigo entender a condição de precisão. O que impede que o algoritmo E sempre produza 1? Você quis dizer 1 / q (n) <(valor verdadeiro) / (valor estimado) <q (n)?
Tsuyoshi Ito
Parece que p (n) = q (n) = O (1) e o algoritmo trivial que gera "1" devem funcionar. O tempo de execução é O (1), limitado por . E sua precisão é <= 1, que é menor que q (n). p ( n )Ef(1n)p(n)E[f(n)]
Robin Kothari
@ Tsuyoshi & Robin: Desculpe pessoal, perdi uma condição na precisão. Verifique isso agora!
MS Dousti 2/10/10
Além disso, acho que o estimador é randomizado (apenas porque parece impossível de outra forma). É esse o caso? Além disso, se for, o que a condição de tempo de execução e a precisão precisam exatamente?
Tsuyoshi Ito
1
Eu acho que não entendo claramente a pergunta. Por que um amostrador ingênuo com um limite chernoff não é um bom estimador?
Sylvain Peyronnet

Respostas:

15

EDIT: Isso resolve a versão do problema em que f apenas gera 0 ou 1. Mas acho que a solução pode ser adaptada para fazê-la funcionar no caso mais geral.

Talvez eu tenha entendido mal a pergunta, mas isso não parece muito difícil.

Em vez de estimar, a média, vamos pensar em estimar o número de 1s e chamar esse número k. Seja . Então a média é k / N. Você deseja estimar isso dentro de um fator multiplicativo polinomial no tempo O (N polilog (N) / k).N=2n

Eu acho que isso pode ser feito dentro de qualquer fator multiplicativo constante também. Por exemplo, digamos que você queira estimar isso dentro de um fator de 2. Portanto, a saída do algoritmo estará entre k / 2 e 2k.k

Esboçarei um algoritmo, que deve ter o tempo de execução apropriado. Primeiro verifique se k está entre N / 2 e N. Isso é fácil, basta amostrar alguns valores aleatórios e se você tiver mais de meio segundo, então está nesse intervalo. Então você tem uma aproximação 2. Caso contrário, verifique se está entre N / 4 e N / 2. E assim por diante. Toda vez que você diminui o intervalo, é mais caro estimar se k está nesse intervalo. Mas o custo é inversamente proporcional ao tamanho do intervalo.

Por exemplo, se você estiver verificando se k está entre e , precisará fazer consultas . De qualquer forma, depois de repetir esse procedimento várias vezes, você deve obter o intervalo em que k se encontra. Digamos que k esteja entre e . Então k é aproximadamente . Então é sobre k / N. Portanto, nesta etapa, gastaríamos consultas O (k / N). Mas chegar a essa etapa exigiu q outras etapas, mas esse é apenas um fator extra de polilog (N). Portanto, o tempo total de execução é O (N polylog (N) / k), para uma aproximação de 2. 2 N / 2 q O ( 2 q ) N / 2 q 2 N / 2 q N / 2 q 2 qN/2q2N/2qO(2q)N/2q2N/2qN/2q2q

(Na verdade, seria necessário amplificar o erro para obter precisão decente em cada etapa. Mas isso é apenas um fator extra de polilog.)


A razão pela qual gosto de pensar nesse processo de várias etapas é que ele destaca o processo como um palpite e verifica a precedência. Se alguém lhe que está entre e , você poderá estimar com precisão ainda melhor sabendo esse fato, no prazo prometido. Portanto, precisamos eliminar a etapa de adivinhar o . Isso é feito através da pesquisa binária em todos os intervalos possíveis desse tipo.N / 2 q 2 n / 2 q kkN/2q2n/2qk

Para fazer isso funcionar no caso de saídas não booleanas, em vez de contar o número de 1s, basta somar os valores vistos. Vou tentar encontrar uma referência para mostrar que isso funciona rigorosamente.

Robin Kothari
fonte
(1) Como a função f pode assumir valores não integrais, provavelmente você deseja usar a soma dos valores em vez do número de 1s. (2) Temos que estimar estágio por estágio? Suponho que podemos fazer isso em um único estágio, apenas repetindo até que a soma exceda um polinômio fixo. Veja também meu comentário à pergunta.
Tsuyoshi Ito
Ah, eu não notei que o intervalo é [0,1]. Eu pensei que era {0,1}. Mas acho que o mesmo procedimento funciona. Talvez possamos reduzir um problema ao outro, pois podemos "contar" o número de 1s em uma posição específica da representação binária da saída com precisão suficiente. Sobre (2), acho que seu procedimento é equivalente. Penso dessa maneira, pois parece um processo de adivinhação e verificação, ou seja, dada uma estimativa ruim de k, obtenha uma melhor. Vou adicionar isso na minha resposta.
Robin Kothari
Concordo que os dois algoritmos são essencialmente os mesmos. Além disso, como em [0,1] e {0,1}, seu algoritmo provavelmente funciona como indicado após a substituição de cada avaliação de um valor não integral f (x) por um lançamento de moeda (1 wp f (x) e 0 wp 1-f (x)).
Tsuyoshi Ito
@ Robin: Obrigado pela resposta. Algo também não está claro para mim: você disse: "Apenas experimente alguns valores aleatórios e, se você tiver mais de meio segundo, está nesse intervalo". Acredito que isso deve ser quantificado: quantas amostras resultam em que precisão? (Eu mudei OP considerar tal confiança Caso contrário, seria impossível projetar o amostrador necessário.!)
MS Dousti
@Sadeq: isso é um limite chernoff. se você espera que k seja n / 2 (uma moeda justa, por exemplo), pode anotar rapidamente um limite de cauda para ver mais de n (1 + eps) / 2 e da mesma forma para o limite inferior.
Suresh Venkat
3

Deixe denotar os valores de aplicados a uma sequência infinita de amostras aleatórias (com substituição) de . Seja o número inteiro menos positivo que para algum valor , talvez . Eu acho que o estimador deve realizar o que você deseja.f1,f2,f{0,1}nki=1kfiMMM=polylog(n)M/k

Para a análise, você não pode aplicar os limites de Chernoff diretamente à variável aleatória mas há um truque para permitir que você use Chernoff de qualquer maneira. Vamos denotar a expectativa desconhecido . Encontre as constantes e (funções de ) para que, com probabilidade pelo menos , tenhamos e . Essas somas de s podem ser limitadas usando Chernoff. Segue-se que com probabilidade de pelo menos e, portanto, o estimadorμ E ( f ) k l O w K H i g h μ 1 - ô Σ k l o w i = 1 f i < H Σ k h i g h i = 1 f i > H f i k L O w < k < k h i g h 1 - δkμE(f)klowkhighμ1δi=1klowfi<Mi=1khighfi>Mfiklow<k<khigh1δM/k está bem concentrado.

Warren Schudy
fonte