Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
Aleatoriedade no Coração dos Algoritmos do Futuro
Search
Juan Lopes
March 29, 2016
Technology
1.1k
1
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
Aleatoriedade no Coração dos Algoritmos do Futuro
Juan Lopes
March 29, 2016
Transcript
81 slides
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!
More Decks by Juan Lopes
See All by Juan Lopes
Estruturas de dados que suportam 300 mil jogadores simultâneos
juanplopes
1
240
ESTRUTURAS DE DADOS PROBABILÍSTICAS PARA REPRESENTAÇÃO DE GRAFOS GIGANTES
juanplopes
0
130
Sketching data structures for massive graph problems
juanplopes
0
640
Big Graph: Big Data aplicado a grafos gigantes e dinâmicos
juanplopes
0
760
Representações implícitas probabilísticas de grafos
juanplopes
0
430
Nubank Machine Learning Meetup
juanplopes
1
320
Lucene Escala? Full-text para Big Data com hardware modesto
juanplopes
2
900
Algoritmos no Fronte de Batalha
juanplopes
1
240
Other Decks in Technology
See All in Technology
Re:ゼロから始めるシェアハウスのペットな鯖
silmin_
0
250
エンタープライズ事業未経験のデータ屋、 AI時代にN回撃沈する.pdf
ryoskdara_
0
150
速くなるほど、深く考える AI時代のQAに学ぶ
kobayashiyorimitsu
0
270
HTTP通信に使おうとすると実はめんどくさいfile_get_contents
maguroalternative
0
220
常時稼働エージェントの作り方(Claude公式ブログを資料化)
minorun365
PRO
16
28k
AWS Client VPNの設定でハマったポイントとその過程での気づき
amarelo_n24
1
400
業務の傍らで進める改善ループエンジニアリング
bengo4com
1
200
DevOps Agentにあらゆるセキュリティインシデントのトリアージを任せた件
jirtosterone
1
190
CloudTrail を推したい
kazzpapa3
1
140
人間+AIを「チーム」としてプロセスを再設計する
littlehands
4
3.5k
共通基盤の実装に Kotlin - Quarkus を選定した理由と採用したアーキテクチャ
nealle
1
140
異夢同船〜異なる夢でも同じ船でなんとかする〜
fortegp05
1
530
Featured
See All Featured
Leadership Guide Workshop - DevTernity 2021
reverentgeek
1
430
Product Roadmaps are Hard
iamctodd
55
13k
A better future with KSS
kneath
240
18k
Beyond borders and beyond the search box: How to win the global "messy middle" with AI-driven SEO
davidcarrasco
3
300
Building Flexible Design Systems
yeseniaperezcruz
330
41k
Music & Morning Musume
bryan
48
7.5k
Unsuck your backbone
ammeep
672
58k
A Modern Web Designer's Workflow
chriscoyier
699
190k
Agile that works and the tools we love
rasmusluckow
331
22k
Believing is Seeing
oripsolob
1
280
Exploring the Power of Turbo Streams & Action Cable | RailsConf2023
kevinliebholz
37
6.7k
Marketing to machines
jonoalderson
1
6k