Artigos

3.E: Funções de geração (exercícios)


Para alguns desses exercícios, você pode querer usar o miniaplicativo sábio acima, por exemplo 3.1.4, ou seu sistema de álgebra de computador favorito.

Ex 3.1.1 Prove que ({r escolha k} = {r-1 escolha k-1} + {r-1 escolha k} ).

Ex 3.1.2 Mostre que a série Maclaurin para ((x + 1) ^ r ) é ( sum_ {i = 0} ^ infty {r escolha i} x ^ i ).

Ex 3.1.3 Exemplo relativo 3.1.4, mostre que todos os coeficientes começando com (x ^ {16} ) são 180.

Ex 3.1.4 Use uma função geradora para encontrar o número de soluções para ( ds x_1 + x_2 + x_3 + x_4 = 14 ), onde (0 le x_1 le3 ), (2 le x_2 le5 ), (0 le x_3 le5 ), (4 le x_4 le6 ).

Ex 3.1.5 Encontre a função geradora para o número de soluções para ( ds x_1 + x_2 + x_3 + x_4 = k ), onde (0 le x_1 le infty ), (3 le x_2 le infty ), (2 le x_3 le5 ), (1 le x_4 le5 ).

Ex 3.1.6 Encontre uma função geradora para o número de soluções inteiras não negativas para (3x + 2y + 7z = n ).

Ex 3.1.7 Suponha que temos um grande estoque de balões vermelhos, brancos e azuis. Quantos cachos diferentes de 10 balões existem, se cada cacho deve ter pelo menos um balão de cada cor e o número de bolas brancas deve ser par?

Ex 3.1.8 Use funções geradoras para mostrar que todo número inteiro positivo pode ser escrito exatamente de uma maneira como uma soma de potências distintas de 2.

Ex 3.1.9 Suponha que tenhamos um grande suprimento de velas azuis e verdes e uma vela dourada. Quantas coleções de (n ) velas existem nas quais o número de velas azuis é par, o número de velas verdes é qualquer número e o número de velas douradas é no máximo um?

Ex 3.2.1 Encontre o coeficiente de (x ^ 9/9! ) Na função de exemplo 3.2.1. Você pode usar o Sage ou um programa semelhante.

Ex 3.2.2 Encontre uma função geradora exponencial para o número de permutações com repetição de comprimento (n ) do conjunto ( {a, b, c } ), em que há um número ímpar de (a , ) s, um número par de (b , ) s, e um número par de (c , ) s.

Ex 3.2.3 Encontre uma função geradora exponencial para o número de permutações com repetição de comprimento (n ) do conjunto ( {a, b, c } ), em que o número de (a , ) s é par e pelo menos 2, o número de (b , ) s é par e no máximo 6, e o número de (c , ) s é pelo menos 3.

Ex 3.2.4 De quantas maneiras podemos pintar os 10 quartos de um hotel se no máximo três podem ser pintados de vermelho, no máximo 2 pintados de verde, no máximo 1 pintado de branco e qualquer número pode ser pintado de azul ou laranja?

Ex 3.2.5 Lembre-se da seção 1.4 que os números do sino (B_n ) contam todas as partições de ( {1,2, ldots, n } ).

Seja ( ds f (x) = sum_ {n = 0} ^ infty B_n cdot {x ^ n over n!} ), E observe que () f '(x) = sum_ {n = 1} ^ infty B_n {x ^ {n-1} over (n-1)!} = sum_ {n = 0} ^ infty B_ {n + 1} {x ^ {n} sobre n!} = sum_ {n = 0} ^ infty left ( sum_ {k = 0} ^ n {n escolha k} B_ {nk} right) {x ^ {n} sobre n! }, () usando a relação de recorrência 1.4.1 para (B_ {n + 1} ) da seção 1.4. Agora é possível escrever isso como um produto de duas séries infinitas: () f '(x) = left ( sum_ {n = 0} ^ infty B_n cdot {x ^ n over n!} direita) esquerda ( sum_ {n = 0} ^ infty a_n x ^ n direita) = f (x) g (x). () Encontre uma expressão para (a_n ) que torne isso verdadeiro, que lhe dirá o que (g (x) ) é, então resolva a equação diferencial para (f (x) ), o exponencial função geradora para os números de Bell. Da seção 1.4, os primeiros números de Bell são 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437. Você pode verificar sua resposta no Sage.

Ex 3.3.1 Use funções de geração para encontrar (p_ {15} ).

Ex 3.3.2 Encontre a função geradora para o número de partições de um inteiro em partes ímpares distintas. Encontre o número dessas partições de 20.

Ex 3.3.3 Encontre a função geradora para o número de partições de um inteiro em partes pares distintas. Encontre o número dessas partições de 30.

Ex 3.3.4 Encontre o número de partições de 25 em partes ímpares.

Ex 3.3.5 Encontre a função geradora para o número de partições de um inteiro em (k ) partes; ou seja, o coeficiente de (x ^ n ) é o número de partições de (n ) em (k ) partes.

Ex 3.3.6 Complete a linha 8 da tabela para o (p_k (n) ), e verifique se a soma das linhas é 22, como vimos no exemplo 3.3.3.

Ex 3.3.7 Uma partição de (n ) é autoconjugada se seu diagrama de Ferrers for simétrico em torno da diagonal principal, de modo que seu conjugado seja ele mesmo. Mostre que o número de partições auto-conjugadas de (n ) é igual ao número de partições de (n ) em partes ímpares distintas.

Ex 3.4.1 Encontre a função geradora para as soluções para (h_n = 4h_ {n-1} -3h_ {n-2} ), (h_0 = 2 ), (h_1 = 5 ), e use-a para encontrar um fórmula para (h_n ).

Ex 3.4.2 Encontre a função geradora para as soluções para (h_n = 3h_ {n-1} + 4h_ {n-2} ), (h_0 = h_1 = 1 ), e use-a para encontrar uma fórmula para (h_n )

Ex 3.4.3 Encontre a função geradora para as soluções para (h_n = 2h_ {n-1} + 3 ^ n ), (h_0 = 0 ), e use-a para encontrar uma fórmula para (h_n ).

Ex 3.4.4 Encontre a função geradora para as soluções para (h_n = 4h_ {n-2} ), (h_0 = 0 ), (h_1 = 1 ), e use-a para encontrar uma fórmula para (h_n ) . (É fácil descobrir essa fórmula diretamente; o ponto aqui é ver se a abordagem da função geradora fornece a resposta correta.)

Ex 3.4.5 Encontre a função geradora para as soluções para (h_n = h_ {n-1} + h_ {n-2} ), (h_0 = 1 ), (h_1 = 3 ), e use-a para encontrar um fórmula para (h_n ).

Ex 3.4.6 Encontre a função geradora para as soluções para (h_n = 9h_ {n-1} -26h_ {n-2} + 24h_ {n-3} ), (h_0 = 0 ), (h_1 = 1 ) , (h_2 = -1 ), e use-o para encontrar uma fórmula para (h_n ).

Ex 3.4.7 Encontre a função geradora para as soluções para (h_n = 3h_ {n-1} + 4h_ {n-2} ), (h_0 = 0 ), (h_1 = 1 ), e use-a para encontrar um fórmula para (h_n ).

Ex 3.4.8 Encontre uma recursão para o número de maneiras de colocar bandeiras em um mastro de (n ) pé, onde temos bandeiras vermelhas com 2 pés de altura, bandeiras azuis com 1 pé de altura e bandeiras amarelas com 1 pé de altura; as alturas das bandeiras devem somar (n ). Resolva a recursão.

Ex 3.4.9 No problema original de Fibonacci, um fazendeiro começou com um par de coelhos (recém-nascidos) no mês 0. Depois que cada par de coelhos completou um mês de idade, eles produziram outro par a cada mês em perpetuidade. Assim, após 1 mês, ele tinha o par original, após dois meses 2 pares, três meses, 3 pares, quatro meses, 5 pares, etc. O número de pares de coelhos satisfaz (h_n = h_ {n-1} + h_ {n-2} ), (h_0 = h_1 = 1 ). (Observe que isso é um pouco diferente da nossa definição, em que (h_0 = 0 ).)

Suponha, em vez disso, que cada par maduro dê à luz a dois pares de coelhos. A sequência para o número de pares de coelhos agora começa (h_0 = 1 ), (h_1 = 1 ), (h_2 = 3 ), (h_3 = 5 ), (h_4 = 11 ) Configure e resolva uma relação de recorrência para o número de pares de coelhos. Mostre também que a sequência está estatisticamente (h_n = 2h_ {n-1} + (- 1) ^ n ).

Ex 3.5.1 Mostre que () {2n escolha n} - {2n escolha n + 1} = {1 sobre n + 1} {2n escolha n}. ()

Ex 3.5.2 Encontre uma expressão simples (f (n) ) de forma que (C_ {n + 1} = f (n) C_n ). Use para calcular (C_1, ldots, C_6 ) de (C_0 ).

Ex 3.5.3 Mostre que se (A_n ) é o número de sequências de parênteses de comprimento devidamente correspondidas (2n ), então () A_n = sum_ {i = 0} ^ {n-1} A_iA_ {ni-1 } () Faça isso no mesmo estilo que usamos para o número de árvores binárias enraizadas: Dadas todas as sequências de comprimento menor, explique como combiná-las para produzir as sequências de comprimento (2n ), de tal forma que a soma conta claramente o número de sequências. Dica: prove o seguinte lema: Se (s ) é uma sequência de parênteses de comprimento devidamente combinada (2n ), (s ) pode ser escrito exclusivamente na forma ((s_1) s_2 ), onde (s_1 ) e (s_2 ) são sequências de parênteses com correspondência adequada cujos comprimentos somam (2n-2 ). Por exemplo, ((()) () = ([()]) [()] ) e (() (()) = ([,]) [(())] ), com as sequências (s_1 ) e (s_2 ) indicadas por ([,] ). Observe que (s_1 ) e (s_2 ) podem ser sequências vazias, com comprimento 0.

Ex 3.5.4 Considere uma "escada" como mostrado abaixo. Um caminho de (A ) para (B ) consiste em uma sequência de arestas começando em (A ), terminando em (B ), e prosseguindo apenas para cima ou à direita; todos os caminhos têm comprimento 6. Um desses caminhos é indicado por setas. A escada mostrada é uma escada ") 3 vezes 3 ) ''. Quantos caminhos existem em uma (n times n ) escada?

Ex 3.5.5 Um polígono convexo com (n ge3 ) lados pode ser dividido em triângulos inserindo (n-3 ) diagonais sem interseção. De quantas maneiras diferentes isso pode ser feito? As possibilidades para (n = 5 ) são mostradas.

Ex 3.5.6 UMA partição de um conjunto (S ) é uma coleção de subconjuntos não vazios (A_i subseteq S ), (1 le i le k ) (o partes da partição), de modo que ( bigcup_ {i = 1} ^ k A_i = S ) e para todo (i not = j ), (A_i cap A_j = emptyset ). Por exemplo, uma partição de ( {1,2,3,4,5 } ) é ( { {1,3 } ), ( {4 } ), ( {2,5 } } ).

Suponha que os inteiros (1,2, ldots, n ) sejam organizados em um círculo, na ordem ao redor do círculo. Uma partição de ( {1,2, ldots, n } ) é um partição não cruzada se satisfaz esta propriedade adicional: Se (w ) e (x ) estão em alguma parte (A_i ), e (y ) e (z ) estão em uma parte diferente (A_j ), então a linha que une (w ) com (x ) não cruza a linha que une (y ) com (z ). A partição acima, ( {1,3 } ), ( {4 } ), ( {2,5 } ), não é uma partição não cruzada, como a linha 1–3 cruza a linha 2–5.

Encontre o número de partições não cruzadas de ( {1,2, ldots, n } ).

Lembre-se da seção 1.4 que os números de Bell contam todas as partições de ( {1,2, ldots, n } ). Portanto, este exercício nos fornece um limite inferior para o número total de partições.

Ex 3.5.7 Considere um conjunto de (2n ) pessoas sentadas ao redor de uma mesa. De quantas maneiras podemos fazer com que cada pessoa aperte a mão de outra pessoa à mesa de forma que não haja dois apertos de mão se cruzando?


No caso univariado, a função geradora de momento, (M_X (t) ), de uma variável aleatória X é dada por:

para todos os valores de (t ) para os quais existe a expectativa.

As funções geradoras de momento podem ser definidas para variáveis ​​aleatórias discretas e contínuas. Para variáveis ​​aleatórias discretas, a função geradora de momento é definida como:

e para o variáveis ​​aleatórias contínuas, a função geradora de momento é dada por:

Se (Y = Ax + b ), então pode ser mostrado que:


Objetivos

  • Para aprender a definição de uma função geradora de momento.
  • Para encontrar a função geradora de momento de uma variável aleatória binomial.
  • Aprender como usar uma função geradora de momento para encontrar a média e a variância de uma variável aleatória.
  • Para aprender como usar uma função geradora de momento para identificar qual função de massa de probabilidade uma variável aleatória (X ) segue.
  • Para entender as etapas envolvidas em cada uma das provas da lição.
  • Ser capaz de aplicar os métodos aprendidos na lição a novos problemas.

3.8: Funções Geradoras de Momento (MGFs) para Variáveis ​​Aleatórias Discretas

  • Contribuição de Kristin Kuter
  • Professor Associado (Matemática Ciência da Computação) no Saint Mary's College

O valor esperado e a variância de uma variável aleatória são, na verdade, casos especiais de uma classe mais geral de características numéricas para variáveis ​​aleatórias dadas por momentos.

Definição ( PageIndex )

O r º momentode uma variável aleatória (X ) é dado por
$ text[X ^ r]. Notag $
O r º momento central de uma variável aleatória (X ) é dado por
$ text[(X- mu) ^ r], notag $
onde ( mu = text[X] ).

Observe que o valor esperado de uma variável aleatória é dada pelo primeiro momento, ou seja, quando (r = 1 ). Também o variância de uma variável aleatória é dado o segundo momento central.

Tal como acontece com o valor esperado e a variância, os momentos de uma variável aleatória são usados ​​para caracterizar a distribuição da variável aleatória e para comparar a distribuição com a de outras variáveis ​​aleatórias. Os momentos podem ser calculados diretamente a partir da definição, mas, mesmo para valores moderados de (r ), essa abordagem se torna complicada. A próxima definição e teorema fornecem uma maneira mais fácil de gerar momentos.

Definição ( PageIndex )

O função geradora de momento (mgf) de uma variável aleatória (X ) é dado por
$ M_X (t) = E [e ^], quad text t in mathbb. notag $

Teorema ( PageIndex )

Se a variável aleatória (X ) tiver mgf (M_X (t) ), então
$ M ^ <(r)> _ X (0) = frac left [M_X (t) right] _ = text[X ^ r]. Notag $
Em outras palavras, o (r ^ < text> ) a derivada do mgf avaliada em (t = 0 ) dá o valor de (r ^ < text> ) momento.

O teorema 3.8.1 nos diz como derivar o mgf de uma variável aleatória, uma vez que o mgf é dado tomando o valor esperado de uma função aplicada à variável aleatória:
$ M_X (t) = E [e ^] = sum_i e ^ cdot p (x_i) notag $
Podemos agora derivar o primeiro momento da distribuição de Poisson, ou seja, derivar o fato que mencionamos na Seção 3.6, mas deixado como um exercício, que o valor esperado é dado pelo parâmetro ( lambda ). Também encontramos a variação.

Exemplo ( PageIndex )

Deixe (X sim text( lambda) ). Então, o pmf de (X ) é dado por
$ p (x) = frac lambda ^ x>, quad text x = 0,1,2, ldots. notag $
Antes de derivarmos o mgf para (X ), lembramos do cálculo a expansão da série de Taylor da função exponencial (e ^ y ):
$ e ^ y = sum_^ < infty> frac. notag $
Usando este fato, encontramos
$ M_X (t) = text[e ^] = sum ^ < infty> _ e ^ cdot frac lambda ^ x> = e ^ <- lambda> sum ^ < infty> _ frac <(e ^ t lambda) ^ x> = e ^ <- lambda> e ^ = e ^ < lambda (e ^ t - 1)>. notag $
Agora pegamos a primeira e a segunda derivadas de (M_X (t) ). Lembre-se de que estamos diferenciando em relação a (t ):
começar
M'_X (t) & amp = frac

left [e ^ < lambda (e ^ t - 1)> right] = lambda e ^ te ^ < lambda (e ^ t - 1)>
M '' _ X (t) & amp = frac
left [ lambda e ^ te ^ < lambda (e ^ t - 1)> right] = lambda e ^ te ^ < lambda (e ^ t - 1)> + lambda ^ 2 e ^ <2t > e ^ < lambda (e ^ t - 1)>
fim
Em seguida, avaliamos as derivadas em (t = 0 ) para encontrar o primeiro e o segundo momentos de (X ):
começar
exto[X] = M'_X (0) & amp = lambda e ^ 0e ^ < lambda (e ^ 0 - 1)> = lambda
exto[X ^ 2] = M '' _ X (0) & amp = lambda e ^ 0e ^ < lambda (e ^ 0 - 1)> + lambda ^ 2 e ^ <0> e ^ < lambda (e ^ 0 - 1)> = lambda + lambda ^ 2
fim
Finalmente, para encontrar a variância, usamos a fórmula alternativa:
$ text(X) = texto[X ^ 2] - left ( text[X] right) ^ 2 = lambda + lambda ^ 2 - lambda ^ 2 = lambda. Notag $
Assim, mostramos que tanto a média quanto a variância para a distribuição de Poisson (( lambda) ) são dadas pelo parâmetro ( lambda ).

Observe que o mgf de uma variável aleatória é um função de (t ). A principal aplicação dos mgf's é encontrar os momentos de uma variável aleatória, como o exemplo anterior demonstrou. Existem mais propriedades de mgf's que nos permitem encontrar momentos para funções de variáveis ​​aleatórias.

Teorema ( PageIndex )

Seja (X ) uma variável aleatória com mgf (M_X (t) ), e seja (a, b ) constantes. Se a variável aleatória (Y = aX + b ), então o mgf de (Y ) é dado por
$ M_Y (t) = e ^M_X (at). Notag $

Teorema ( PageIndex )

Se (X_1, ldots, X_n ) são variáveis ​​aleatórias independentes com mgf's (M_(t), ldots, M_(t) ), respectivamente, então o mgf da variável aleatória (Y = X_1 + cdots + X_n ) é dado por
$ M_Y (t) = M_(t) cdots M_(t). notag $

Lembre-se de que uma variável aleatória distribuída binomialmente pode ser escrita como uma soma de variáveis ​​aleatórias de Bernoulli independentes. Usamos isso e o Teorema 3.8.3 para derivar a média e a variância para uma distribuição binomial. Primeiro, encontramos a média e a variância de uma distribuição de Bernoulli.

Exemplo ( PageIndex )

Lembre-se de que (X ) tem uma distribuição Bernoulli ((p) ) se for atribuído o valor de 1 com probabilidade (p ) e o valor de 0 com probabilidade (1-p ). Assim, o pmf de (X ) é dado por
$ p (x) = left < begin
1-p, & amp text x = 0
p, & amp text x = 1
fim right. notag $
A fim de encontrar a média e a variância de (X ), primeiro derivamos o mgf:
$ M_X (t) = text[e ^] = e ^(1-p) + e ^p = 1 - p + e ^ tp. notag $
Agora diferenciamos (M_X (t) ) em relação a (t ):
começar
M'_X (t) & amp = frac

left [1 - p + e ^ tp right] = e ^ tp
M '' _ X (t) & amp = frac
left [e ^ tp right] = e ^ tp
fim
Em seguida, avaliamos as derivadas em (t = 0 ) para encontrar o primeiro e o segundo momentos:
$ M'_X (0) = M '' _ X (0) = e ^ 0p = p. Notag $
Assim, o valor esperado de (X ) é ( text[X] = p ). Finalmente, usamos a fórmula alternativa para calcular a variância:
$ text(X) = texto[X ^ 2] - left ( text[X] right) ^ 2 = p - p ^ 2 = p (1-p). Notag $

Exemplo ( PageIndex )

Deixe (X sim text(n, p) ). Se (X_1, ldots, X_n ) denotam (n ) variáveis ​​aleatórias Bernoulli ((p) ) independentes, então podemos escrever
$ X = X_1 + cdots + X_n. Notag $
No Exemplo 3.8.2, encontramos o mgf para uma variável aleatória Bernoulli ((p) ). Assim, temos
$ M_(t) = 1 - p + e ^ tp, quad text i = 1, ldots, n. notag $
Usando o Teorema 3.8.3, derivamos o mgf para (X ):
$ M_X (t) = M_(t) cdots M_(t) = (1-p + e ^ tp) cdots (1-p + e ^ tp) = (1-p + e ^ tp) ^ n. notag $
Agora podemos usar o mgf de (X ) para encontrar os momentos:
começar
M'_X (t) & amp = frac

left [(1-p + e ^ tp) ^ n right] = n (1-p + e ^ tp) ^e ^ tp
& amp Rightarrow M'_X (0) = np
M '' _ X (t) & amp = frac
left [n (1-p + e ^ tp) ^e ^ tp right] = n (n-1) (1-p + e ^ tp) ^(e ^ tp) ^ 2 + n (1-p + e ^ tp) ^e ^ tp
& amp Rightarrow M '' _ X (0) = n (n-1) p ^ 2 + np
fim
Assim, o valor esperado de (X ) é ( text[X] = np ), e a variação é
$ text(X) = texto[X ^ 2] - ( text[X]) ^ 2 = n (n-1) p ^ 2 + np - (np) ^ 2 = np (1-p). Notag $


Terminamos com uma propriedade final de mgf's que se relaciona com a comparação da distribuição de variáveis ​​aleatórias.

Teorema ( PageIndex )

O mgf (M_X (t) ) da variável aleatória (X ) determina exclusivamente a distribuição de probabilidade de (X ). Em outras palavras, se as variáveis ​​aleatórias (X ) e (Y ) têm o mesmo mgf, (M_X (t) = M_Y (t) ), então (X ) e (Y ) têm a mesma distribuição de probabilidade.

Exercício ( PageIndex )

Suponha que a variável aleatória (X ) tenha o seguinte mgf:
$ M_X (t) = left (0.85 + 0.15e ^ t right) ^ <33> notag $ Qual é a distribuição de (X )?

Dica Use o Teorema 3.8.4 e veja o Exemplo 3.8.3. Responder

Encontramos no Exemplo 3.8.3 que o mgf para uma distribuição binomial é
$ M_X (t) = (1-p + e ^ tp) ^ n, notag $ que é o mgf dado com (p = 0,15 ) e (n = 33 ). Assim, (X sim text(33, 0.15)).


Resumo

Fundo

Estudos anteriores mostraram que o exercício multicomponente melhorou as funções físicas e cognitivas. Este estudo teve como objetivo investigar os efeitos de um exercício multicomponente no desempenho de dupla tarefa e função executiva e demonstrar a relação entre a melhoria no desempenho de dupla tarefa e o aprimoramento da função executiva em idosos.

Métodos

Um total de 27 pessoas completaram a intervenção, sendo 16 no grupo experimental e 11 no grupo controle. O exercício multicomponente de 12 semanas durou 1 hora por dia e 3 dias por semana. O desempenho da marcha dos participantes e # x27 foi avaliado em condições de dupla tarefa e a função executiva foi examinada tanto no pré quanto no pós-intervenção.

Resultados

Os resultados mostraram efeitos de interação significativos de tempo x grupo em todos os parâmetros de marcha selecionados em ambas as condições de tarefa dupla e na Entrevista Executiva. Comparado com o grupo de controle, o grupo experimental mostrou maiores melhorias na maioria das medidas após a intervenção. O desempenho aprimorado de dupla tarefa foi correlacionado com o aprimoramento da função executiva (r = 0,46-0,75).

Conclusão

Nossos resultados sugeriram que um exercício multicomponente afeta positivamente o desempenho de dupla tarefa e a função executiva em idosos.


Ensaios Relacionados

A operação terrestre unificada é o conceito operacional do Exército, executada por meio de ações decisivas e orientada pelo comando da missão. A estrutura do Exército para o exercício.

Cabeça de corrida: MID-TERM 1 MID-TERM.

O comandante pode solicitar várias áreas de estudo, tais como: hostil, composição de força amistosa, ambiente operacional ou a estrutura da população civil.

O país que se sentia o chefe de todos os países do mundo. American Army é um dos maiores ramos das forças armadas dos EUA e executa lan.

A Metodologia de Projeto do Exército (ADM), desenvolvida como parte da doutrina do Exército na sequência de campanhas fracassadas no Iraque e no Afeganistão, fornece uma abordagem para comunicação.

Em certo sentido, este documento é o "boletim" que apresenta as "notas" do sargento para o período por meio de várias verificações de bloco, marcadores e comentários narrativos.

O Gerenciamento de Prontidão de Pessoal engloba uma série de coisas para determinar as capacidades de combate atuais, projetar requisitos futuros, bem como avaliar.

Uma Visão de Sucesso: General Petraeus e a publicação de referência de doutrina do Exército da Cidade de Mosul (ADRP) 6-0 descreve o comando de missão como “o exercício de aut.

O Exército constrói agilidade e flexibilidade com uma Brigada Combat Team (BCT) rotativa na Europa, estoques pré-posicionados e uso operacional do Exército Nacional.

Em seu livro Transforming Leadership: From Vision to Results, o autor John D. Adams identifica a importância da liderança direta “Seguidores passivos, alth.


3.E: Funções de geração (exercícios)

Para ver uma revisão de como iniciar o R, olhe no início do Lab1
Lab1 http://www-stat.stanford.edu/ epurdom / RLab.htm

Os exemplos a seguir demonstram como calcular o valor da função de distribuição cumulativa em (ou a probabilidade à esquerda) de um determinado número.

Exercício: Calcule as seguintes probabilidades: 1. Probabilidade de que uma variável aleatória normal com média 22 e variância 25 (i) esteja entre 16,2 e 27,5
pnorm (27.5,22, sd = 5) -pnorm (16.2,22, sd = 5)
[1] 0,7413095 (ii) é maior do que 29 1-pnorm (29,22, sd = 5)
[1] 0,08075666 (iii) é menor que 17 pnorm (17,22, sd = 5)
[1] 0,1586553 (iv) é menor que 15 ou maior que 25 pnorm (15,22, sd = 5) + 1-pnorm (25,22, sd = 5)
[1] 0,3550098 2. Probabilidade de que em 60 lances de uma moeda justa a cara apareça (i) 20,25 ou 30 vezes
soma (dbinom (c (20,25,30), 60, prob = 0,5))
[1] 0.1512435
(ii) menos de 20 vezes
pbinom (19,60, prob = 0,5)
[1] 0,0031088 (iii) entre 20 e 30 vezes pbinom (30,60, prob = 0,5) -pbinom (20,60, prob = 0,5)
[1] 0,5445444 3. Uma variável aleatória X tem distribuição de Poisson com média 7. Encontre a probabilidade de que (i) X seja menor que 5 menor ou igual é:
& gt ppois (5,7)
[1]0.3007083
menos do que é
& gt ppois (4,7)
[1] 0,1729916 (ii) X é maior que 10 (estritamente)
& gt 1-ppois (10,7) [1] 0,0985208 (iii) X está entre 4 e 16 & gt ppois (16,7) -ppois (3,7) [1] 0,9172764

Os exemplos a seguir mostram como comum os quantis de algumas distribuições comuns para uma determinada probabilidade (ou um número entre 0 e 1).

Os exemplos a seguir ilustram como gerar amostras aleatórias de algumas das distribuições de probabilidade bem conhecidas.

A primeira amostra é da distribuição e a próxima da distribuição.

Exercício (avançado): Gere 500 amostras da distribuição de Student com 5 graus de liberdade e plote o jogo histórico. (Nota: a distribuição será abordada em aula). A função correspondente é rt. hist (rt (500,5), 40)

    Traçando a função de densidade de probabilidade (pdf) de uma distribuição normal:

** Observe a distinção entre as distrubções contínuas (Normal) e as discretas (Binomial).

Exercício: Plote as funções de probabilidade de massa para a distribuição de Poisson com média 4,5 e 12 respectivamente. Você vê alguma semelhança entre esses gráficos e qualquer um dos gráficos acima? Se sim, você consegue adivinhar por quê?

Exercício: recrie as probabilidades que o professor Holmes fez na aula (Bin (5, .4)) [Você pode fazer isso em 1 comando!] Como você obteria as contagens esperadas?

R tem duas funções diferentes que podem ser usadas para gerar um gráfico Q-Q. Use a função qqnorm para traçar os quantis da amostra contra os quantis teóricos (população) da variável aleatória normal padrão.

Nota: O desvio sistemático de pontos da linha Q-Q (a linha reta vermelha nos gráficos) indicaria algum tipo de desvio da normalidade para os pontos de amostra.

Uso da função qqplot para traçar quantis de amostra para uma amostra contra os quantis de amostra de outra amostra

Exercício: Gere 100 amostras da distribuição de Student com 4 graus de liberdade e gere o qqplot para esta amostra.
qqnorm (rt (100, df = 4)) Gere outra amostra do mesmo tamanho, mas agora a partir de uma distribuição com 30 graus de liberdade e gere o gráfico q-q. Você vê alguma diferença?
qqnorm (rt (100, df = 30))

Deve ser evidente para você que a distribuição t está muito longe do normal e os 30 graus de liberdade t são indistinguíveis do Normal.
Susan Holmes 31/10/2004


4.3: Análise e análise de árvores

  • Contribuição de Carol Critchlow e David J. Eck
  • Professores (Matemática e Ciências da Computação) na Hobart and William Smith Colleges

Suponha que G seja uma gramática para a linguagem L. Ou seja, L = L (G). A gramática G pode ser usada para gerar strings na linguagem L. Na prática, porém, muitas vezes começamos com uma string que pode ou não estar em L, e o problema é determinar se a string está na linguagem e, se então, como ela pode ser gerada por G. O objetivo é encontrar uma derivação da string, usando as regras de produção da gramática, ou mostrar que tal derivação não existe. Isso é conhecido como análise da string. Quando a string é um programa de computador ou uma frase em linguagem natural, análise a string é uma etapa essencial para determinar seu significado.

Como um exemplo que usaremos ao longo desta seção, considere a linguagem que consiste em expressões aritméticas contendo parênteses, os operadores binários + e & lowast e as variáveis ​​x, y e z. Strings neste idioma incluem x, x + y & lowastz e ((x + y) & lowasty) + z & lowastz. Aqui está uma gramática livre de contexto que gera esta linguagem:

(E longrightarrow E + E )
(E longrightarrow E * E )
(E longrightarrow (E) )
(E longrightarrow x )
(E longrightarrow y )
(E longrightarrow z )

Chame a gramática descrita por estas regras de produção (G_ <1>. ) A gramática (G_ <1> ) diz que x, y e z são expressões e que você pode fazer novas expressões adicionando duas expressões, multiplicando duas expressões e colocando uma expressão entre parênteses. (Posteriormente, examinaremos outras gramáticas para as mesmas linguagens que revelaram ter certas vantagens sobre (G_ <1>.) )

Considere a string x + y & lowast z. Para mostrar que esta string está na linguagem (L left (G_ <1> right), ) podemos exibir uma derivação da string a partir do símbolo inicial (E ) Por exemplo:

Esta derivação mostra que a string x + y & lowastz está de fato em L (G1). Agora, esta string tem muitas outras derivações. Em cada etapa da derivação, pode haver muita liberdade sobre a próxima regra a ser aplicada na gramática. Parte dessa liberdade claramente não é muito significativa. Quando nos deparamos com a string E + E & lowast E no exemplo acima, a ordem em que substituímos E & rsquos pelas variáveis ​​x, y e z não importa muito. Para eliminar um pouco dessa liberdade sem sentido, poderíamos concordar que, em cada etapa de uma derivação, o símbolo não terminal que é substituído é o símbolo não terminal mais à esquerda na string. Uma derivação em que isso é verdadeiro é chamada de derivação esquerda. Os seguintes derivação esquerda da string x + y & lowastz usa as mesmas regras de produção da derivação anterior, mas as aplica em uma ordem diferente:

Não deve ser muito difícil se convencer de que qualquer string que tenha uma derivação tem uma derivação à esquerda (que pode ser obtida alterando a ordem em que as regras de produção são aplicadas).

Vimos que a mesma string pode ter várias derivações diferentes. Podemos perguntar se ele pode ter várias derivações diferentes à esquerda. A resposta é que depende da gramática. Uma gramática livre de contexto (G ) é considerada ambíguo se houver uma string (w in L (G) ) tal que (w ) tenha mais de uma derivação à esquerda de acordo com a gramática G.

Nosso exemplo de gramática (G_ <1> ) é ambíguo. Na verdade, além da derivação esquerda fornecida acima, a string x + y & lowastz tem a derivação esquerda alternativa

(começar E & amp Longrightarrow E * E & amp Longrightarrow E + E * E & amp Longrightarrow x + E * E & amp Longrightarrow x + y * E & amp Longrightarrow x + y * z end)

Nesta derivação à esquerda da string x + y & lowast z, a primeira regra de produção aplicada é (E longrightarrow E * E. ) A primeira (E ) no lado direito eventualmente produz & ldquox + y & rdquo enquanto o segundo produz & ldquoz & rdquo. Na derivação esquerda anterior, a primeira regra de produção aplicada foi (E longrightarrow E + E, ) com o primeiro (E ) à direita produzindo & ldquox & rdquo e o segundo E produzindo & ldquoy & lowast z & rdquo. Se pensarmos em termos de expressões aritméticas, as duas derivações à esquerda levam a duas interpretações diferentes da expressão x + y & lowast z. Em uma interpretação, o x + y é uma unidade que é multiplicada por z. Na segunda interpretação, o y & lowast z é uma unidade que é adicionada a x. A segunda interpretação é a correta de acordo com as regras usuais da aritmética. No entanto, a gramática permite qualquer interpretação. A ambigüidade da gramática permite que a string seja analisada de duas maneiras essencialmente diferentes, e apenas uma das análises é consistente com o significado da string. Claro, a gramática do inglês também é ambígua. Em um exemplo famoso, é impossível dizer se um acampamento & ldquopretty girls & rsquo & rdquo pretende descrever um acampamento bonito para meninas ou um acampamento para meninas bonitas.

Ao lidar com linguagens artificiais, como linguagens de programação, é melhor evitar ambiguidades. A gramática (G_ <1> ) está perfeitamente correta porque gera o conjunto correto de strings, mas em uma situação prática onde estamos interessados ​​no significado das strings, (G_ <1> ) não é o gramática certa para o trabalho. Existem outras gramáticas que geram o mesmo idioma que (G_ <1>. ) Algumas delas são gramáticas inequívocas que refletem melhor o significado das strings no idioma. Por exemplo, o idioma (L left (G_ <1> right) ) também é gerado pela gramática BNF

Esta gramática pode ser traduzida em uma gramática livre de contexto padrão, que chamarei de (G_ <2>: )

(E longrightarrow T A )
(A longrightarrow + T A )
(A longrightarrow varepsilon )

(T longrightarrow F B )
(B longrightarrow * F B )
(B longrightarrow varepsilon )

(F longrightarrow (E) )
(F longrightarrow x )
(F longrightarrow y )
(F longrightarrow z )

A linguagem gerada por (G_ <2> ) consiste em todas as expressões aritméticas legais compostas por parênteses, os operadores + e & menos, e as variáveis ​​x, y e z. Ou seja, (L left (G_ <2> right) = L left (G_ <1> right). ) No entanto, (G_ <2> ) é uma gramática inequívoca. Considere, por exemplo, a string (x + y * z. ) Usando a gramática (G_ <2>, ) a única derivação à esquerda para esta string é:

( Longrightarrow F B A )
( Longrightarrow x B A )
( Longrightarrow x A )
( Longrightarrow x + T A )

( Longrightarrow x + F B A )
( Longrightarrow x + y B A )
( Longrightarrow x + y * F B A )
( Longrightarrow x + y * z B A )
( Longrightarrow x + y * z A )
( Longrightarrow x + y * z )

Não há escolha sobre o primeiro passo nesta derivação, uma vez que a única regra de produção com E no lado esquerdo é (E longrightarrow T A ). esde a única regra de produção com E no lado esquerdo é E & menos & rarr TA. Da mesma forma, a segunda etapa é forçada pelo fato de que há apenas uma regra para reescrever aT. Na terceira etapa, devemos substituir um F. Existem quatro maneiras de reescrever F, mas apenas uma maneira de produzir o x que começa a string x + y & lowast z, então aplicamos a regra (F longrightarrow x. ) Agora, temos que decidir o que fazer com o (B ) em (x BA. ) Existem duas regras para reescrever (B, B longrightarrow * FB ) e (B longrightarrow varejpsilon ). No entanto, a primeira dessas regras introduz um não terminal, & lowast, que não corresponde à string que estamos tentando analisar. Portanto, a única escolha é aplicar a regra de produção (B longrightarrow varepsilon ). In the next step of the derivation, we must apply the rule (A longrightarrow+T A) in order to account for the (+) in the string x + y &lowast z. Similarly, each of the remaining steps in the left derivation is forced.

The fact that (G_<2>) is an unambiguous grammar means that at each step in a left derivation for a string w, there is only one production rule that can be applied which will lead ultimately to a correct derivation of w. However, (G_<2>) actually satisfies a much stronger property: at each step in the left derivation of w, we can tell which production rule has to be applied by looking ahead at the next symbol in (w .) We say that (G_<2>) is an (L L(1)) grammar. (This notation means that we can read a string from Left to right and construct a Left derivation of the string by looking ahead at most 1 character in the string.) Given an LL(1) grammar for a language, it is fairly straightforward to write a computer program that can parse strings in that language. If the language is a programming language, then parsing is one of the essential steps in translating a computer program into machine language. LL(1) grammars and parsing programs that use them are often studied in courses in programming languages and the theory of compilers.

Not every unambiguous context-free grammar is an LL(1) grammar. Consider, for example, the following grammar, which I will call (G_<3>) :

(E longrightarrow E+T)
(E longrightarrow T)
(T longrightarrow T * F)
(T longrightarrow F)
(F longrightarrow(E))
(F longrightarrow x)
(F longrightarrow y)
(F longrightarrow z)

This grammar generates the same language as (G_<1>) and (G_<2>,) and it is unambiguous. However, it is not possible to construct a left derivation for a string according to the grammar (G_<3>) by looking ahead one character in the string at each step. The first step in any left derivation must be either (E Longrightarrow E+T) or (E Rightarrow T .) But how can we decide which of these is the correct first step? Consider the strings (x+y)&lowastz and (x+y)&lowastz+z&lowastx, which are both in the language (Lleft(G_<3> ight) .) For the string ((x+y) * z,) the first step in a left derivation must be (E Longrightarrow T,) while the first step in a left derivation of ((x+y) * z+z * x) must be (E Longrightarrow E+T .) However, the first seven characters of the strings are identical, so clearly looking even seven characters ahead is not enough to tell us which production rule to apply. In fact, similar examples show that looking ahead any given finite number of characters is not enough.

However, there is an alternative parsing procedure that will work for (G_<3>), This alternative method of parsing a string produces a right derivationof the string, that is, a derivation in which at each step, the non-terminal symbol that is replaced is the rightmost non-terminal symbol in the string. Here, for example, is a right derivation of the string (x + y) &lowast z according to the grammar (G_ <3>:)

(Longrightarrow T * F)
(Longrightarrow T * z)
(Longrightarrow F * z)
(Longrightarrow(E) * z)
(Longrightarrow(E+T) * z)
(Longrightarrow(E+T) * z)
(Longrightarrow(F+F) * z)
(Longrightarrow(F+y) * z)
(Longrightarrow(x+y) * z)

The parsing method that produces this right derivation produces it from &ldquobottom to top.&rdquo That is, it begins with the string (x + y) &lowast z and works backward to the start symbol E, generating the steps of the right derivation in reverse order. The method works because (G_<3>) is what is called an (L R(1)) grammar. That is, roughly, it is possible to read a string from Left to right and produce a Right derivation of the string, by looking ahead at most 1 symbol at each step. Although LL(1) grammars are easier for people to work with, LR(1) grammars turn out to be very suitable for machine processing, and they are used as the basis for the parsing process in many compilers.

LR(1) parsing uses a shift/reduce algorithm. Imagine a cursor or current position that moves through the string that is being parsed. We can visualize the cursor as a vertical bar, so for the string (x + y) &lowast z, we start with the configuration |(x + y) &lowast z. A shift operation simply moves the cursor one symbol to the right. For example, a shift operation would convert |(x + y) &lowast z to (|x + y) &lowast z, and a second shift operation would convert that to (x| + y) &lowast z. In a reduce operation, one or more symbols immediately to the left of the cursor are recognized as the right-hand side of one of the production rules in the grammar. These symbols are removed and replaced by the left-hand side of the production rule. For example, in the configuration (x| + y) &lowast z, the x to the left of the cursor is the right-hand side of the production rule (F longrightarrow x,) so we can apply a reduce operation corresponds to the last step in the right derivation of the string, ((F+y) * z Longrightarrow(x+y) * z .) Now the (F) can be recognized as the right-hand side of the production rule (T longrightarrow F,) so we can replace the (F) with (T,) giving (T|+y)&lowastz. This corresponds to the next-to-last step in the right derivation, ((T+y) * z Longrightarrow(F+y) * z).

At this point, we have the configuration (T | + y) &lowast z. The T could be the right-hand side of the production rule (E longrightarrow T .) However, it could also conceivably come from the rule (T longrightarrow T * F .) How do we know whether to reducetheT toEatthispointortowaitfora&lowastF tocomealongsothatwe can reduce T &lowast F ? We can decide by looking ahead at the next character after the cursor. Since this character is a + rather than a &lowast, we should choose the reduce operation that replaces T with E, giving (E| + y) &lowast z. What makes (G_<3>) an LR(1) grammar is the fact that we can always decide what operation to apply by looking ahead at most one symbol past the cursor.

After a few more shift and reduce operations, the configuration becomes (E)| &lowast z, which we can reduce to T | &lowast z by applying the production rules (F longrightarrow(E)) and (T longrightarrow F .) Now, faced with (T | * z,) we must once again decide between a shift operation and a reduce operation that applies the rule (E longrightarrow T .) In this case, since the next character is a * rather than a (+) we apply the shift operation, giving T &lowast|z. From there we get, in succession,T &lowast z|, T &lowast F |, T |, and finally E|. At this point, we have reduced the entire string (x + y) &lowast z to the start symbol of the grammar. The very last step, the reduction of T to E corresponds to the first step of the right derivation, (E Longrightarrow T).

In summary, LR(1) parsing transforms a string into the start symbol of the grammar by a sequence of shift and reduce operations. Each reduce operation corresponds to a step in a right derivation of the string, and these steps are generated in reverse order. Because the steps in the derivation are generated from &ldquobottom to top,&rdquo LR(1) parsing is a type of bottom-up parsing. LL(1) parsing, on the other hand, generates the steps in a left derivation from &ldquotop to bottom&rdquo and so is a type of top-down parsing.

Although the language generated by a context-free grammar is defined in terms of derivations, there is another way of presenting the generation of a string that is often more useful. UMA parse tree displays the generation of a string from the start symbol of a grammar as a two dimensional diagram. Here are two parse trees that show two derivations of the string x+y*z ac- cording to the grammar (G_<1>), which was given at the beginning of this section:

A parse tree is made up of terminal and non-terminal symbols, connected by lines. The start symbol is at the top, or &ldquoroot,&rdquo of the tree. Terminal symbols are at the lowest level, or &ldquoleaves,&rdquo of the tree. (For some reason, computer scientists traditionally draw trees with leaves at the bottom and root at the top.) A production rule (A longrightarrow w) is represented in a parse tree by the symbol A lying above all the symbols in w, with a line joining A to each of the symbols in w. For example, in the left parse tree above, the root, E, is connected to the symbols E, +, and E, and this corresponds to an application of the production rule (E longrightarrow E+E).It is customary to draw a parse tree with the string of non-terminals in a row across the bottom, and with the rest of the tree built on top of that base. Thus, the two parse trees shown above might be drawn as:

Given any derivation of a string, it is possible to construct a parse tree that shows each of the steps in that derivation. However, two different derivations can give rise to the same parse tree, since the parse tree does not show the order in which production rules are applied. For example, the parse tree on the left, above, does not show whether the production rule (E longrightarrow x) is applied before or after the production rule (E longrightarrow y .) However, if we restrict our attention to left derivations, then we find that each parse tree corresponds to a unique left derivation and vice versa. I will state this fact as a theorem, without proof. A similar result holds for right derivations.

Let G be a context-free grammar. There is a one-to-one correspondence between parse trees and left derivations based on the grammar G.

Based on this theorem, we can say that a context-free grammar G is ambiguous if and only if there is a string (w in L(G)) which has two parse trees.

1. Show that each of the following grammars is ambiguous by finding a string that has two left derivations according to the grammar:

a) (S longrightarrow S S)
(S longrightarrow a S b)
(S longrightarrow b S a)
(S longrightarrow varepsilon)

b) (S longrightarrow A S b)
(S longrightarrow varepsilon)
(A longrightarrow a A)
(A longrightarrow a)

2. Consider the string z+(x+y)&lowastx. Find a left derivation of this string according to each of the grammars (G_<1>, G_<2>,) and (G_<3>,) as given in this section.

  1. Draw a parse tree for the string (x+y)&lowastz&lowastx according to each of the grammars (G_<1>, G_<2>,) and (G_<3>,) as given in this section.
  2. Draw three different parse trees for the string ababbaab based on the grammar given in part a) of exercise 1.
  3. Suppose that the string abbcabac has the following parse tree, according to some grammar G:

a) List five production rules that must be rules in the grammar G, given that this is a valid parse tree.

b) Give a left derivation for the string abbcabac according to the grammar G.

c) Give a right derivation for the string abbcabac according to the grammar G.

6. Show the full sequence of shift and reduce operations that are used in the LR(1) parsing of the string x + (y) &lowast z according to the grammar G3, and give the corresponding right derivation of the string.

7. This section showed how to use LL(1) and LR(1) parsing to find a derivation of a string in the language L(G) generated by some grammar G. How is it possible to use LL(1) or LR(1) parsing to determine for an arbitrary string wwhether w &isin L(G) ? Give an example.


5.1 Gaussian process prior

Gaussian process is a generic term that pops up, taking on disparate but quite specific meanings, in various statistical and probabilistic modeling enterprises. As a generic term, all it means is that any finite collection of realizations (i.e., (n) observations) is modeled as having a multivariate normal (MVN) distribution. That, in turn, means that characteristics of those realizations are completely described by their mean (n) -vector (mu) and (n imes n) covariance matrix (Sigma) . With interest in modeling functions, we’ll sometimes use the term mean function, thinking of (mu(x)) , and covariance function, thinking of (Sigma(x, x')) . But ultimately we’ll end up with vectors (mu) and matrices (Sigma) after evaluating those functions at specific input locations (x_1, dots, x_n) .

You’ll hear people talk about function spaces, reproducing kernel Hilbert spaces, and so on, in the context of GP modeling of functions. Sometimes thinking about those aspects/properties is important, depending on context. For most purposes that makes things seem fancier than they really need to be.

The action, at least the part that’s interesting, in a GP treatment of functions is all in the covariance. Consider a covariance function defined by inverse exponentiated squared Euclidean distance:

Here covariance decays exponentially fast as (x) and (x') become farther apart in the input, or (x) -space. In this specification, observe that (Sigma(x,x) = 1) and (Sigma(x, x') < 1) for (x' e x) . The function (Sigma(x, x')) must be positive definite. For us this means that if we define a covariance matrix (Sigma_n) , based on evaluating (Sigma(x_i, x_j) ) at pairs of (n) (x) -values (x_1, dots, x_n) , we must have that

[ x^ op Sigma_n x > 0 quad mbox < for all >x e 0. ]

We intend to use (Sigma_n) as a covariance matrix in an MVN, and a positive (semi-) definite covariance matrix is required for MVN analysis. In that context, positive definiteness is the multivariate extension of requiring that a univariate Gaussian have positive variance parameter, (sigma^2) .

To ultimately see how a GP with that simple choice of covariance (Sigma_n) can be used to perform regression, let’s first see how GPs can be used to generate random data following a smooth functional relationship. Suppose we take a bunch of (x) -values: (x_1,dots, x_n) , define (Sigma_n) via (Sigma_n^ = Sigma(x_i, x_j)) , for (i,j=1,dots,n) , then draw an (n) -variate realization

and plot the result in the (x) - (y) plane. That was a mouthful, but don’t worry: we’ll see it in code momentarily. First note that the mean of this MVN is zero this need not be but it’s quite surprising how well things work even in this special case. Location invariant zero-mean GP modeling, sometimes after subtracting off a middle value of the response (e.g., (ar) ), is the default in computer surrogate modeling and (ML) literatures. We’ll talk about generalizing this later.

Here’s a version of that verbal description with (x) -values in 1d. First create an input grid with 100 elements.

Next calculate pairwise squared Euclidean distances between those inputs. I like the distance function from the plgp package (Gramacy 2014) in R because it was designed exactly for this purpose (i.e., for use with GPs), however dist in base R provides similar functionality.

Then build up covariance matrix (Sigma_n) as inverse exponentiated squared Euclidean distances. Notice that the code below augments the diagonal with a small number eps (equiv epsilon) . Although inverse exponentiated distances guarantee a positive definite matrix in theory, sometimes in practice the matrix is numerically ill-conditioned. Augmenting the diagonal a tiny bit prevents that. Neal (1998) , a GP vanguard in the statistical/ML literature, calls (epsilon) the jitter in this context.

Finally, plug that covariance matrix into an MVN random generator below I use one from the mvtnorm package (Genz et al. 2018) on CRAN.

That’s it! We’ve generated a finite realization of a random function under a GP prior with a particular covariance structure. Now all that’s left is visualization. Figure 5.1 plots those X and Y pairs as tiny connected line segments on an (x) - (y) plane.

FIGURE 5.1: A random function under a GP prior.

Because the (Y) -values are random, you’ll get a different curve when you try this on your own. We’ll generate some more below in a moment. But first, what are the properties of this function, or more precisely of a random function generated in this way? Several are easy to deduce from the form of the covariance structure. We’ll get a range of about ([-2,2]) , with 95% probability, because the scale of the covariance is 1, ignoring the jitter (epsilon) added to the diagonal. We’ll get several bumps in the (x) -range of ([0,10]) because short distances are highly correlated (about 37%) and long distances are essentially uncorrelated ( (1e^<-7>) ).

Now the function plotted above is only a finite realization, meaning that we really only have 100 pairs of points. Those points look smooth, in a tactile sense, because they’re close together and because the plot function is “connecting the dots” with lines. The full surface, which you might conceptually extend to an infinite realization over a compact domain, is extremely smooth in a calculus sense because the covariance function is infinitely differentiable, a discussion we’ll table for a little bit later.

Besides those three things – scale of two, several bumps, smooth look – we won’t be able to anticipate much else about the nature of a particular realization. Figure 5.2 shows three new random draws obtained in a similar way, which will again look different when you run the code on your own.

FIGURE 5.2: Three more random functions under a GP prior.

Each random finite collection is different than the next. They all have similar range, about the same number of bumps, and are smooth. That’s what it means to have function realizations under a GP prior: (Y(x) sim mathcal) .

5.1.1 Gaussian process posterior

Of course, we’re not in the business of generating random functions. I’m not sure what that would be useful for. Instead, we ask: given examples of a function in pairs ((x_1, y_1), dots, (x_n, y_n)) , comprising data (D_n = (X_n, Y_n)) , what random function realizations could explain – could have generated – those observed values? That is, we want to know about the conditional distribution of (Y(x) mid D_n) . If we call (Y(x) sim mathcal) the prior, then (Y(x) mid D_n) must be the posterior.

Fortunately, you don’t need to be a card-carrying Bayesian to appreciate what’s going on, although that perspective has really taken hold in ML. That conditional distribution, (Y(x) mid D_n) , which one might more simply call a predictive distribution, is a familiar quantity in regression analysis. Forget for the moment that when regressing one is often interested in other aspects, like relevance of predictors through estimates of parameter standard errors, etc., and that so far our random functions look like they have no noise. The somewhat strange, and certainly most noteworthy, thing is that so far there are no parameters!

Let’s shelve interpretation (Bayesian updating or a twist on simple regression) for a moment and focus on conditional distributions, because that’s what it’s really all about. Deriving that predictive distribution is a simple application of deducing a conditional from a (joint) MVN. From Wikipedia, if an (N) -dimensional random vector (X) is partitioned as

[ X = left( egin X_1 X_2 end ight) quad mbox < with sizes >quad left( egin q imes 1 (N-q) imes 1 end ight), ]

and accordingly (mu) and (Sigma) are partitioned as,

[ mu = left( egin mu_1 mu_2 end ight) quad mbox < with sizes >quad left( egin q imes 1 (N-q) imes 1 end ight) ]

[ Sigma = left(egin Sigma_ <11>& Sigma_ <12> Sigma_ <21>& Sigma_ <22>end ight) mbox < with sizes > left(egin q imes q & q imes (N-q) (N-q) imes q & (N - q) imes (N-q) end ight), ]

then the distribution of (X_1) conditional on (X_2 = x_2) is MVN (X_1 mid x_2 sim mathcal_q (ar, ar)) , where

[começar ar &= mu_1 + Sigma_ <12>Sigma_<22>^<-1>(x_2 - mu_2) ag <5.1> mbox quad ar &= Sigma_ <11>- Sigma_ <12>Sigma_<22>^ <-1>Sigma_<21>. otag end]

An interesting feature of this result is that conditioning upon (x_2) alters the variance of (X_1) . Observe that (ar) above is reduced compared to its marginal analog (Sigma_<11>) . Reduction in variance when conditioning on data is a hallmark of statistical learning. We know more – have less uncertainty – after incorporating data. Curiously, the amount by which variance is decreased doesn’t depend on the value of (x_2) . Observe that the mean is also altered, comparing (mu_1) to (ar) . In fact, the equation for (ar) is a linear mapping, i.e., of the form (ax + b) for vectors (a) and (b) . Finally, note that (Sigma_ <12>= Sigma_<21>^ op) so that (ar) is symmetric.

Ok, how do we deploy that fundamental MVN result towards deriving the GP predictive distribution (Y(x) mid D_n) ? Consider an (n+1^>) observation (Y(x)) . Allow (Y(x)) and (Y_n) to have a joint MVN distribution with mean zero and covariance function (Sigma(x,x')) . That is, stack

[ left( egin Y(x) Y_n end ight) quad mbox < with sizes >quad left( egin 1 imes 1 n imes 1 end ight), ]

and if (Sigma(X_n,x)) is the (n imes 1) matrix comprised of (Sigma(x_1, x), dots, Sigma(x_n, x)) , its covariance structure can be partitioned as follows:

[ left(egin Sigma(x,x) & Sigma(x,X_n) Sigma(X_n,x) & Sigma_n end ight) mbox < with sizes > left(egin 1 imes 1 & 1 imes n n imes 1 & n imes n end ight). ]

Recall that (Sigma(x,x) = 1) with our simple choice of covariance function, and that symmetry provides (Sigma(x,X_n) = Sigma(X_n,x)^ op) .

Applying Eq. (5.1) yields the following predictive distribution

[ Y(x) mid D_n sim mathcal(mu(x), sigma^2(x)) ]

[começar mbox quad mu(x) &= Sigma(x, X_n) Sigma_n^ <-1>Y_n ag <5.2> mbox quad sigma^2(x) &= Sigma(x,x) - Sigma(x, X_n) Sigma_n^ <-1>Sigma(X_n, x). otag end]

Observe that (mu(x)) is linear in observations (Y_n) , so we have a linear predictor! In fact it’s the best linear unbiased predictor (BLUP), an argument we’ll leave to other texts (e.g., Santner, Williams, and Notz 2018) . Also notice that (sigma^2(x)) is lower than the marginal variance. So we learn something from data (Y_n) in fact the amount that variance goes down is a quadratic function of distance between (x) and (X_n) . Learning is most efficient for (x) that are close to training data locations (X_n) . However the amount learned doesn’t depend upon (Y_n) . We’ll return to that later.

The derivation above is for “pointwise” GP predictive calculations. These are sometimes called the kriging equations, especially in geospatial contexts. We can apply them, separately, for many predictive/testing locations (x) , one (x) at a time, but that would ignore the obvious correlation they’d experience in a big MVN analysis. Alternatively, we may consider a bunch of (x) locations jointly, in a testing design (mathcal) of (n') rows, say, all at once:

[ Y(mathcal) mid D_n sim mathcal_(mu(mathcal), Sigma(mathcal)) ]

[começar mbox quad mu(mathcal) &= Sigma(mathcal, X_n) Sigma_n^ <-1>Y_n ag<5.3> mbox quad Sigma(mathcal) &= Sigma(mathcal,mathcal) - Sigma(mathcal, X_n) Sigma_n^ <-1>Sigma(mathcal, X_n)^ op, otag end]

where (Sigma(mathcal, X_n)) is an (n' imes n) matrix. Having a full covariance structure offers a more complete picture of the random functions which explain data under a GP posterior, but also more computation. The (n' imes n') matrix (Sigma(mathcal)) could be enormous even for seemingly moderate (n') .

Simple 1d GP prediction example

Consider a toy example in 1d where the response is a simple sinusoid measured at eight equally spaced (x) -locations in the span of a single period of oscillation. R code below provides relevant data quantities, including pairwise squared distances between the input locations collected in the matrix D , and its inverse exponentiation in Sigma .

Now this is where the example diverges from our earlier one, where we used such quantities to generate data from a GP prior. Applying MVN conditioning equations requires similar calculations on a testing design (mathcal) , coded as XX below. We need inverse exponentiated squared distances between those XX locations …

… as well as between testing locations (mathcal) and training data locations (X_n) .

Note that an (epsilon) jitter adjustment is not required for SX because it need not be decomposed in the conditioning calculations (and SX is anyways not square). We do need jitter on the diagonal of SXX though, because this matrix is directly involved in calculation of the predictive covariance which we shall feed into an MVN generator below.

Now simply follow Eq. (5.3) to derive joint predictive equations for XX (equiv mathcal) : invert (Sigma_n) , apply the linear predictor, and calculate reduction in covariance.

Above mup maps to (mu(mathcal)) evaluated at our testing grid (mathcal equiv) XX , and Sigmap similarly for (Sigma(mathcal)) via pairs in XX . As a computational note, observe that Siy <- Si %*% y may be pre-computed in time quadratic in (n=) length(y) so that mup may subsequently be calculated for any XX in time linear in (n) , without redoing Siy for example, as solve(Sigma, y) . There are two reasons we’re not doing that here. One is to establish a clean link between code and mathematical formulae. The other is a presumption that the variance calculation, which remains quadratic in (n) no matter what, is at least as important as the mean.

Mean vector and covariance matrix in hand, we may generate (Y) -values from the posterior/predictive distribution (Y(mathcal) mid D_n) in the same manner as we did from the prior.

Those (Y(mathcal) equiv) YY samples may then be plotted as a function of predictive input (mathcal equiv) XX locations. Before doing that, extract some pointwise quantile-based error-bars from the diagonal of (Sigma(mathcal)) to aid in visualization.

Figure 5.3 plots each of the random predictive, finite realizations as gray curves. Training data points are overlayed, along with true response at the (mathcal) locations as a thin blue line. Predictive mean (mu(mathcal)) in black, and 90% quantiles in dashed-red, are added as thicker lines.

FIGURE 5.3: Posterior predictive distribution in terms of means (solid black), quantiles (dashed-red), and draws (gray). The truth is shown as a thin blue line.

What do we observe in the figure? Notice how the predictive surface interpolates the data. That’s because (Sigma(x, x) = 1) and (Sigma(x, x') ightarrow 1^-) as (x' ightarrow x) . Error-bars take on a “football” shape, or some say a “sausage” shape, being widest at locations farthest from (x_i) -values in the data. Error-bars get really big outside the range of the data, a typical feature in ordinary linear regression settings. But the predictive mean behaves rather differently than under an ordinary linear model. For GPs it’s mean-reverting, eventually leveling off to zero as (x in mathcal) gets far away from (X_n) . Predictive variance, as exemplified by those error-bars, is also reverting to something: a prior variance of 1. In particular, variance won’t continue to increase as (x) gets farther and farther from (X_n) . Together those two “reversions” imply that although we can’t trust extrapolations too far outside of the data range, at least their behavior isn’t unpredictable, as can sometimes happen in linear regression contexts, for example when based upon feature-expanded (e.g., polynomial basis) covariates.

These characteristics, especially the football/sausage shape, is what makes GPs popular as surrogates for computer simulation experiments. That literature, which historically emphasized study of deterministic computer simulators, drew comfort from interpolation-plus-expansion of variance away from training simulations. Perhaps more importantly, they liked that out-of-sample prediction was highly accurate. Come to think of it, that’s why spatial statisticians and machine learners like them too. But hold that thought there are a few more things to do before we get to predictive comparisons.

5.1.2 Higher dimension?

There’s nothing particularly special about the presentation above that would preclude application in higher input dimension. Except perhaps that visualization is a lot simpler in 1d or 2d. We’ll get to even higher dimensions with some of our later examples. For now, consider a random function in 2d sampled from a GP prior. The plan is to go back through the process above: first prior, then (posterior) predictive, etc.

Begin by creating an input set, (X_n) , in two dimensions. Here we’ll use a regular (20 imes 20) grid.

Then calculate pairwise distances and evaluate covariances under inverse exponentiated squared Euclidean distances, plus jitter.

Finally make random MVN draws in exactly the same way as before. Below we save two such draws.

For visualization in Figure 5.4, persp is used to stretch each (20 imes 20) = 400-variate draw over a mesh with a fortuitously chosen viewing angle.

FIGURE 5.4: Two random functions under a GP prior in 2d.

So drawing from a GP prior in 2d is identical to the 1d case, except with a 2d input grid. All other code is “cut-and-paste”. Visualization is more cumbersome, but that’s a cosmetic detail. Learning from training data, i.e., calculating the predictive distribution for observed ((x_i, y_i)) pairs, is no different: more cut-and-paste.

To try it out we need to cook up some toy data from which to learn. Consider the 2d function (y(x) = x_1 exp<-x_1^2 - x_2^2>) which is highly nonlinear near the origin, but flat (zero) as inputs get large. This function has become a benchmark 2d problem in the literature for reasons that we’ll get more into in Chapter 9. Suffice it to say that thinking up simple-yet-challenging toy problems is a great way to get noticed in the community, even when you borrow a common example in vector calculus textbooks or one used to demonstrate 3d plotting features in MATLAB®.

Above, a Latin hypercube sample (LHS §4.1) is used to generate forty (coded) input locations in lieu of a regular grid in order to create a space-filling input design. A regular grid with 400 elements would have been overkill, but a uniform random design of size forty or so would have worked equally well. Coded inputs are mapped onto a scale of ([-2,4]^2) in order to include both bumpy and flat regions.

Let’s suppose that we wish to interpolate those forty points onto a regular (40 imes 40) grid, say for stretching over a mesh. Here’s code that creates such testing locations XX (equivmathcal) in natural units.

Now that we have inputs and outputs, X and y , and predictive locations XX we can start cutting-and-pasting. Start with the relevant training data quantities …

… and follow with similar calculations between input sets X and XX .

Then apply Eq. (5.3). Code wise, these lines are identical to what we did in the 1d case.

It’s hard to visualize a multitude of sample paths in 2d – two was plenty when generating from the prior – but if desired, we may obtain them with the same rmvnorm commands as in §5.1.1. Instead focus on plotting pointwise summaries, namely predictive mean (mu(x) equiv) mup and predictive standard deviation (sigma(x)) :

The left panel in Figure 5.5 provides an image plot of the mean over our regularly-gridded inputs XX the right panel shows standard deviation.

FIGURE 5.5: Posterior predictive for a two-dimensional example, via mean (left) and standard deviation (right) surfaces. Training data input locations are indicated by open circles.

What do we observe? Pretty much the same thing as in the 1d case. We can’t see it, but the predictive surface interpolates. Predictive uncertainty, here as standard deviation (sigma(x)) , is highest away from (x_i) -values in the training data. Predictive intervals don’t look as much like footballs or sausages, yet somehow that analogy still works. Training data locations act as anchors to smooth variation between points with an organic rise in uncertainty as we imagine predictive inputs moving away from one toward the next.

Figure 5.6 provides another look, obtained by stretching the predictive mean over a mesh. Bumps near the origin are clearly visible, with a flat region emerging for larger (x_1) and (x_2) settings.

FIGURE 5.6: Perspective view on the posterior mean surface from the left panel of Figure 5.5.

Well that’s basically it! Now you know GP regression. Where to go from here? Hopefully I’ve convinced you that GPs hold great potential as a nonlinear regression tool. It’s kinda-cool that they perform so well – that they “learn” – without having to tune anything. In statistics, we’re so used to seeking out optimal settings of parameters that a GP predictive surface might seem like voodoo. Simple MVN conditioning is able to capture input–output dynamics without having to “fit” anything, or without trying to minimize a loss criteria. That flexibility, without any tuning knobs, is what people think of when they call GPs a nonparametric regression tool. All we did was define covariance in terms of (inverse exponentiated squared Euclidean) distance, condition, and voilà.

But when you think about it a little bit, there are lots of (hidden) assumptions which are going to be violated by most real-data contexts. Data is noisy. The amplitude of all functions we might hope to learn will not be 2. Correlation won’t decay uniformly in all directions, i.e., radially. Even the most ideally smooth physical relationships are rarely infinitely smooth.

Yet we’ll see that even gross violations of those assumptions are easy to address, or “fix up”. At the same time GPs are relatively robust to transgressions between assumptions and reality. In other words, sometimes it works well even when it ought not. As I see it – once we clean things up – there are really only two serious problems that GPs face in practice: stationarity of covariance (§5.3.3), and computational burden, which in most contexts go hand-in-hand. Remedies for both will have to wait for Chapter 9. For now, let’s keep the message upbeat. There’s lots that can be accomplished with the canonical setup, whose description continues below.


  • M. Allamanis and C. Sutton (2013) Why, when, and what: analyzing stack overflow questions by topic, type, and code . In Proceedings of the 10th Working Conference on Mining Software Repositories , pp. 53–56 . Cited by: §3.1 .
  • M. Allamanis, D. Tarlow, A. Gordon, and Y. Wei (2015) Bimodal modelling of source code and natural language . Em

International Conference on Machine Learning

Moses: open source toolkit for statistical machine translation

Question difficulty estimation in community question answering services

Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing

Join one of the world's largest A.I. communities