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
870
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
180
ESTRUTURAS DE DADOS PROBABILÍSTICAS PARA REPRESENTAÇÃO DE GRAFOS GIGANTES
juanplopes
0
91
Sketching data structures for massive graph problems
juanplopes
0
500
Big Graph: Big Data aplicado a grafos gigantes e dinâmicos
juanplopes
0
610
Representações implícitas probabilísticas de grafos
juanplopes
0
300
Nubank Machine Learning Meetup
juanplopes
1
260
Lucene Escala? Full-text para Big Data com hardware modesto
juanplopes
2
790
Algoritmos no Fronte de Batalha
juanplopes
1
210
Other Decks in Technology
See All in Technology
Amazon_CloudWatch_ログ異常検出_導入ガイド
tsujiba
4
1.8k
Microsoft Intune アプリのトラブルシューティング
sophiakunii
1
180
「 SharePoint 難しい」ってよく聞くけど、そんなに言うなら8歳の息子に試してもらった
taichinakamura
2
760
リンクアンドモチベーション ソフトウェアエンジニア向け紹介資料 / Introduction to Link and Motivation for Software Engineers
lmi
4
290k
組み込みLinuxの時系列
puhitaku
2
530
コンテナのトラブルシューティング目線から AWS SAW についてしゃべってみる
kazzpapa3
1
120
"君は見ているが観察していない"で考えるインシデントマネジメント
grimoh
3
520
家具家電付アパートの冷蔵庫をIoT化してみた!
scbc1167
0
140
VPC間の接続方法を整理してみた #自治体クラウド勉強会
non97
1
1k
Microsoft Fabric OneLake の実体について
ryomaru0825
0
120
プロポーザルのつくり方 〜個人技編〜 / How to come up with proposals
ohbarye
4
280
生成AIと知識グラフの相互利用に基づく文書解析
koujikozaki
1
150
Featured
See All Featured
Imperfection Machines: The Place of Print at Facebook
scottboms
264
13k
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
191
16k
The Success of Rails: Ensuring Growth for the Next 100 Years
eileencodes
43
6.6k
The Invisible Side of Design
smashingmag
297
50k
The Cult of Friendly URLs
andyhume
78
6k
Thoughts on Productivity
jonyablonski
67
4.3k
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
14
2k
Music & Morning Musume
bryan
46
6.1k
Art, The Web, and Tiny UX
lynnandtonic
297
20k
jQuery: Nuts, Bolts and Bling
dougneiner
61
7.5k
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
46
2.1k
Put a Button on it: Removing Barriers to Going Fast.
kastner
59
3.5k
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!