Benzersiz öğe sayısını verimli biçimde sayan yeni algoritma

 (quantamagazine.org)
2 puan yazan GN⁺ 2024-05-17 | 1 yorum | WhatsApp'ta paylaş
  • CVM algoritması, uzun veri akışlarında farklı öğe sayısını yaklaşık olarak hesaplayarak tüm listeyi saklamadan benzersiz öğe sayısını tahmin eder
  • Tüm girdinin belleği aştığı benzersiz öğeler problemi (distinct elements problem) üzerine odaklanır ve çok sayıda yinelenen girdi içeren büyük ölçekli loglar veya olay akışlarına uygulanabilir
  • Sınırlı bellekte yalnızca bazı öğeleri tutup alan doldukça rastgele silme işlemini tekrarlayarak, her öğenin elde kalma olasılığını eşitler
  • Hamlet örneğinde, 100 kelimelik bellekle 5 çalıştırmanın ortalamasında 3.955 tahmini elde edildi; bu, gerçek benzersiz kelime sayısı olan 3.967'ye yakındı. 1.000 kelimelik bellekte ortalama 3.964'e yükseldi
  • Bellek büyüdükçe doğruluk artar ve tüm benzersiz öğeleri tutacak kadar yeterliyse %100 doğruluk da mümkündür

Uzun veri akışlarında benzersiz öğeleri saymak

  • Amaç, öğelerin teker teker geldiği uzun bir listede yinelenenleri çıkardıktan sonraki benzersiz öğe sayısını verimli biçimde tahmin etmektir
  • En basit yöntem, şimdiye kadar görülen tüm öğeleri saklamak ve yeni bir öğe geldiğinde onu mevcut listeyle karşılaştırmaktır
    • Yaban hayatı araştırmalarında, daha önce görülen hayvan fotoğrafları listesini sürekli kontrol etmek gerekir
    • Facebook'un günlük giriş yapan kullanıcı sayısı gibi listeler milyarlarca öğeye ulaştığında, saklama ve karşılaştırma zorlaşır
  • CVM, adını Sourav Chakraborty, Vinodchandran Variyam ve Kuldeep Meel'den alan bir algoritmadır
  • Kelimeler, konveyör banttaki ürünler veya otoyoldaki araçlar gibi öğelerin sıralı biçimde geldiği listelere uygulanabilir

CVM algoritmasının temel fikri

  • CVM, tüm öğeleri saklamak yerine yalnızca sınırlı belleğe sığan bir alt kümeyi tutar
  • Her benzersiz öğenin son listede kalma olasılığını denetlemek için rastgelelik kullanır
  • Andrew McGregor, bu algoritmanın çok basit ve uygulamasının kolay olduğunu, bu yüzden gerçek dünyadaki benzersiz öğeler problemi için temel bir yaklaşım haline gelebileceğini düşünüyor

Hamlet örneğiyle çalışma biçimi

  • Hamlet'te toplam 30.557 kelime vardır ve algoritma bunların içindeki benzersiz kelime sayısını tahmin eder
  • Belleğin 100 kelimelik bir beyaz tahta olduğunu varsayarsak, başlangıçta yinelenen kelimeler atlanarak ilk 100 benzersiz kelime yazılır
  • Alan dolduğunda her kelime için yazı tura atılır
    • Yazı gelirse kelime tutulur
    • Tura gelirse kelime silinir
    • Bu ön aşamadan sonra yaklaşık 50 benzersiz kelime kalır

Turlar ilerledikçe zorlaşan elde tutma koşulu

    1. Tur'da yeni kelimeler eklenmeye devam edilir; listede zaten bulunan bir kelime yeniden gelirse yazı tura atılır ve tura gelirse silinir
  • Liste yeniden 100 kelimeye ulaştığında, 100 yazı tura sonucuna göre yaklaşık yarısı silinir ve 1. Tur sona erer
    1. Tur'dan itibaren kelimelerin hayatta kalması zorlaşır
    • Yinelenen bir kelime gelirse, tura gelirse silinir
    • Yazı gelirse bir kez daha yazı tura atılır ve yalnızca ikinci kez de yazı gelirse tutulur
  • Üçüncü turda art arda 3 kez yazı gelmesi gerekir; dördüncü turda ise art arda 4 kez yazı gelmesi gerekir
  • Genel olarak, k'inci turun sonunda her kelimenin kalma olasılığı 1/2^k olur

Tahminin hesaplanması ve deney sonuçları

  • Son listede kalan kelime sayısı, kalma olasılığına bölünerek toplam benzersiz kelime sayısı tahmin edilir
  • Örneğin 6 turun ardından 61 kelime kaldıysa, 1/2^6 olasılığına bölünerek 3.904 tahmini elde edilir
  • Hamlet'teki gerçek benzersiz kelime sayısı 3.967'dir
  • Bellek boyutu büyüdükçe tahmin, gerçek değere yaklaşır
    • 100 kelimelik bellekte 5 çalıştırmanın ortalama tahmini 3.955'tir
    • 1.000 kelimelik bellekte ortalama tahmin 3.964'tür
  • Variyam ve çalışma arkadaşları, bu tekniğin doğruluğunun bellek boyutuna göre nasıl ölçeklendiğini matematiksel olarak kanıtladı

Basit ama sıradan olmayan bir çözüm

  • CVM, 40 yılı aşkın süredir araştırılan benzersiz öğeler problemi için önemli bir ilerleme olarak değerlendiriliyor
  • William Kuszmaul, çok temel ve iyi incelenmiş problemlerde bile basit ama kolayca akla gelmeyen çözümlerin hâlâ bulunabileceğini düşünüyor

İlgili okumalar

1 yorum

 
GN⁺ 2024-05-17
Hacker News yorumları

  • Bu algoritmanın DNF hacim sayma sürümünün uygulanmasında yazarlarla birlikte yer aldım. İlgili yazı burada: https://www.msoos.org/2023/09/pepin-our-probabilistic-approx...
    Kod burada: https://github.com/meelgroup/pepin
    Algoritma akıl almaz derecede hızlı; öyle ki çoğu zaman toplam sürenin %30'u dosya okuma G/Ç'sine gidiyor. Bu arada Knuth da algoritmaya katkıda bulundu; notları burada: https://cs.stanford.edu/~knuth/papers/cvm-note.pdf
    TAOCP çalışmalarından koca bir ay ayırıp bunu yaptı ve tahmin edeceğiniz gibi inanılmaz derecede iyiydi

    • Gerçekten ilginç; olağanüstü yetenekli insanlara çok ilgi duyuyorum. Knuth'un size neden bu kadar etkileyici geldiğini merak ediyorum. Özel bir an mı vardı, fikirleri kavrama hızı mıydı, yoksa kolayca açıklayabilme becerisi mi?
    • Bu aptalca görünüyor. Hem de çok aptalca; acaba bir şeyi mi kaçırıyorum? Bu sayma değil, sadece örnekleme; gerçekten tüm farklı kelimeleri saymak istiyorsanız, basitçe saymaya kıyasla bellek kullanımının değişmediği anlaşılıyor
    • Muhtemelen biliyorsunuzdur ama neden daha büyük sayımlara öncelik verecek şekilde sıralayıp dolunca alt yarıyı atma yönteminin seçilmediğini merak ediyorum. Başkalarına obvious gelebilir ama nedenini bilmek isterim
    • Bu algoritmanın başlıca kullanım alanlarının ne olduğunu merak ediyorum
    • Artık Knuth'un bir sonraki kitabının gecikmesinden sorumlu tutabileceğimiz biri var demek :)

  • Bu algoritma, makalede de atıf yapılan HyperLogLog'a benziyor. Tahmini elde etmek için yazı/tura sonuçlarının art arda gelmesini izleme yönündeki aynı içgörüyü kullanıyor; ama fikri tersine çevirip, hatırlanan değerleri para atışı sonuçlarının sürekliliğine göre atan daha basit bir algoritmaya dönüştürmüş gibi
    Akış durumlarında özellikle verimli çalışıyor; hata payı olsa da farklı öğe sayısını sayan “sayaç” benzeri bir şeyi tutabiliyorsunuz
    HyperLogLog'un avantajı, bir bakıma hash kümesi gibi davranması. Öğe ekleyebilir, farklı öğe sayısını sayabilir ve önemlisi iki HLL'yi birleştirerek birleşim oluşturabilirsiniz; üstelik milyarlarca öğelik kümelerde bile bellek birkaç KB'de sabit kalır. Dağıtık veri depolarında Elasticsearch/OpenSearch'ün cardinality agg'i, Redis/Redict'in PFADD/PFMERGE/PFCOUNT'u bu numarayı kullanır
    CVM algoritmasının HLL ile tam olarak nasıl karşılaştırıldığını pek bilmiyorum ama Knuth tarafından incelenmiş ve bir lisans öğrencisinin bile kolayca uygulayabileceği söyleniyor; bu yüzden epey iyi bir algoritma gibi görünüyor

    • HLL, iki HLL'nin hem birleşimini hem de kesişimini tahmin edebildiği için join'lerin kardinalite tahmininde de kullanılabilir
      http://oertl.github.io/hyperloglog-sketch-estimation-paper/
    • Bu veri yapıları da birleştirilebilir. Birleştirilecek iki örneğin “tur”u farklıysa, daha erken turda olanı tur farkı kadar ilerletmek yeterli. Yani rastgele yarısını atarsınız. Sonra bir listenin değerlerini diğer listeye koyar ve tekrarları yok sayarsınız. Sonuç çok büyükse rastgele yarısını atıp tur numarasını artırabilirsiniz
      Önceki işimde tam olarak bu algoritmayı uygulamıştım; her değerin yanında, o değerin kaç kez göründüğüne dair bir tahmini de saklıyordum. Böylece en sık görülen değerlerin yaklaşık bir listesini ve her değerin tahmini sayımını oluşturabiliyorduk
    • Eski okul bilgileri aklıma geliyor; burada bahsedilen HLL ve CVM'in, eskiden öğrendiğimiz reservoir sampling ile ilişkisi nedir?
      Bir zamanlar hastanede çalışırken, DAT teyp üzerinde saklanan kayıtların küçük bir alt kümesini oluşturmak için reservoir sampling kullanmıştım

  • Makaleyi okumak, bir blog yazısını okumakla neredeyse aynı süreyi aldı ve makale daha yararlıydı
    https://arxiv.org/pdf/2301.10191
    Bir akıştan gelen öğe kümesinin kardinalitesini tahmin etmekle ilgili. Algoritma o kadar basit ki makaleyi okurken kendiniz kodlayıp üzerinde oynayabilirsiniz
    Yazarlar bu algoritmanın hedef kitlesinin ve amacının lisans öğrencileri ve ders kitapları olduğunu açıkça belirtiyor

    • Makalenin alt başlığı “An Algorithm for the (Text) Book”, basitliği ve güzelliği o kadar zarif ki “The Book’tan çıkmış” bir kanıt gibi olduğunu anlatan Paul Erdős’ün ünlü ifadesine gönderme yapıyor gibi
      Knuth bizzat incelemiş olduğuna göre, bu algoritmanın o türden olduğunu söylemiş olabilir. Öyleyse yazarların bunu başlığa koyması pek mütevazı olmayan bir övünme gibi görünüyor, ama bunu fazlasıyla hak ediyor
      Aslında bu ifadeyi Knuth’un söylediğini hatırlıyordum, meğer hafızam yanılmış
    • Blog yazısının yarısından fazlası dolgu gibiydi. Algoritmanın uzun bir blog yazısı çıkarmayı zorlaştıracak kadar basit olması aslında iyi bir şey
    • Makalenin blog yazısından daha iyi olduğuna katılıyorum, ama CVM makalesine yönelik bir eleştirim sonlandırma koşulu koyması. Diğer başlıkta geçen Knuth’un CVM notu, rezervuarı yarıya indirme adımında daha fazla alan açılması için sadece bir döngü kullanıyor
      https://en.wikipedia.org/wiki/Up_tack’i açıklamaktansa doğrudan döngü kullanmak daha az zahmetli görünüyor. [1]
      [1] https://news.ycombinator.com/item?id=40388878
    • Eskiden bilgisayar bilimiyle uğraşıyordum ama beynim mi düzleşti bilmiyorum; bu gereğinden fazla kafa karıştırıcı görünüyor
      Öncelikle contradiction işlemesi bildiğin hata ya da panic gibi duruyor; neden öyle ifade ettiklerini anlamadım. Ayrıca 1..m varsayımı kafa karıştırıcı. Boyutu önceden bilmek gerekip gerekmediğinden emin olamadım; devamını okuyunca gerekmiyor gibi duruyor. Bir eşik değeri seçiliyor ve akış boyutuna göre olasılık değişiyor, ama algoritma açıklaması tek bir çıktısı varmış gibi yazıldığı için karışıyor
      Chernoff sınırı ve delta/epsilon da makalede hiç açıklanmadığından daha da kafam karıştı. Go ile yaptığım uygulama burada: https://github.com/betamos/distinct
      Eşik değeriyle ilgili kısmı bir helper’a çıkarmak, yanlışlıkla fazla bellek ayırmaktan çok daha mantıklı. Güvenilirliği ya da hata oranını tahmin eden metotlar da olmalı gibi. Akış boyutunu kimse önceden bilmediğine göre, bu değeri ilerledikçe güncellemek daha doğal
    • “Lisans öğrencileri ve ders kitapları için” sözleri, onların kullanabileceği kadar basit olduğu anlamına değil de gerçekten yalnızca orada işe yaradığı anlamına geliyorsa, uzmanlar için neden yararlı olmadığını ama lisans öğrencileri için yararlı olduğunu açıklasalar iyi olurdu

  • Makalenin konusu düşünüldüğünde dipnot özellikle hoş
    Yazarlar, eski yazar adlarını alfabetik sıralama geleneği yerine rastgele sıralamayı seçmiş ve bunu r⃝ ile işaretlemişler. Rastgeleleştirmenin herkese açık doğrulanabilir kaydı burada: https://www.aeaweb.org/journals/policies/random-author-order...
    [0]: https://arxiv.org/pdf/2301.10191

  • Algoritma açıklaması hatalı gibi değil mi?
    “Listede zaten olan bir kelimeyle karşılaşırsan tekrar yazı tura at, tura gelmezse kelimeyi sil” açıklamasına göre “listede olup olmadığını kontrol ettikten sonra silme” şeklinde uygularsan yaklaşık 20 yineleme yapıyor ve tahmin 772800512 gibi saçma bir değer çıkıyor
    Tersine, kelimeyi önce kaydedip sonra aynı kelimeyi silersen gerçek benzersiz kelime sayısı 7233’e yakın, 7240 çıkıyor. Yani açıklamada sıra önemli ama yanlış aktarılmış gibi

    • Aynı sorunu yaşadım. Quanta Magazine açıklamasına bakıp arxiv makalesine bakmadan uygularsan hep 461746372167462146216468796214962164 gibi tahminler çıkıyordu
      Makaleyi okuduktan sonra doğru tahminler geldi; sorun küçücük tek bir else imiş. Quanta açıklaması “listede yoksa ekle, aksi halde olasılığa göre kaldır” gibi okunuyor, oysa doğru uygulama, eklenip eklenmediğinden bağımsız olarak ardından olasılık koşulunu uygulamak
    • Az önce çözmeye çalışırken başkası da aynı sorunu yaşamış mı diye bakmaya geldim; evet. Açıklandığı gibi yapınca yanlış oluyor; her turda yeni değeri ekleyip sonra olasılıksal olarak budamak ve bellek sınıra ulaşınca tüm kümeden rastgele yarısını kaldırmak şeklinde uygulamak gerekiyor

  • Bir kümedeki benzersiz öğe sayısını tahmin etmek ile bir kümedeki benzersiz öğe sayısını saymak çok farklı şeyler. Harika bir yöntem ama başlık pek iyi değil

    • O kadar da farklı değiller. Gerçek dünyadaki tüm sayma yöntemlerinin sıfır olmayan bir hata oranı vardır; bu yüzden çoğu bağlamda iki terim birbirinin yerine kullanılır
      Örneğin seçimlerde “oylar sayılır” deriz, ama yarış başa başsa “yeniden sayım” yapılır ve asıl sayımdan biraz farklı bir sayı çıkması gayet beklenir. O halde oy saymak da aslında oy tahminidir; yeniden sayım ise daha dar hata sınırına sahip bir tahminden ibarettir
      “countless stones” efsanesi (https://en.wikipedia.org/wiki/Countless_stones) de, büyük, sert ve durağan dikili taşlar gibi şeylerin bile doğru sayıldığından fazla emin olmamak gerektiğini hatırlatan halk işi bir uyarı gibi geliyor
      Saymanın tahmin olmadığı durumlar daha çok matematiksel durumlarla sınırlı. Tüm öğeleri eksiksiz ele aldığınızı ve hiçbir öğenin kimliğini bir başkasıyla karıştırmadığınızı garanti edebildiğiniz durumlar
    • Nispeten küçük sayılarda doğru. Ama çok büyük sayılarda tahmin genellikle sayma ile eşdeğer kabul edilir; sonuç da tam sayı olarak değil, bilimsel gösterimle, yani kayan noktalı sayı gibi ifade edilebilir
      Örneğin mol bir tam sayıdır ama değeri yalnızca yaklaşık olarak bilinir ve kesin değerini önemseyen de yoktur
    • Bu estimation değil, approximation

  • Bu tür kalıpların dışında düşünme örneklerini gerçekten seviyorum. Mesleki olarak da pek iyi olmadığım bir alan olduğu için daha da öyle. Önemli olan yalnızca bir problemi çözmenin doğru yolunu öğrenmek değil; elinizdeki problemi daha kolay, bazen de mümkün hâle getirecek soruyu bulma süreci.
    Burada kilit soru şu: “Kesin sayıya ihtiyacım yok; tanımlanmış parametreler içinde olasılıksal bir aralık belirlemem yeterli.” Başka problemlerde başka sorular olacaktır. Bu tür örnekleri yeterince görürsem düşünme sürecini içselleştirip doğru şekilde uygulayabilmeyi umuyorum.

    • Adil olmak gerekirse, bunu bir üniversite araştırma ekibi yaptı. Kelimenin tam anlamıyla bütün gün tek bir konuyu bilimsel yöntemle tekrar tekrar gözden geçirebilen insanlardan oluşan bir ekip.
      Büyük bir şirkette aynı derecede zeki mühendislerle bütün gün beyaz tahta başında oturmanız için para alsaydınız, dünyanın geri kalanına “kalıpların dışında bir çözüm” gibi görünecek bir şeyi mutlaka ortaya çıkarabilirdiniz.
      Ama çoğumuz JIRA fabrika hattında çalışmamız için para aldığımızdan, tek bir probleme takılıp deney yapabileceğimiz zaman sınırlı.
    • Buna genelde lateral düşünme deniyor sanırım. Edward de Bono bu konuda birkaç kitap yazdı; ilginizi çekebilir.

  • “Facebook’ta her gün giriş yapan farklı kullanıcı sayısını saymak istiyorsanız ve bazı kullanıcılar birden fazla cihazdan ve farklı zamanlarda giriş yapıyorsa?” örneği, bu algoritmanın gerçekten yararlı olduğu bir durum için pek iyi görünmüyor.
    Giriş sürecini tasarlarken bu bilgiye ihtiyacınız olduğunu zaten biliyorsanız iş basit: Her hesabın son giriş tarihini saklar, saklanan değer geçerli tarihten farklıysa benzersiz kullanıcı sayacını artırırsınız.
    Öyle olmasa bile, daha sonra veritabanından giriş olayları akışını “yeniden oynatıp” analiz edebilirsiniz. Yıllarca birikmiş veriniz varsa durum farklı olabilir.

    • Bu yöntem “her hesabın son giriş tarihi”ni takip etmeyi gerektirir, dolayısıyla kullanıcı sayısı kadar bellek ister. Bu algoritmanın asıl noktası, bunu çok daha küçük ve sabit bellekle yapabilmesidir.

  • Sayma konusuyla bağlantılı olarak, bir akıştaki ilk k öğeyi bulmak için verimli ve uygulaması da kolay bir algoritmadan bahsetmek istiyorum. Sanıldığı kadar bilinmiyor gibi.
    A Simple Algorithm for Finding Frequent Elements in Streams and Bags
    Karp, Shenker & Papadimitriou
    https://www.cs.umd.edu/~samir/498/karp.pdf

    • “Akıştaki ilk k öğe” ifadesi, özetin açıklamasından farklı geliyor. Özet, büyük bir alfabeden gelen çok uzun bir sembol dizisinde frekansı verilen eşikten yüksek olan sembolleri bulmaktan söz ediyor.
      Sizin açıklamanız sabit sayıda k öğe bulmayı ve bunların mutlaka en üsttekiler olduğunu garanti etmeyi anlatıyor gibi. Özet ise belirli bir k değerinden büyük olma koşulunu sağlayan, sayısı önceden bilinmeyen öğeleri bulmaktan söz ediyor gibi.
      Bu bana “en yaşlı 100 kullanıcıyı bulmak” ile “30 yaşın üzerindeki tüm kullanıcıları bulmak” arasındaki fark gibi görünüyor; sizi ya da özeti yanlış mı anladım? İngilizce ana dilim olmadığı için kafam karıştı.

  • Bilgisayar bilimcileri, bir alt kümenin boyutunu bellek açısından verimli biçimde tahmin etmenin bir yolunu icat etmişler demek.

    • Daha az tur yazı tura atarak bir tahmin elde edilebiliyorsa hızlı da görünüyor. Farklı kelime sayısını tahmin etmek için tüm “kitabı” sonuna kadar taramak gerekmeyebilir.
    • Burada alt küme önemli. Tam olarak benzersiz öğelerin alt kümesi.