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
970
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
540
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
LLMアプリケーション開発におけるセキュリティリスクと対策 / LLM Application Security
flatt_security
7
1.9k
How to achieve interoperable digital identity across Asian countries
fujie
0
120
神回のメカニズムと再現方法/Mechanisms and Playbook for Kamikai scrumat2025
moriyuya
4
540
about #74462 go/token#FileSet
tomtwinkle
1
330
コンテキストエンジニアリングとは? 考え方と応用方法
findy_eventslides
4
900
リーダーになったら未来を語れるようになろう/Speak the Future
sanogemaru
0
280
成長自己責任時代のあるきかた/How to navigate the era of personal responsibility for growth
kwappa
3
270
PLaMoの事後学習を支える技術 / PFN LLMセミナー
pfn
PRO
9
3.8k
OpenAI gpt-oss ファインチューニング入門
kmotohas
2
970
定期的な価値提供だけじゃない、スクラムが導くチームの共創化 / 20251004 Naoki Takahashi
shift_evolve
PRO
3
300
多様な事業ドメインのクリエイターへ 価値を届けるための営みについて
massyuu
0
220
Escaping_the_Kraken_-_October_2025.pdf
mdalmijn
0
130
Featured
See All Featured
How to Ace a Technical Interview
jacobian
280
24k
Fantastic passwords and where to find them - at NoRuKo
philnash
52
3.4k
Mobile First: as difficult as doing things right
swwweet
224
10k
Understanding Cognitive Biases in Performance Measurement
bluesmoon
29
2.6k
Scaling GitHub
holman
463
140k
We Have a Design System, Now What?
morganepeng
53
7.8k
Refactoring Trust on Your Teams (GOTO; Chicago 2020)
rmw
35
3.2k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
252
21k
Helping Users Find Their Own Way: Creating Modern Search Experiences
danielanewman
30
2.9k
Balancing Empowerment & Direction
lara
4
680
[RailsConf 2023 Opening Keynote] The Magic of Rails
eileencodes
31
9.7k
Dealing with People You Can't Stand - Big Design 2015
cassininazir
367
27k
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!