Aleatoriedade no Coração dos Algoritmos do Futuro

Transcript

2. MACHINE LEARNING RESOLVE MUITA COISA MAS NÃO É SEMPRE A MELHOR SOLUÇÃO.
3. DETECTAR PLÁGIO EM BILHÕES DE TEXTOS
4. DETECTAR SIMILARIDADE EM BANCOS DE DADOS DE IMAGENS
5. ESTIMAR INTERSEÇÃO DE CONJUNTOS, SEM PRECISAR TÊ-LOS PRÓXIMOS GEOGRAFICAMENTE.
6. ALEATORIEDADE NO CORAÇÃO DOS ALGORITMOS DO FUTURO
7. • PAI DO MIGUEL • BACHAREL E QUASE MESTRE • PROGRAMADOR • VICIADO EM COMPETIÇÕES QUEM É JUAN LOPES?
8. SLIDES, LINKS E DEMOS TWITTER E GITHUB
9. ALGORITMOS RANDOMIZADOS
10. • HASHTABLES • GERAÇÃO DE PARES DE CHAVES CRIPTOGRÁFICAS • RANDOMIZED QUICKSORT ALGORITMOS RANDOMIZADOS
12. RANDOMIZED ALGORITHMS
14. INTRODUÇÃO AOS ALGORITMOS RANDOMIZADOS
15. MINING OF MASSIVE DATASETS
16. ALGORITMOS RANDOMIZADOS PROBABILÍSTICOS
17. VAMOS FALAR DE POLÍTICA?
18. QUAL É A BASE TEÓRICA DE UMA PESQUISA ELEITORAL?
19. QUAL É A BASE TEÓRICA DE UMA ESTIMATIVA DE PARTICIPANTES?
20. PROBABILIDADE E ESTATÍSTICA
21. VARIÁVEL ALEATÓRIA X
22. VARIÁVEL ALEATÓRIA X ROLAGEM DE DADO DE 6 LADOS
23. ESTIMADORES NÃO- ENVIESADOS
24. COMO CRIAR UMA VARIÁVEL ALEATÓRIA QUE ESTIME ALGUM VALOR IMPORTANTE?
25. A OPINIÃO DE UM INDIVÍDUO ALEATÓRIO EM UMA POPULAÇÃO É UM ESTIMADOR DA OPINIÃO DA POPULAÇÃO
26. A QUANTIDADE DE PESSOAS EM UM TRECHO DE UMA MANIFESTAÇÃO É UM ESTIMADOR DO NÚMERO TOTAL DE PESSOAS
27. COMPOSIÇÃO DE ESTIMADORES DIMINUI A VARIÂNCIA
28. • FILTRO DE BLOOM [Blo70] • CM-SKETCH [CM05] • MINHASH [Bro97] • HYPERLOGLOG [FFGM08] ESTRUTURAS PROBABILÍSTICAS
29. 1970 1990 1980 2000 2010 LINHA DO TEMPO FILTRO DE BLOOM [Blo70] FM-SKETCH [FM85] MINHASH [Bro97] KMV-SKETCH [BYJK+02] LSH THEORY [IM98] SIMHASH [Cha02] LOGLOG [DF03] AMS PAPER [AMS96] CM-SKETCH [CM05] HYPERLOGLOG [FFGM08] SPECTRAL BLOOM [CM03]
30. – DONALD KNUTH HASH FUNCTIONS
31. HASH FUNCTIONS x h(x) 0: 50% 1: 50% 0: 50% 1: 50% 0: 50% 1: 50% …
32. MINHASH [Bro97] Andrei Z Broder. On the resemblance and containment of documents. In Compression and Complexity of Sequences 1997. Proceedings, pages 21–29. IEEE, 1997.
33. MINHASH • VARIÁVEL DE BERNOULLI • ÍNDICE DE JACCARD • DUAS VARIANTES
34. MINHASH, COM CALMA A B
35. A B MINHASH, COM CALMA
36. A B A B MINHASH, COM CALMA
37. CALMA!
38. MINHASH • CADA FUNÇÃO DEFINE UM ESTIMADOR NÃO-ENVIESADO • MÚLTIPLAS FUNÇÕES DE HASH • COMPARAÇÃO DOS VALORES DE CADA ASSINATURA
39. MINHASH • ASSINATURA DEFINIDA POR K MENORES VALORES • TAMBÉM É VARIÁVEL DE BERNOULLI • COMPARAÇÃO DOS VALORES DE CADA ASSINATURA
40. MINHASH • PODE SER 1 COM PROBABILIDADE p E 0 COM PROBABILIDADE 1-p
41. MINHASH
42. MINHASH • 42 OBRAS DE SHAKESPEARE • 84 DOCUMENTOS NO TOTAL • 0 ≤ K ≤ 1000
43. MINHASH S 1 S 2 S 3 S 4 S 5 h 1 h 2 h 3 h 4 h 5 h 6 h 7 h 8
44. MINHASH S 1 S 2 S 3 S 4 S 5 h 1 h 2 h 3 h 4 h 5 h 6 h 7 h 8 r=2 }
45. MINHASH S 1 S 2 S 3 S 4 S 5 r 1 h 1 h 2 r 2 h 3 h 4 r 3 h 5 h 6 r 4 h 7 h 8 }r=2 { b=4
46. MINHASH S 1 S 2 S 3 S 4 S 5 r 1 h 1 h 2 r 2 h 3 h 4 r 3 h 5 h 6 r 4 h 7 h 8 S 1 S 4
47. MINHASH S 1 S 2 S 3 S 4 S 5 r 1 h 1 h 2 r 2 h 3 h 4 r 3 h 5 h 6 r 4 h 7 h 8 S 2 S 5 S 1 S 4
48. MINHASH S 1 S 2 S 3 S 4 S 5 r 1 h 1 h 2 r 2 h 3 h 4 r 3 h 5 h 6 r 4 h 7 h 8 S 2 S 5 S 2 S 5 S 1 S 4
49. MINHASH S 1 S 2 S 3 S 4 S 5 r 1 h 1 h 2 r 2 h 3 h 4 r 3 h 5 h 6 r 4 h 7 h 8 S 1 S 4 S 2 S 5 S 2 S 5 S 2 S 5 S 2 S 5 S 2 S 5 S 1 S 4
50. MINHASH S 1 S 2 S 3 S 4 S 5 r 1 h 1 h 2 r 2 h 3 h 4 r 3 h 5 h 6 r 4 h 7 h 8 S 1 S 4 S 2 S 5 S 2 S 5 S 2 S 5 S 1 S 4 S 2 S 5 S 2 S 5 S 1 S 4
51. MINHASH • PROBABILIDADE DE UM PAR SER ESCOLHIDO DEPENDE DA SIMILARIDADE ENTRE OS CONJUNTOS
52. MINHASH • PROBABILIDADE DE UM PAR SER ESCOLHIDO DEPENDE DA SIMILARIDADE ENTRE OS CONJUNTOS
53. MINHASH • 42 OBRAS DE SHAKESPEARE • 84 DOCUMENTOS NO TOTAL • K = 512
54. SIMHASH
55. SIMHASH
56. SIMHASH r⃗ u⃗ v⃗
57. SIMHASH • FUNÇÃO DE HASH DEFINIDA POR VETOR ALEATÓRIO • ESTIMATIVA DO MENOR ÂNGULO ENTRE DOIS VETORES
58. SIMHASH • REPRESENTAÇÃO COMPACTA • COMPUTAÇÃO EFICIENTE • REPRESENTA MULTICONJUNTOS FACILMENTE
60. HYPERLOGLOG [FFGM08] Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm. DMTCS Proceedings, (1), 2008.
61. É COMO ESTIMAR O NÚMERO DE PESSOAS EM UMA MULTIDÃO PELA ALTURA DA MAIOR PESSOA
62. HYPERLOGLOG • BASEIA-SE NA OBSERVAÇÃO DO PADRÃO DE BITS
63. HYPERLOGLOG 0 0 0 0 0 0 0 0
64. HYPERLOGLOG A 0 0 0 3 0 0 0 0 01000101
65. HYPERLOGLOG B 0 0 0 3 0 0 1 0 11010011
66. HYPERLOGLOG C 0 0 0 5 0 0 1 0 01000001
67. HYPERLOGLOG C 0 0 0 5 0 0 1 0 01000001 CADA POSIÇÃO NESTE ARRAY DE EXEMPLO USA APENAS 3 BITS
68. HYPERLOGLOG C 0 0 0 5 0 0 1 0 01000001
69. HYPERLOGLOG • SE O VALOR ESTIMADO FOR MUITO BAIXO (<2.5M), USA- SE LINEAR COUNTING NO MESMO VETOR • A ESTIMATIVA TEM UM VIÉS MULTIPLICATIVO CONSTANTE QUE PRECISA SER CORRIGIDO
70. “LOGLOG” VEM DA QUANTIDADE DE MEMÓRIA NECESSARIA PARA CADA SUBFLUXO. LOGLOG(2^32) = 5 BITS
71. HYPERLOGLOG++
72. HYPERLOGLOG++
73. COMO ENGENHEIROS RESOLVEM PROBLEMAS: goo.gl/iU8Ig 18 PÁGINAS DE CONSTANTES
74. HYPERLOGLOG
75. HYPERLOGLOG • 42 OBRAS DE SHAKESPEARE
76. OPERAÇÕES SOBRE HYPERLOGLOGS
77. INTERSEÇÃO DE HYPERLOGLOGS • IDEIA SIMPLES • O PROBLEMA
78. INTERSEÇÃO DE HYPERLOGLOGS • MINHASH × HYPERLOGLOG • ERRO CONTROLADO
79. • SÃO MUITO IMPORTANTES QUANDO HÁ RESTRIÇÃO DE RECURSOS • ÁREA DE PESQUISA RECENTE • ATRAI MUITO INTERESSE DOS BIG PLAYERS • IMPLEMENTAR É MAIS SIMPLES QUE EXPLICAR ESTRUTURAS PROBABILÍSTICAS
80. SLIDES, LINKS E DEMOS TWITTER E GITHUB PERGUNTAS?
81. OBRIGADO!