Loading
Nota de Estudos
Study Reminders
Support
Text Version

Aleatoriedade e Distância Total de Variação

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Assim, comecemos por introduzir um outro conceito relacionado com a incerteza, a saber, o da Randomness. Nas duas palestras anteriores, identificamos a entropia como uma medida de incerteza e, portanto, as informações reveladas quando se observa uma variável aleatória x gerada a partir de uma distribuição p é uma. Então, esse é x que é gerado a partir de uma distribuição p é entropia de p, H de p que eu defino como somatória sobre x px log 1 por px porque informação, como você lembra foi redução na incerteza, ok.
Então, por que o H de p, porque bem a incerteza antes da resposta foi revelada a você foi H de p e depois que a resposta é revelada a você é 0. E assim sendo, portanto, a informação é H de p menos, que é apenas H de p. Mas estamos a chamar a isso uma medida de incerteza e definimos um problema relacionado com a compressão, para medir a incerteza ou para, pelo menos, dar um significado operacional à incerteza mas há uma outra noção nacional de incerteza, nomeadamente a da aleatoriedade numa variável aleatória.
Sendo assim, uma variável aleatória é realmente aleatória e como a incerteza se relaciona com a aleatoriedade? Esta é a pergunta que estabelecemos para responder nesta nas palestras desta semana, certo, portanto há duas maneiras possíveis de medir o quanto a aleatoriedade está aí em uma variável aleatória x. Quais são essas duas maneiras possíveis? Aqui estão essas duas definições possíveis. Primeiro, pode-se perguntar quantos bits aleatórios são necessários para gerar a variável aleatória.
Então, essa variável aleatória tem uma distribuição especificada e você quer gerá-la, mas você só tem um bits independente aleatório perfeito e imbirentado disponível para você. Quantos bits você precisa para gerar essa variável aleatória x? Assim, se você escrever um código de computador onde se gera uma amostra dessa variável aleatória x com este pmfp que computador quantas vezes vai que o código do computador acesse esta função, o que gera um bit aleatório que é uma maneira de pensar nele.
Esta é uma medida razoável de aleatoriedade em uma variável aleatória x ou associada a um pmfp. Alternativamente, podemos pensar nesta definição verde. Quantos bits aleatórios podem ser gerados a partir de ok para gerar, você precisa gerar, e quantas aleatoriedade pode ser gerada a partir dessa variável aleatória x? Então, quantos bits aleatórios independentes você consegue extrair dessa variável aleatória x? Então, esta é uma espécie de entrada. Assim, você confere bits aleatórios como entrada para um, para uma função, e ele dá saída como saída. Ele dá a amostra como a saída que ele dá uma amostra dessa distribuição.
Aqui o que estamos pedindo é você tomar como uma entrada x e saída bits aleatórios. Quantos bits podem ser extraídos fora deste x? Essas duas questões podem ser pensadas como medidas naturais de respostas a essas duas questões podem ser pensadas como medidas naturais de incerteza, medidas naturais de aleatoriedade em uma variável aleatória. E vamos examinar ambas as definições esta semana, de modo que apenas para tornar as coisas concretas, vejamos alguns exemplos.
Vejamos este primeiro exemplo sobre quantos flips de moedas independentes, não tendenciados, são necessários para gerar amostras a partir dessas duas distribuições. Por isso, antes de prosseguir, vou solicitar a pausa e pensar sobre esta resposta para ambos esses exemplos. E quando você voltar, eu estarei lhe dizendo a resposta, tudo bem para a primeira pergunta, o que podemos fazer? Então, você precisa gerar 3 símbolos; a, b, c.
E um deve ter probabilidade metade, b deve ter probabilidade um quarto, c deve ter probabilidade um quarto. Aqui está uma maneira de fazê-lo usando 2 moedas aleatórias, 2 moedas aleatórias aleatórias. Primeiro a gente flip uma moeda se for. Então, se nós flip uma moeda 2 vezes, então se o primeiro é de cabeça então nós declaramos um, ok. Se for cauda então a gente flip uma moeda outra vez. Então, se isso assim talvez eu devesse fazer melhor mais uma vez.
Então você flip uma moeda. Se é cabeça você declara um, se é cauda você declara, você flip a segunda moeda. Se a segunda moeda é cabeça, você declara b. Então, se a segunda moeda é cabeça, então declare b, se a segunda moeda é cauda deve declarar c. Então, qual é a probabilidade de um? É a metade. Qual é a probabilidade de b? É a metade da metade, que é uma quarta. Qual é a probabilidade de c? É a metade em metade que é de um quarto. Então, nós dois tosses de moedas, eu sou capaz de gerar uma amostra dessa variável aleatória com distribuição uma metade, uma quarta, uma quarta.
Agora, que tal esse? Quantas tosses de moedas você precisa fazer para gerar uma amostra a partir disso. Se você pensar em um procedimento como o que temos aqui, o que você logo perceverá é que para obter uma probabilidade como 1 acima de 3 de moeda, moeda imparcial que é a probabilidade meia, você precisa infinitamente muitas, você pode precisar de infinitamente muitas amostras, ok. Então, nós temos que colocar essa questão melhor e podemos fazer perguntas como quantas amostras precisamos?
Quantas flip de moeda unbiased precisamos on? Então, quantos direito, quantos. Em média na expectativa essa é uma questão melhor para gerar uma amostra dessa distribuição, e essa será a medida da aleatoriedade nessas duas variáveis aleatórias. Vejamos esta outra questão, que é uma espécie de famosa. Ela foi estudada por Von Neumann pode estar cerca de 70 anos de volta.
Então, suponhamos que eu lhe dê acesso a amostras dessa distribuição Bernoulli p e você quer gerar uma amostra dessa moeda imparcial esta é a segunda questão, a que nós criamos aqui. Então, este é o primeiro que vimos um exemplo, este é o segundo. Então como você faz isso? E qual é o número mínimo de flip de moedas que você precisa para fazer isso, número mínimo de clipes de moeda dessa moeda para fazer isso? Então, você quer gerar uma moeda imparcial de um biased one.
Portanto, aqui está um protocolo que na verdade Von Neumann deu que não é o ideal, mas vai dar algum exemplo. Então, o que você faz é tosse a moeda 2 vezes. Se ambas as saídas são as mesmas, então você joga de novo mas você pára quando ambas as saídas são diferentes. Então, você pára quando a saída é HT ou TH quando é HT você declara 0 e é TH você declara 1 ou vice-versa o que preferir.
Aí você pode mostrar essa condição sobre o fato de que você para com essa probabilidade de 0 1 é 0 e 1 são iguais e ela apenas a metade. Então, essa é uma maneira de gerar uma moeda imbitada de tendida a biased one. Na verdade, você pode computar o número esperado de tosses de moedas a partir dessa moeda que você vai levar para parar que vai se transformar. Bem você para quando tem isso ou isso, a probabilidade disso ou isto é de 2 em p em 1 menos p.
E, portanto, o número esperado de tosses de moedas que você precisa parar é de 1 por 2 em p em 1 menos p, ok. Você pode verificar se trata-se de uma distribuição geométrica, a distribuição da variável aleatória que indica um número de tosses após o qual você parar é um geométrico e assim você vai parar depois desses muitos tosses de moedas. Então, a questão é: esse é o ideal? Então, a resposta para esta pergunta está relacionada com o quanto de aleatoriedade lá, está aí nessa variável aleatória.
Da mesma forma, a resposta para esta questão está relacionada com o quanto a aleatoriedade está relacionada, está aí neste emfp, ok. E o que é muito interessante, o que veremos é que a resposta para ambas as perguntas é aproximadamente a mesma. É a entropia da variável aleatória. Por isso, a entropia de fato também mede a aleatoriedade em uma variável aleatória, ok. Então, veremos isso na próxima parte.

Antes de avançarmos para caracterizar a medida de aleatoriedade para uma variável aleatória que basicamente relacionamos com o problema de gerar moedas não biased out de uma variável aleatória ou gerar a variável aleatória a partir de moeda imparcial, ambas as formulações fazem sentido. Antes de abordarmos essa questão, queremos introduzir uma versão aproximada dessa questão.
Então, o objetivo não será mais gerar exatamente uma moeda não tendenciável ou gerar uma variável aleatória com um dado exato de distribuição P, mas gerar uma variável aleatória com uma distribuição próxima a P. Então, isso implora a questão, como se mede distâncias entre distribuições? O que eu quero dizer com dizer que uma distribuição é próxima de P. Então, isso é um pouco de degradação o que eu gostaria de fazer agora é dizer sobre como medimos distâncias entre distribuições.
Por isso, revisaremos este tópico mais tarde, mas é um momento apropriado para primeiro introduzir isso pela primeira vez. Por isso, como você pode notar, provavelmente neste curso, em vez de afirmar quantidades adiantadas o que venho tentando fazer é eu ter tentado primeiro motivar uma questão primeiro usar uma questão motivadora para configurar um problema e então introduzir quantidades como resposta natural a esse problema nesse contexto muito bom (()) (01:39) para medir distâncias entre distribuições é essa quantidade que é chamada de distância total de variação, distância total de variação esta tem muitos nomes.
Ele também é chamado de distância estatística. Em algumas, algumas pessoas chamam de distância estatística, eu diria que a distância estatística é o nome mais popular dessa grandeza em ciência da computação e aprendizado de máquina, a distância de variação total é um nome mais clássico, e é muito fácil definir esta quantidade para distribuições discretas, a saber, pmf. Portanto, isso é algo que vai se encontrar de novo e de novo neste curso, assim como entropia. Este é um dos outros personagens principais deste curso.
A primeira foi entropia, segundo uma que introduzimos hoje é esta distância total de variação d P, Q; d para distância P, Q. Então, é uma distância entre P e Q. Esta notação é, como é definida, é assim é definida como a metade da somatória sobre x, x naquele alfabeto calligráfico x de P x, menos Q x, mod dali, ok. Então, você passa por cima de todas as realizações x e leva P x menos Q x, ou seja, para d P é, está bem definido. Você pode verificar se esta é uma medida razoável de distância, embora não seja muito importante para o nosso tratamento no sentido de que ele satisfaz 3 propriedades.
Se d P, Q é 0, então P x deve ser igual Q x para todos x, portanto P é igual a Q. Assim, os mesmos pontos têm distância 0, ele é não negativo que também é bom então é 0 se e somente se P for igual a Q e ele satisfaça a desigualdade triangular e algo que você pode verificar. Nós vamos voltar para essas propriedades mais tarde. Mas algum teste sanitário rápido assim d P, Q é menor do que igual a d P deixe-nos dizer Q Prime mais d Q prime Q você pode conferir isso, este também. Então, essa é uma noção razoável de uma distância entre distribuições. E satisfaz certas propriedades.
Vou apenas revisar poucas propriedades que são essenciais, que são expressão essencialmente equivalente para isso, d P, Q o que você pode mostrar é na verdade este d P, Q é supremacia sobre todos. Supremum é como o máximo. Por isso, é máxima Supremum é semelhante ao máximo, mas requer alguma definição um pouco mais formal.
É máximo sobre todos os eventos aqui sobre todos os subconjuntos A de x de P A menos Q A. Então, é a diferença máxima de probabilidade entre dois eventos, mas é a diferença máxima entre probabilidades de um evento A em P e Q que é o que d P, Q é. Da simetria isso também é igual ao máximo sobre B de Q, B, menos B A, P B e, portanto, você também pode mostrar que este é igual a sup sobre A, P A menos Q. Você pode colocar um mod aqui porque o máximo será atingido por uma quantidade não negativa. Isso também é verdade ok você pode mostrar isso. Então, eu não estou mostrando essa propriedade, mas pode ser mostrado, de fato, podemos exatamente anotar qual conjunto atinge esse máximo, esta supremacia. Assim, sua supremacia é um max quando ela pode ser alcanada. E este é de fato um max porque pode ser atingido por este conjunto, que eu estou chamando de estrela. É o conjunto daqueles x para os quais P x excede Q x. Esse é aquele que para o qual d P, Q é igual ao supremo.
E similarmente, este sup em particular aqui atingido pelo conjunto B x tal que Q x é maior que P x. Então, esta é uma propriedade que seria útil para nós, eu exortaria você a voltar atrás e estudar essas propriedades cuidadosamente. Isso é algo que você deve relembrar rapidamente ao longo deste curso.
Outra propriedade deste d P, Q é que ela é sempre entre 0 e 1, é 0 se e somente se P for igual a Q e for 1 também pode ser 1, você vê que é P A menos Q A. Então, é sempre menor que igual a 1 porque PA é menor que igual a 1, mas também pode igual a 1. Quando será igual a 1? Isso é interessante. Por isso, a igualdade no lado direito se mantém se e somente se for apoio de P e apoio de Q são dispensados. Então, o que é suporte de um pmf ou suporte de uma distribuição?
É um conjunto de pontos sobre os quais um P de distribuição coloca em massa e é o suporte de Q similarmente um ponto de set em que a distribuição Q coloca massa. Assim, d P, Q é 1 se e somente se estes dois suportes forem dispensados. Portanto, se você tem pensar neste alfabeto x e suponha que é aqui que P coloca massa e é aqui que Q coloca massa, portanto, estes são desunidos, não há um ponto comum entre eles, e neste caso d P, Q será 1. E isso é se e só se for bem. Então, se isso se mantém, então este é 1. Se isso é 1, então este deve ser 2. Você também pode mostrar que isso vai voltar para aquela prova depois.
Por fim, gostaria de destacar que esta definição de d P, Q pode ser facilmente estendida a distribuições contínuas, a uma contínua variáveis aleatórias, distribuições mais gerais, distribuições com densidade. Então, aqui estão os exemplos de suponhamos que sua distribuição tenha densidade é, suponha que duas distribuições P e Q tenham densidades. Então, isso é densidades f e g so densidade de p e densidade de Q. Então, você tem suponha que você tenha essas densidades f e g com relação a esta medida de vida padrão, mas eu não preciso usar essa linguagem de fato. Então, isso é assim quando você pensa em uma variável aleatória contínua, você pode pensar em suas densidades e essas variáveis aleatórias P e Qter densidades f e g com relação à medida do comprimento e então você pode definir d P, Q simplesmente como metade do fx integral menos gx integral sobre x ok, assim como nós tínhamos somatória mais cedo agora você tem integral de densidade.
Por isso, o pmf ganha um lugar com densidade e você tem integração de somatória. Este dois é equivalente à supremacia sobre um PA menos Q A. E agora a igualdade se mantém se e somente se for uma condição semelhante de modo que os conjuntos que atesta a igualdade ela é dada por Uma estrela equivale ao conjunto daqueles x para os quais fx excede gx que é o conjunto que atinge essa igualdade. Então, esse d P, Q é essa distância de variação total é algo que gostaríamos de usar como medida de distância entre distribuições e ele satisfaz várias propriedades.
Por exemplo, está sempre entre 0 e 1 e 1. Por isso, a propriedade importante que vimos nesta parte é esta fórmula que é supremacia sobre todos os APA menos QA. Isso é muito importante. Tais fórmulas serão vistas ao longo deste curso, que levam uma quantidade como esta e relacionadas ao max de alguma outra função, ok.
Por isso, em particular eles úteis porque qualquer um particular A para qualquer particular A, P A menos Q A é menor que d P, Q. E o melhor A este, mantém a igualdade. Essa é aquela que é uma maneira de interpretar tais fórmulas às vezes tais fórmulas são chamadas de variação, são chamadas de fórmula variacional. E isso é que temos esse nome essa distância às vezes também é chamada de distância variacional porque você tem essa forma para essa distância.
O nome de variação total de variação é de fato associado a este formulário. É. Algo relacionado à variação total e que você pode olhar para cima, a razão para este nome mas distância variacional, distância de variação total, distância estatística estas são todas as mesmas coisas, a saber, essa distância, e nós iremos usá-la ao longo deste curso. Veja você na próxima palestra.