2kFatorial Matheus

Prévia do material em texto

30/05/2017
1
Matheus Alcântara Souza
Métodos Quantitativos em Ciência da Computação
• O que é um projeto experimental?• Variáveis de resposta e Fatores• Erros comuns em “experimentação”• Tipos de projetos experimentais
• Simples• Fatorial Completo• Fatorial Fracionado
30/05/2017
2
 Objetivos:
 Obter o máximo de informação possível do mínimo de experimentos
 Permitir uma análise apropriada do efeito de determinados parâmetros nos resultados
Como...
 projetar um conjunto de experimentos?
 modelar a descrição resultados?
 estimar o desempenho de cada alternativa?
 verificar e minimizar erros?
 definir o intervalo de confiança?
 verificar diferenças entre as alternativas?
 verificar se o modelo é adequado?
30/05/2017
3
 Variáveis de resposta
 Resultados de um experimento
 Ex: tempo de resposta, consumo de energia, throughput, etc...
 Fatores (preditores)
 Parâmetros ou variáveis que afetam a variável de resposta. O nível é o valor do fator.
 Ex: tamanho de memória, nº nós da rede, nível de escolaridade, gênero
 Ignorar a variação causada pelo erro
 Descontrole sobre parâmetros importantes
 Não isolar efeitos de diferentes fatores
 Simplificar com “um fator de cada vez”
 Ignorar interações de fatores
 Condução de muitos experimentos
30/05/2017
4
 Projeto Simples
 Começar de uma alternativa típica
 Variar um fator por vez
 Número de experimentos:
݊ ൌ 1 ൅ ෍ሺ݊௜ െ 1ሻ
௞
௜ୀଵ Não é estatisticamente eficiente
 Problema da interação entre fatores
CPU Memória Topologia Aplicação
 Projeto Simples
Intel
ARM
AMD
16GB
32GB
8GB
Big Data
Clima
Imagens
Torus
Cluster
Mesh
Anel
30/05/2017
5
 Fatorial Completo
 Combinação de todos os fatores e seus níveis
 Número de experimentos:
݊ ൌ ෑ ݊௜
௞
௜ୀଵ
 O custo para realização é alto
CPU Memória Topologia Aplicação
 Fatorial Completo
Intel
ARM
AMD
16GB
32GB
8GB
Big Data
Clima
Imagens
Torus
Cluster
Mesh
Anel
30/05/2017
6
 Fatorial Fracionado
 “Fracionar” os fatores e/ou níveis
 Número de experimentos:
▪ Depende dos fatores ou níveis removidos
 Reduz o custo
 Reduz a informação obtida no experimento
CPU Memória TopologiaTopologia Aplicação
 Fatorial Fracionado
Intel
ARM
AMD
16GB16GB
32GB
8GB
Big Data
ClimaClima
Imagens
TorusTorus
ClusterCluster
MeshMesh
AnelAnel
30/05/2017
7
• Projeto 2² fatorial
• Cálculo de efeitos
• Alocação de variação
 2 fatores com 2 níveis cada, e 1 resposta
 Ex: Desempenho em Milhões de Instruções Por Segundo (MIPS)
Tamanho de cache
Tamanho de memória
4 MB 16MB
1 kB 15 45
2 kB 25 75
30/05/2017
8
 Associar a cada fator extremo um sinal (+ou-)
 ୅ୀ ቚିଵ ୱ ସ ୑୆ ୢୣ ୫ୣ୫ó୰୧ୟଵ ୱ ଵ଺ ୑୆ ୢୣ ୫ୣ୫ó୰୧ୟ
 ୆ୀ ቚିଵ ୱୣ ଵ ୩୆ ୢୣ ୡୟୡ୦ୣଵ ୱ ଶ ୩୆ ୢୣ ୡୟୡ୦ୣ
 Seja y a variável de resposta. Temos o seguinte modelo de regressão:
 y ൌ q଴ ൅ q୅ݔ୅ ൅ q୆ݔ୆ ൅ q୅୆ݔ୅ݔ୆
15 ൌ ݍ଴ െ ݍ஺ െ ݍ஻ ൅ ݍ஺஻ 45 ൌ ݍ଴ ൅ ݍ஺ െ ݍ஻ െ ݍ஺஻25 ൌ ݍ଴ െ ݍ஺ ൅ ݍ஻ െ ݍ஺஻75 ൌ ݍ଴ ൅ ݍ஺ ൅ ݍ஻ ൅ ݍ஺஻
Tamanho de cache
Tamanho de memória
4 MB 16MB
1 kB 15 45
2 kB 25 75
x୅ୀ ቚିଵ ୱୣ ସ ୑୆ ୢୣ ୫ୣ୫ó୰୧ୟଵ ୱୣ ଵ଺ ୑୆ ୢୣ ୫ୣ୫ó୰୧ୟx୆ୀ ቚିଵ ୱୣ ଵ ୩୆ ୢୣ ୡୟୡ୦ୣଵ ୱୣ ଶ ୩୆ ୢୣ ୡୟୡ୦ୣ
30/05/2017
9
 Seja y a variável de resposta. Temos o seguinte modelo de regressão:
 y ൌ q଴ ൅ q୅ݔ୅ ൅ q୆ݔ୆ ൅ q୅୆ݔ୅ݔ୆
y ൌ 40 ൅ 20ݔ஺ ൅ 10ݔ஻ ൅ 5ݔ஺ݔ஻
y ൌ 40 ൅ 20ݔ஺ ൅ 10ݔ஻ ൅ 5ݔ஺ݔ஻
 Interpretação:
Desempenho médio: 40 MIPS
Efeito da memória: 20 MIPS
Efeito da cache: 10 MIPS
Efeito da interação (memória x cache): 5 MIPS
30/05/2017
10
 Generalizando, com experimentos 2² temos:
Experimento A B y
1 -1 -1 ݕଵ2 1 -1 ݕଶ3 -1 1 ݕଷ4 1 1 ݕସ
 Com o modelo de regressão, temos:
 y ൌ q଴ ൅ q୅ݔ୅ ൅ q୆ݔ୆ ൅ q୅୆ݔ୅ݔ୆
ݕଵ ൌ ݍ଴ െ ݍ஺ െ ݍ஻ ൅ ݍ஺஻ݕଶ ൌ ݍ଴ ൅ ݍ஺ െ ݍ஻ െ ݍ஺஻ݕଷ ൌ ݍ଴ െ ݍ஺ ൅ ݍ஻ െ ݍ஺஻ݕସ ൌ ݍ଴ ൅ ݍ஺ ൅ ݍ஻ ൅ ݍ஺஻
30/05/2017
11
 Solucionando (contrastes):
(os efeitos são combinações lineares das respostas)
ݍ଴ ൌ 14 ሺݕଵ ൅ ݕଶ ൅ ݕଷ ൅ ݕସሻ
ݍ஺ ൌ 14 ሺെݕଵ ൅ ݕଶ െ ݕଷ ൅ ݕସሻ
ݍ஻ ൌ 14 ሺെݕଵ െ ݕଶ ൅ ݕଷ ൅ ݕସሻ
ݍ஺஻ ൌ 14 ሺݕଵ െ ݕଶ െ ݕଷ ൅ ݕସሻ
 Método da tabela de sinais:
I A B AB y
1 -1 -1 1 15
1 1 -1 -1 45
1 -1 1 -1 25
1 1 1 1 75
160 80 40 20 Total
40 20 10 5 Total/4
30/05/2017
12
 A importância de um fator é igual a proporção da variação explicada
 Variância amostral de ݕ ⇒ ݏ²௬ ൌ ∑ ሺ௬೔ି௬തሻ²మ²೔సభଶ²ିଵ Variação total de ݕ ⇒ SST ൌ ∑ ሺݕ௜ െ ݕതሻ²ଶ²௜ୀଵ
 Para um projeto 2²:SST ൌ 2²ݍ²஺ ൅ 2²ݍ²஻ ൅ 2²ݍ²஺஻SST ൌ 2ଶ ݍଶ஺ ൅ ݍଶ஻ ൅ ݍଶ஺஻SST ൌ SSA ൅ SSB ൅ SSAB
 No exemplo
ݕത ൌ 14 15 ൅ 45 ൅ 25 ൅ 75 ൌ 40 Logo:
SST ൌ ෍ ሺݕ௜ െ ݕതሻ²ସ௜ୀଵSST ൌ 25ଶ ൅ 5ଶ ൅ 15ଶ ൅ 35ଶ ൌ 2100
 Após um processo de derivação:SST ൌ 4 ൈ 20² ൅ 4 ൈ 10² ൅ 4 ൈ 5²
30/05/2017
13
SST ൌ 4 ൈ 20² ൅ 4 ൈ 10² ൅ 4 ൈ 5²
 Variação total: 2100
 Variação pela memória: SSA = 1600 (76%)
 Variação pela cache: SSB = 400 (19%)
 Variação pela interação: SSAB = 100 (5%)
A variação ajuda a decidir quando explorar um fator ou interação entre fatores.
• Projeto 2k fatorial
• Cálculo de efeitos
• Alocação de variação
30/05/2017
14
 Determinar o efeito de k fatores
 Cada fator com 2 níveis
 Segue os mesmos princípios do projeto 2²
 São produzidos 2k efeitos
 k efeitos principais
 ௞ଶ efeitos de interações com 2 fatores
 ௞ଷ efeitos de interações com 3 fatores ... e assim por diante
 Vamos incluir um novo fator no exemplo (2³)
 A: Tamanho de memória
 B: Tamanho de cache
 C: Número de núcleos
Tamanho de cache
Tamanho de memória
4 MB 16MB
Dual core Quad core Dual core Quad core
1 kB 14 46 22 58
2 kB 10 50 34 86
30/05/2017
15
I A B C AB AC BC ABC y
1 -1 -1 -1 1 1 1 -1 14
1 1 -1 -1 -1 -1 1 1 22
1 -1 1 -1 -1 1 -1 1 10
1 1 1 -1 1 -1 -1 -1 34
1 -1 -1 1 1 -1 -1 1 46
1 1 -1 1 -1 1 -1 -1 58
1 -1 1 1 -1 -1 1 -1 50
1 1 1 1 1 1 1 1 86
320 80 40 160 40 16 24 9 Total
40 10 5 20 5 2 3 1 Total/2³
 Temos que:SST ൌ 2ଷ ݍଶ஺ ൅ ݍଶ஻ ൅ ݍଶ஼ ൅2ଷ ݍଶ஺஻ ൅ ݍଶ஺஼ ൅ ݍଶ஻஼ ൅2ଷ ݍଶ஺஻஼ Logo:SST ൌ 8 10² ൅ 5² ൅ 20² ൅ 5² ൅ 2² ൅ 3² ൅ 1²SST ൌ 800 ൅ 200 ൅ 3200 ൅ 200 ൅ 32 ൅ 72 ൅ 8SST ൌ 18% ൅ 4% ൅ 71% ൅ 4% ൅ 1% ൅ 2% ൅ 0%
I A B C AB AC BC ABC y
40 10 5 20 5 2 3 1 Total/2³
30/05/2017
16
 Temos que:SST ൌ 2ଷ ݍଶ஺ ൅ ݍଶ஻ ൅ ݍଶ஼ ൅2ଷ ݍଶ஺஻ ൅ ݍଶ஺஼ ൅ ݍଶ஻஼ ൅2ଷ ݍଶ஺஻ Logo:SST ൌ 8 10² ൅ 5² ൅ 20² ൅ 5² ൅ 2² ൅ 3² ൅ 1²SST ൌ 800 ൅ 200 ൅ 3200 ൅ 200 ൅ 32 ൅ 72 ൅ 8SST ൌ 18% ൅ 4% ൅ 71% ൅ 4% ൅ 1% ൅ 2% ൅ 0%
I A B C AB AC BC ABC y
40 10 5 20 5 2 3 1 Total/2³
O fator C (Número de núcleos) é o mais importante dentre todos.Apresentou o maior efeito.
• 2kr fatorial
• Experimentos não determinísticos replicados (diversas respostas)
• Adiciona um erro e ao modelo, e a SSE (variação não explicada)
• Efeitos possuem intervalo de confiança
30/05/2017
17
• Experimento de 1 fator
• Apenas um fator, mas com vários níveis
• Devem ser categóricos
• 2k-p fatorial
• Fatorial completo de 2 fatores
• Fatorial completo de k fatores
• Exibidos no início da apresentação
30/05/2017
18
30/05/2017
19
 JAIN, R. The art of computer systems performance analysis. New York: Wiley, 1991
 Portal Action:http://www.portalaction.com.br/planejamento-de-experimento/experimentos-fatoriais-completos 
Páginas 272 a 389
Disponível na biblioteca