Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Aleatoriedade no Coração dos Algoritmos do Futuro
Search
Juan Lopes
March 29, 2016
Technology
1
990
Aleatoriedade no Coração dos Algoritmos do Futuro
Juan Lopes
March 29, 2016
Tweet
Share
More Decks by Juan Lopes
See All by Juan Lopes
Estruturas de dados que suportam 300 mil jogadores simultâneos
juanplopes
1
200
ESTRUTURAS DE DADOS PROBABILÍSTICAS PARA REPRESENTAÇÃO DE GRAFOS GIGANTES
juanplopes
0
100
Sketching data structures for massive graph problems
juanplopes
0
550
Big Graph: Big Data aplicado a grafos gigantes e dinâmicos
juanplopes
0
660
Representações implícitas probabilísticas de grafos
juanplopes
0
340
Nubank Machine Learning Meetup
juanplopes
1
260
Lucene Escala? Full-text para Big Data com hardware modesto
juanplopes
2
820
Algoritmos no Fronte de Batalha
juanplopes
1
220
Other Decks in Technology
See All in Technology
AI連携の新常識! 話題のMCPをはじめて学ぶ!
makoakiba
0
140
アウトプットから始めるOSSコントリビューション 〜eslint-plugin-vueの場合〜 #vuefes
bengo4com
3
1.8k
AI-Readyを目指した非構造化データのメダリオンアーキテクチャ
r_miura
1
340
serverless team topology
_kensh
3
240
AI時代の開発を加速する組織づくり - ブログでは書けなかったリアル
hiro8ma
2
330
頭部ふわふわ浄酔器
uyupun
0
230
AWS re:Invent 2025事前勉強会資料 / AWS re:Invent 2025 pre study meetup
kinunori
0
650
webpack依存からの脱却!快適フロントエンド開発をViteで実現する #vuefes
bengo4com
4
3.6k
AIの個性を理解し、指揮する
shoota
1
220
「タコピーの原罪」から学ぶ間違った”支援” / the bad support of Takopii
piyonakajima
0
150
【SORACOM UG Explorer 2025】さらなる10年へ ~ SORACOM MVC 発表
soracom
PRO
0
160
OTEPsで知るOpenTelemetryの未来 / Observability Conference Tokyo 2025
arthur1
0
280
Featured
See All Featured
Building a Scalable Design System with Sketch
lauravandoore
463
33k
Documentation Writing (for coders)
carmenintech
75
5.1k
Fantastic passwords and where to find them - at NoRuKo
philnash
52
3.5k
Code Reviewing Like a Champion
maltzj
526
40k
I Don’t Have Time: Getting Over the Fear to Launch Your Podcast
jcasabona
34
2.5k
Building Better People: How to give real-time feedback that sticks.
wjessup
369
20k
Build your cross-platform service in a week with App Engine
jlugia
233
18k
How STYLIGHT went responsive
nonsquared
100
5.9k
The Cost Of JavaScript in 2023
addyosmani
55
9.1k
How to Think Like a Performance Engineer
csswizardry
27
2.1k
XXLCSS - How to scale CSS and keep your sanity
sugarenia
249
1.3M
"I'm Feeling Lucky" - Building Great Search Experiences for Today's Users (#IAC19)
danielanewman
230
22k
Transcript
None
MACHINE LEARNING RESOLVE MUITA COISA MAS NÃO É SEMPRE A
MELHOR SOLUÇÃO.
DETECTAR PLÁGIO EM BILHÕES DE TEXTOS
DETECTAR SIMILARIDADE EM BANCOS DE DADOS DE IMAGENS
ESTIMAR INTERSEÇÃO DE CONJUNTOS, SEM PRECISAR TÊ-LOS PRÓXIMOS GEOGRAFICAMENTE.
ALEATORIEDADE NO CORAÇÃO DOS ALGORITMOS DO FUTURO
• PAI DO MIGUEL • BACHAREL E QUASE MESTRE •
PROGRAMADOR • VICIADO EM COMPETIÇÕES QUEM É JUAN LOPES?
SLIDES, LINKS E DEMOS TWITTER E GITHUB
ALGORITMOS RANDOMIZADOS
• HASHTABLES • GERAÇÃO DE PARES DE CHAVES CRIPTOGRÁFICAS •
RANDOMIZED QUICKSORT ALGORITMOS RANDOMIZADOS
None
RANDOMIZED ALGORITHMS
None
INTRODUÇÃO AOS ALGORITMOS RANDOMIZADOS
MINING OF MASSIVE DATASETS
ALGORITMOS RANDOMIZADOS PROBABILÍSTICOS
VAMOS FALAR DE POLÍTICA?
QUAL É A BASE TEÓRICA DE UMA PESQUISA ELEITORAL?
QUAL É A BASE TEÓRICA DE UMA ESTIMATIVA DE PARTICIPANTES?
PROBABILIDADE E ESTATÍSTICA
VARIÁVEL ALEATÓRIA X
VARIÁVEL ALEATÓRIA X ROLAGEM DE DADO DE 6 LADOS
ESTIMADORES NÃO- ENVIESADOS
COMO CRIAR UMA VARIÁVEL ALEATÓRIA QUE ESTIME ALGUM VALOR IMPORTANTE?
A OPINIÃO DE UM INDIVÍDUO ALEATÓRIO EM UMA POPULAÇÃO É
UM ESTIMADOR DA OPINIÃO DA POPULAÇÃO
A QUANTIDADE DE PESSOAS EM UM TRECHO DE UMA MANIFESTAÇÃO
É UM ESTIMADOR DO NÚMERO TOTAL DE PESSOAS
COMPOSIÇÃO DE ESTIMADORES DIMINUI A VARIÂNCIA
• FILTRO DE BLOOM [Blo70] • CM-SKETCH [CM05] • MINHASH
[Bro97] • HYPERLOGLOG [FFGM08] ESTRUTURAS PROBABILÍSTICAS
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]
– DONALD KNUTH HASH FUNCTIONS
HASH FUNCTIONS x h(x) 0: 50% 1: 50% 0: 50%
1: 50% 0: 50% 1: 50% …
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.
MINHASH • VARIÁVEL DE BERNOULLI • ÍNDICE DE JACCARD •
DUAS VARIANTES
MINHASH, COM CALMA A B
A B MINHASH, COM CALMA
A B A B MINHASH, COM CALMA
CALMA!
MINHASH • CADA FUNÇÃO DEFINE UM ESTIMADOR NÃO-ENVIESADO • MÚLTIPLAS
FUNÇÕES DE HASH • COMPARAÇÃO DOS VALORES DE CADA ASSINATURA
MINHASH • ASSINATURA DEFINIDA POR K MENORES VALORES • TAMBÉM
É VARIÁVEL DE BERNOULLI • COMPARAÇÃO DOS VALORES DE CADA ASSINATURA
MINHASH • PODE SER 1 COM PROBABILIDADE p E 0
COM PROBABILIDADE 1-p
MINHASH
MINHASH • 42 OBRAS DE SHAKESPEARE • 84 DOCUMENTOS NO
TOTAL • 0 ≤ K ≤ 1000
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
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 }
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
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
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
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
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
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
MINHASH • PROBABILIDADE DE UM PAR SER ESCOLHIDO DEPENDE DA
SIMILARIDADE ENTRE OS CONJUNTOS
MINHASH • PROBABILIDADE DE UM PAR SER ESCOLHIDO DEPENDE DA
SIMILARIDADE ENTRE OS CONJUNTOS
MINHASH • 42 OBRAS DE SHAKESPEARE • 84 DOCUMENTOS NO
TOTAL • K = 512
SIMHASH
SIMHASH
SIMHASH r⃗ u⃗ v⃗
SIMHASH • FUNÇÃO DE HASH DEFINIDA POR VETOR ALEATÓRIO •
ESTIMATIVA DO MENOR ÂNGULO ENTRE DOIS VETORES
SIMHASH • REPRESENTAÇÃO COMPACTA • COMPUTAÇÃO EFICIENTE • REPRESENTA MULTICONJUNTOS
FACILMENTE
None
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.
É COMO ESTIMAR O NÚMERO DE PESSOAS EM UMA MULTIDÃO
PELA ALTURA DA MAIOR PESSOA
HYPERLOGLOG • BASEIA-SE NA OBSERVAÇÃO DO PADRÃO DE BITS
HYPERLOGLOG 0 0 0 0 0 0 0 0
HYPERLOGLOG A 0 0 0 3 0 0 0 0
01000101
HYPERLOGLOG B 0 0 0 3 0 0 1 0
11010011
HYPERLOGLOG C 0 0 0 5 0 0 1 0
01000001
HYPERLOGLOG C 0 0 0 5 0 0 1 0
01000001 CADA POSIÇÃO NESTE ARRAY DE EXEMPLO USA APENAS 3 BITS
HYPERLOGLOG C 0 0 0 5 0 0 1 0
01000001
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
“LOGLOG” VEM DA QUANTIDADE DE MEMÓRIA NECESSARIA PARA CADA SUBFLUXO.
LOGLOG(2^32) = 5 BITS
HYPERLOGLOG++
HYPERLOGLOG++
COMO ENGENHEIROS RESOLVEM PROBLEMAS: goo.gl/iU8Ig 18 PÁGINAS DE CONSTANTES
HYPERLOGLOG
HYPERLOGLOG • 42 OBRAS DE SHAKESPEARE
OPERAÇÕES SOBRE HYPERLOGLOGS
INTERSEÇÃO DE HYPERLOGLOGS • IDEIA SIMPLES • O PROBLEMA
INTERSEÇÃO DE HYPERLOGLOGS • MINHASH × HYPERLOGLOG • ERRO CONTROLADO
• 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
SLIDES, LINKS E DEMOS TWITTER E GITHUB PERGUNTAS?
OBRIGADO!