Çevrimdışı olarak milyonlarca Wikipedia sayfasını ‘vibe’ ile aramak

 (leebutterman.com)
1 puan yazan GN⁺ 2023-09-03 | 1 yorum | WhatsApp'ta paylaş
  • Sunucu olmadan, tarayıcı içinde çevrimdışı gerçek zamanlı embedding araması uygulanarak English Wikipedia’daki 6 milyon belge yerelde etkileşimli olarak geziliyor
  • 384 boyutlu float32 embedding’lerin ham hali yaklaşık 9GB olduğundan tarayıcı uygulaması için uygun değil; boyut, all-minilm-l6-v2 ve sayfa parçalarının ortalama embedding’leri temel alınarak küçültülüyor
  • Product Quantization, 8 boyutlu altuzay birimleri halinde uygulanarak veri kümesi 288MB seviyesine indiriliyor ve 96MB içine yaklaşık 2 milyon embedding sığdırılabiliyor
  • Arama, sıkıştırmayı açmadan sıkıştırılmış alanda mesafe hesaplaması yapıyor; ONNX’in GatherElements opcode’u ile dönüşüm sonucundaki hesap düzeltilerek yaklaşık 4 kat hız kazanılıyor
  • Güncel cihazlarda MiniLM çıkarımı ve 100k embedding için mesafe hesaplaması kısa sürede tamamlanıyor; React arayüzü sonuçları 100~300ms aralıklarla güncelleyebiliyor

Tarayıcı içinde çalışan çevrimdışı vektör araması

  • Amaç, karmaşık sunucu arama altyapıları olmadan da milyonlarca Wikipedia sayfasının tarayıcıda gerçek zamanlı aranabileceğini göstermek
  • Temel tasarım üç noktada özetleniyor
    • Vektör araması, yalnızca Product Quantization ve doğrusal taramayla bile yeterince hızlı olabilir
    • ONNX Runtime kullanılsa da, PyTorch dönüşümünden doğan verimsizlikler opcode düzeyinde düzeltilebilir
    • Tarayıcı, WASM ile gerçek zamanlı çıkarım yapacak kadar hızlıdır; WebGPU da geleceğe dönük bir olasılık olarak duruyor
  • Arama koşulları, gövde embedding’inin vektör benzerliği ile başlığın ilk harfinin eşitlik koşulunu birlikte kullanıyor
    • Bu, bazı sütunların vektör benzerliğiyle, diğer sütunların ise eşitlik koşuluyla arandığı veritabanı sorgularına daha yakın
  • Çevrimdışı tarayıcı uygulaması kısıtı nedeniyle embedding’lerin küçük olması, embedding modelinin açık kaynak olması, model boyutu ve işlem yükünün de hafif kalması gerekiyor
    • 2023 itibarıyla hafif modeller genelde 100MB altı anlamına geliyor

English Wikipedia verisi ve embedding boyutu

  • Veri kümesi English Wikipedia ve embedding işlemi all-minilm-l6-v2 modeliyle yapılıyor
  • Yaklaşık 6 milyon belge var; sayfalar parçalara bölündükten sonra her parçanın embedding’i ortalanarak sayfa embedding’i oluşturuluyor
  • Sayfalar en uzundan başlayarak yerleştiriliyor
    • Veritabanı kademeli yüklenirken, insanlar tarafından daha çok emek verilmiş olma ihtimali yüksek olan uzun sayfaları önce göstermek için
  • Embedding boyutu 384 boyut
    • float32 olarak saklanırsa 6M * 384 * 4 = 9GB
    • 96MB içine yalnızca yaklaşık 64k embedding sığabiliyor
  • Ham float32 kodlama, tarayıcı tabanlı çevrimdışı arama için fazla büyük kalıyor

Product Quantization ile embedding sıkıştırma

  • Product Quantization, kayan noktalı değerleri doğrudan saklamak yerine birden fazla palet oluşturup giriş değerlerini palet indekslerine dönüştürüyor
  • Paletler genelde en fazla 256 değer içerdiğinden, her indeks en fazla 1 bayt olabilir
    • Örtük paletler, -127~127 veya 0~255 gibi sayı doğrularının kaydırılıp ölçeklenmesiyle kullanılır
    • Açık paletlerde 256 sayı sırayla saklanır
    • Product Quantization, açık paletleme kullanır
  • En temel yapıda 384 boyutun her biri 1 baytlık indekslere çevrilirse veri kümesi 6M * 384 = 2.25GB olur
    • 96MB içine yaklaşık 256k embedding sığdırılabilir
    • Bu yöntem de hedefe göre hâlâ verimsizdir
  • 2 boyutlu noktalar düzeyinde nicemleme yapılırsa 384 boyutlu embedding, 192 indeksle temsil edilebilir ve 2 kat alan tasarrufu sağlanır
  • Gerçek yapılandırma 8 boyutlu noktalar kullanıyor
    • 384 boyut, 48 indeksle temsil ediliyor
    • Palet boyutu yaklaşık 384KB seviyesinde kalıyor
    • Veri kümesi boyutu 6M * 48 = 288M
    • 96MB içine yaklaşık 2 milyon embedding sığdırılabiliyor
  • Her nicemleme düzeyi için precision ve recall ölçülebilir

Sıkıştırmayı açmadan doğrudan arama

  • Product Quantization’ın avantajı, sıkıştırmayı açmadan sıkıştırılmış durumda arama yapılabilmesi
  • n boyut, n/2 adet 2 boyutlu nokta olarak gruplanırsa her palet noktası ile sorgunun ilgili 2 boyutlu noktası arasındaki mesafe önceden hesaplanabilir
  • Sonrasında her embedding, palet indeksleri üzerinden mesafe değerlerini alıp toplayarak toplam mesafeyi hesaplar
    • Bu, önce tüm n boyutlu noktayı geri kurup sonra her boyutta mesafe hesaplamaktan daha az iş gerektirir
  • Gerçek 8 boyutlu nokta yapılandırmasında, mesafe hesaplaması sıkıştırılmamış embedding’lerle çalışmaya göre 1/8 düzeyinde işlem yüküyle yapılabiliyor

Veri alışveriş formatı olarak Arrow kullanımı

  • Veri taşıma ve dönüştürme maliyeti yüksek olduğu için, sıkıştırılmış embedding’leri hemen kullanılabilecek biçimde serileştirmek avantajlı
  • Arrow, bu amaç için uygun sütun odaklı bir format
    • Embedding’ler ve sayfa başlıkları Arrow tabloları olarak saklanıyor
    • Palet indeksleri 2 boyutlu bir dizi gibi, başlıklar ise 1 boyutlu string dizisi gibi ele alınıyor
    • Amaç, parse veya yüklemeden çok bitleri doğru yerlere kopyalamaya odaklanmak
  • Arrow dizi formatı yalnızca 1 boyutlu veri tuttuğundan, 48 boyutlu embedding’leri işlemek için iki şema kullanılıyor
    • Metadata şeması 100 bin satır biriminde
    • Embedding şeması 100 bin * 48 satır biriminde
    • Yükleme anında embedding’ler yeniden reshape ediliyor
  • safetensors da aynı tasarım ilkesini izliyor
  • JSON, 48 öğeli dizileri değişken uzunluklu ASCII karakterler olarak serileştirdiği için yükleme aşamasını karmaşıklaştırıyor
  • Protocol Buffers, 32 bitten küçük tamsayılar için base 128 değişken genişlikli tamsayı kullanıyor; bu tamsayı biçimi mevcut compute kernel’lerde iyi desteklenmiyor

Wikipedia ayrıştırma ve embedding üretimi

  • Wikipedia işaretlemesini ayrıştırmak için mediawiki parser from hell, yani mwparserfromhell kullanılıyor
  • OLM’nin Wikipedia dataset veri kümesi, belirli bir dildeki Wikipedia’nın en güncel veri dökümünü alıp başlık ve gövde gibi satırlara ayrıştırıyor
    • Bu veri kümesi, zararsız serileştirilmiş veriden çok çalıştırılması gereken koda benziyor; bu yüzden yürütme güveni gerekiyor
  • Ayrıştırma, tek bir makinedeki tüm çekirdeklerde yapılıyor
    • Güncel makinelerde onlarca çekirdek bulunduğundan, bugünkü 6 milyon sayfalık English Wikipedia gibi 100 milyon belgenin altındaki yapılar için uygun
  • Embedding modeli olarak all-minilm-l6-v2 kullanılıyor
    • İngilizce için iyi performans veren hafif bir sentence transformer
    • Sorgu ve belgeleri aynı uzaya embedding olarak yerleştiriyor
    • 22 milyon parametreyle oldukça hafif bir model
  • Tarayıcıda JavaScript çalıştırmak için ONNX ve transformers.js üzerinden 8 bit nicemlenmiş sürüm de kullanılıyor
  • Model, 128 token dizileriyle eğitildiğinden bağlam penceresi ortalama sayfa uzunluğundan çok daha kısa
    • Bu yüzden sayfalar parçalara ayrılıyor ve her parçanın embedding’i ortalanarak sayfa ortalama embedding’i oluşturuluyor

pq.js ve doğrusal tarama tabanlı facet araması

  • Milyonlarca belge yerelde aranacaksa karmaşık indeksleme sistemleri şart değil
  • Amaç, belirli bir noktaya en yakın birkaç sonucu, örneğin en yakın 12 mesafeyi, bulmak
  • 10 milyonluk mesafe dizisi, 10 milyonluk facet sütunu ve tek bir facet değeri olduğunda; koşula uyanlara 0, uymayanlara Infinity ekleyip ardından top-k bulma yöntemiyle filtreleme yapılıyor
    • Güncel telefonlarda ilk 100 sonuç 10ms’den kısa sürede bulunabiliyor
    • Uygulama filtered-topk ve pq.js içinde yer alıyor
  • Product Quantization ile sıkıştırılmış embedding’lerin mesafe hesabı PyTorch ile yazılabiliyor
    • subspaceCount adet palet bulunuyor ve her palette codewordCount adet subspaceDim boyutlu nokta var
  • PyTorch’tan dışa aktarılan ONNX modelindeki indeksleme biraz hantallaşabiliyor
    • ONNX’in GatherElements opcode’u gereken işi doğrudan yapıyor
    • ONNX-modifier gibi araçlarla dışa aktarılan ONNX modelinin veri akışı grafiğindeki düğümler eklenip çıkarılabiliyor
  • Çok aşamalı indekslemeyi doğru tekil opcode ile değiştirmek, mesafe hesaplamasını yaklaşık 4 kat hızlandırıyor

Akışlı hesaplama ve etkileşimli arayüz

  • Mesafesi hesaplanacak embedding sayısı sabit değil
    • Sorgu ile embedding’lerin bir kısmı arasındaki mesafeler akış halinde hesaplanabiliyor
    • Yeterli süre geçtiğinde, o ana kadar hesaplanan mesafelerle top-k çalıştırılıp arama sonuçları güncelleniyor
  • Tüm embedding’ler yerelde olduğundan, arama altyapısına giden gecikme fiilen 0ms
  • Hedef arayüz tepkiselliği, bir işlemden sonra 100~300ms içinde sonucun görünmesi
    • MiniLM, 100ms’den kısa sürede çalışabiliyor
    • Uç cihazlara bağlı olarak bu süre 15ms’nin altına da inebiliyor
    • 100k embedding için mesafe hesabı yaklaşık 10ms’de yapılabiliyor
  • Veri kümesi, uzun makalelerden kısa makalelere doğru sıralanırsa nihai üst sıralardaki sonuçların çoğu ilk akışlı sonuçlarda hızla ortaya çıkıyor
    • Çünkü uzun makaleler yazılırken genelde daha fazla ilgi ve emek harcanıyor ve çok sayıdaki stub makaleye göre arama sorgusuyla daha iyi eşleşebiliyorlar
  • Mesafeler küresel olarak hesaplanıp sonra facet filtresi ve top-k uygulandığı için, aynı sorguda facet değeri ya da sonuç sayısı değiştiğinde yalnızca filtreleme yeniden çalıştırılıyor
    • Bu filtreleme 10ms’den kısa sürdüğünden anlık hissediliyor

Yeniden kullanılabilir pq.js bileşenleri

  • Tüm Wikipedia search app içindeki pek çok kütüphane işlevi, yeniden kullanılabilir pq.js bileşenlerine taşınabilir
  • Şu anda birçok ONNX shape önceden sabitlenmiş durumda
  • Farklı nicemleme düzeyleri ve farklı embedding boyutları desteklenirse daha geniş yeniden kullanım mümkün olabilir

İlgili okumalar

1 yorum

 
GN⁺ 2023-09-03
Hacker News yorumları

  • Kesinlikle ilginç, ama birkaç felsefe ve psikoloji terimini açıklamayı denediğimde aradığım maddelerin hepsi ancak 20. sıralar civarında çıktı
    Daha ünlü ama daha az isabetli maddeler üstlere yerleşmişti; örneğin belirli bir psikoterapi yöntemini tanımlamak için ne yazsam “psychotherapy” her zaman 1. sıradaydı
    Öte yandan ChatGPT ile adını hatırlamadığım dar bir alt alanı aradığım olmuştu ve her seferinde doğru bildi
    Açıklamaya bakarak bir şeyin adını bulan bir yapay zeka servisi fikri güzel, ama bunu Wikipedia ya da Wikipedia madde başlıklarıyla sınırlamanın doğru yaklaşım olup olmadığından emin değilim; genel amaçlı büyük dil modelleri bunu zaten epey iyi yapıyor gibi görünüyor
    Yine de bir kavram kanıtı olması ve tarayıcıda yerel olarak çalışabilmesi gerçekten harika

    • Amaç veritabanı motorunu göstermek ve tarayıcı her şeyi indirdikten sonra tamamen yalıtılmış bir ortamda da çalışabileceğini demo etmekti
      Ayarlanabilecek çok parametre var gibi görünüyor. Belgenin yalnızca ilk paragrafını mı yoksa tamamını mı kullanmak, belirli bir belgeye yakın bir aralıkta mı aramak gibi şeyler; bunlara henüz dokunmadım
      Wikipedia demo veri kümesi olarak harika ve başka veri kümeleri de eklemeyi denemek istiyorum. Örneğin iPhoto’da “mountain” aratınca içinde dağ olan fotoğrafların çıkması gibi, CLIP benzeri çok modlu modellerle çeşitli veri kümelerinde arama yapmak ilginç olabilir
    • Bir fikri ve hedefi açıklayıp alan adını ya da bakılabilecek anahtar kelimeleri geri almak şeklinde kullandığım oldu
      Büyük dil modelleri en iyi bulanık arama motoru gibi görünüyor; geleneksel arama motorlarından oldukça farklı ama onları tamamlayan bir biçimde çalışıyor

  • Kavram hoşuma gitti ama sonuçlar iyi çıkmadı
    “weird looking monkey” yazıp hortumlu maymun ya da altın kalkık burunlu maymun gibi sonuçlar bekledim, ama yalnızca “Pet monkey”, “List of individual monkeys”, “Ethnoprimatology”, “Monkey” gibi maddeler geldi
    Aynı sorguyu Google’a yazınca tam beklediğim sonuçlar çıkıyor; bu yüzden üzücüydü, bilmediğim tuhaf görünümlü maymunları araştırmak istemiştim

    • Bir yılı aşkın süredir var olan hazır bir sentence-transformer modeli olduğu gibi kullanıldı
      Demonun odağı embedding veritabanını göstermekti, ama embedding’lerin kendisi de bir miktar işe yarıyor
      Sayfada neyin bulunup bulunamadığına dair hiçbir analiz verisi tutmadığım için arama sonuçlarını iyileştirmeye hazır değilim
    • Wikipedia editörleri ve yönergeleri genel olarak öznel sıfatları pek sevmez; sorgudaki “weird looking” ifadesi de Wikipedia maddelerinde kaçınılacak türden bir ifade gibi duyuluyor
      Bu yüzden bu bilgi derleminden iyi sonuç almak zorlaşıyor

  • Uygulama gerçekten iyi ve bunu çevrimdışı yapabilmek harika. Ancak embedding kalitesi hâlâ yetersiz görünüyor
    Yardımcı olabilecek bir püf noktası, Wikipedia maddesinin tamamını değil tanıma yakın cümleleri ya da genelde ilk cümle/ilk paragrafı embedding’e dönüştürmek. Şu anda hangi kısmın kullanıldığını pek bilmiyorum
    Benim sitem OneLook da 2003’ten beri https://onelook.com/thesaurus/ adresinde açıklamadan kelime ve kavram bulmaya yarayan benzer bir özellik sunuyor
    Başta saf bir ters sözlük aramasıydı, ama son 20 yılda kelime embedding’leri, cümle embedding’leri ve son dönemde büyük dil modellerini denedik; bugünlerde kendi başına yanıtlayamadığı girdiler için GPT adaylar üretiyor
    Bu işte büyük dil modelleri eski yöntemlerden çok daha iyi olduğundan, OneLook’un bu kısmını geliştirme isteğim biraz azaldı. Ters tanım aramasının ChatGPT kullanmalarının başlıca nedeni olduğunu söyleyen insanları sık görüyorum

  • Biraz geç gördüm ama metin embedding’leri, en azından bu yazıda kullanılanlar açısından, genelde vibe’a göre arama yapmakta pek iyi değil
    Daha çok örtüşen kelimeleri karşılaştırmaya ya da sorguya benzer içerik bulmaya yakınlar
    Ancak gerçekten bu problemi ele alan yakın tarihli bir makale var: “Retrieving Texts based on Abstract Descriptions” (Ravfogel et al., 2023) https://arxiv.org/abs/2305.12517
    Makalede “binalar tasarlayan mimar”, “başka bir şirketin parçası olan şirket”, “bir türün gelişimini etkilemiş kitap” gibi soyut açıklamalarla arama örnekleri çok
    Söz konusu embedding’ler bu tür aramaları çok daha iyi destekliyor gibi; bu yüzden bağlantıdaki yazının çevrimdışı Wikipedia aramasını bu yeni embedding türüyle yeniden yapmak ilginç olabilir

  • Şu anda sayfa benim ortamımda çalışmıyor; model_quantized.onnx yüklenmiyor
    Yazı yazarken bile 19,2 MB’a kadar indirdi ve hız yaklaşık 50 KB/s; bunu her ziyaretçi tetikliyorsa Lee Butterman’ın bant genişliği ücretlerine korkunç şeyler yapıyor olabilir

    • Tek bir t2.nano üzerinden statik dosya olarak servis ediyorum, ne olacağını bilmiyorum

  • Yaptığı işin kendisi çok etkileyici, ama arama sonucu kalitesi iyi görünmüyor
    Deneyimlerime göre arama sonucu kalitesini elle değerlendirmenin gerçekten zor olduğunu biliyorum. Çok iyi bir sonuca neredeyse çok yakın olup bundan çok daha kötü eşleşmeler döndürebilir

    • Doğru. Kalite muhtemelen Similar Website Finder https://explore2.marginalia.nu/ kadar iyi değildir ;)
      Daha yeni cümle embedding’leri kullanılırsa sonuçların iyileşeceğini düşünüyorum; daha fazla veri toplamam gerekecek

  • Teknoloji çok etkileyici ama sonuçlar öyle değildi
    “pointy building in Paris” diye aradığımda Tourism in Paris, Bourse de commerce (Paris), Grands Projets of François Mitterrand, List of tallest buildings and structures in the Paris region, List of tourist attractions in Paris, Palais des congrès de Paris, Landmarks in Paris, Palais de la Bourse, Lyon, Outline of Paris, Architecture of Paris çıktı
    Paris’teki en ünlü sivri yapı hiç görünmüyordu
    Bu tür bir uygulama için belgenin tamamına ait cümle gömmesi en iyi seçenek olmayabilir

    • Bunların en az 5’inde aranan cevabın bulunacağını sanıyorum
    • Eiffel Tower’dan bahsediyorsan, o bir bina değil
      Az önce makaleyi kontrol ettim; “building” kelimesi 19 kez geçiyor ama çoğu fiil, sonraki de “Chrysler Building”
      Aklıma gelmeyen başka ünlü sivri bir yapı yoksa durum bu

  • Arama motorlarının sihrinin bir kısmı, o sayfaya bağlantı veren sayfaların gömmelerini ya da geleneksel bilgi erişimi anahtar kelimelerini tıklama sayıları ve otorite puanlarıyla ağırlıklandırıp harmanlamasında yatıyor
    Bu sinyal olmayınca çok sayıda yararlı bilgi göz ardı ediliyor ve sonuçlar sihirli hissettirmiyor
    Yine de etkileyici ve ilginç bir demo

  • Beğenmek istedim ama denediğim aramalarda alakalı sonuçlar neredeyse hiç çıkmadı
    “The wizard in The Lord of the Rings” için Gandalf ya da Saruman yoktu, yalnızca LOTR ile ilgili kitaplar çıktı
    “Protagonist of Scorsese's Taxi Driver” için Travis Bickle yoktu
    “A person that plants trees for a living” için nedense gardener listede yoktu
    “Curly-haired painter on TV” için Bob Ross hiç yoktu
    “Unusually shaped modern art museum in Spain” aramasında Bilbao 4. sırada çıkıyor ama diğerleri alışılmadık biçimli değildi
    “Dog shaped like a sausage” için dachshund’un üst sonuçlarda olması gerekirdi diye düşünüyorum

    • Burada istenen sonuçların tamamının Wikipedia makalesi olduğunu belirtmekte fayda var
      Makaleleri olmasaydı eksik olmaları daha az tuhaf olurdu ama gerçekte hepsi var

  • “Vibes”, “sentence embeddings”den çok daha sezgisel bir ifade. Ben de bu ifadeyi kullanmaya başlayabilirim belki :)

    • “Sezgisel” olmak uğruna kesinlikten büyük ölçüde ödün veren bir ifade
      Orijinal yazının yazarı o kelimeyi neden seçtiğini açıklamamış ve benim bildiğim hiçbir “vibe” kullanımıyla uyuşmuyor
      “gist” yeterince moda bir kelime değil miydi acaba