Konvolüsyon, Hızlı Fourier Dönüşümü ve Polinomlar (2022)

 (alvarorevuelta.com)
1 puan yazan GN⁺ 2024-07-02 | 1 yorum | WhatsApp'ta paylaş
  • Büyük dereceli polinomları lise yöntemiyle açtığınızda tüm terim çiftlerini çarpmak gerektiğinden O(n²) maliyeti hızla darboğaza dönüşür
  • Polinomların katsayı vektörü çarpımı, ayrık sinyallerdeki konvolüsyon ile aynıdır; [2, 3, 4] ve [5, 6, 7] için sonuç [10, 27, 52, 45, 28] olur
  • DFT, ayrık sinyali frekans alanına taşır; FFT ise aynı dönüşümü O(n log n) zamanda hesaplayarak büyük girdilerde fark yaratır
  • Zaman alanındaki konvolüsyon, frekans alanında eleman bazında çarpıma dönüştüğünden, FFT ile dönüştürüp çarptıktan sonra IFFT ile geri dönmek polinom çarpımını daha hızlı işleyebilir
  • Küçük derecelerde FFT/IFFT gidiş-dönüş maliyeti kazanımı dengeleyebilir; ancak derece büyüdükçe FFT yöntemi daha verimli olur

Polinom çarpımı neden yavaşlar?

  • Bir polinom P(x), katsayılar a_k ile değişken x’in kuvvet terimlerinin toplamı olarak ifade edilir
    • Örnek P(x)=5x²+2x+9, derecesi 2 olan bir polinomdur
    • Katsayı vektörü, gösterim biçimine göre [5, 2, 9] veya [9, 2, 5] gibi yazılabilir
  • Toplama ve çıkarma, aynı derecedeki terimleri toplayıp çıkarmakla yapıldığından görece basittir
    • Python’da zip(p, q) ile her katsayı üzerinde dolaşıp a + b veya a - b hesaplanabilir
    • Dereceler farklıysa zip_longest kullanılabilir
  • Çarpımda her terimi birbiriyle çarpıp sonra aynı derecedeki terimleri yeniden toplamak gerektiği için hesaplama miktarı artar
    • (2x²+3x+4) × (5x²+6x+7) sonucu 10x⁴+27x³+52x²+45x+28 olur
    • Bu yöntemin karmaşıklığı O(n²)’dir ve derece büyüdükçe gereken çarpım sayısı artar

Katsayı vektörü ve konvolüsyon

  • Ayrık alanda iki sinyal p ve q için konvolüsyon y[n]=Σ p[k]·q[n-k] olarak tanımlanır
  • Hesaplama, q ters çevrilip p üzerinde soldan sağa kaydırılırken çakışan elemanların çarpımlarını toplama biçiminde yapılır
  • Örnek sinyaller şöyledir
    • p = [2, 3, 4]
    • q = [5, 6, 7]
  • q ters çevrilip kaydırıldığında her çıktı katsayısı şu sırayla oluşur
    • 2×5 = 10
    • 2×6 + 3×5 = 27
    • 2×7 + 3×6 + 4×5 = 52
    • 3×7 + 4×6 = 45
    • 4×7 = 28
  • Konvolüsyon sonucu y = [10, 27, 52, 45, 28] olur
    • Bu, polinom çarpımından elde edilen 10x⁴+27x³+52x²+45x+28 katsayılarıyla aynıdır
    • Dolayısıyla polinom çarpımı, katsayı vektörlerinin konvolüsyonu olarak görülebilir

Fourier dönüşümü ve FFT

  • Fourier dönüşümü, sinyali zaman alanından frekans alanına dönüştürür
    • Zaman bakış açısından sinyal, belirli anlardaki değerleriyle görülür
    • Frekans bakış açısından sinyal, farklı titreşim frekanslarının toplamı olarak yorumlanır
  • Titreşim frekansları sinüs ve kosinüslerle ifade edilir; her birinin katsayısı ve fazı vardır
  • 5Hz saf sinüs dalgasına FFT uygulandığında, frekans alanında 5Hz konumunda delta gibi görünür
    • Bu, zaman alanındaki sinüs dalgasının tek bir 5Hz sinüsle ifade edilebildiğini gösterir
  • İlgili terimler şöyle ayrılır
    • Fourier Transform(FT): Sürekli alanda tanımlanan Fourier dönüşümü
    • Discrete Fourier Transform(DFT): Ayrık sinyaller için tanımlanan Fourier dönüşümü
    • Fast Fourier Transform(FFT): DFT’yi O(n²) yerine O(n log n) zamanda hesaplayan algoritma
  • DFT, ayrık zaman sinyali x[n]’i frekans alanındaki X[k]’ye dönüştürür
    • Her X[k], giriş örneklerinin belirli bir frekansı temsil eden karmaşık sayılarla çarpılıp toplanmasıyla hesaplanır

Frekans alanında çarpıma dönüştürmek

  • DFT’nin ve frekans alanının temel avantajı, konvolüsyonu eleman bazında çarpıma dönüştürebilmesidir
    • Zaman alanında iki sinyali konvolüsyona sokmak, frekans alanında iki sinyali çarpmakla aynıdır
    • Çarpım, konvolüsyondan daha hızlı hesaplanabilir
  • Polinom çarpımını hızlı yapmak için izlenen prosedür şöyledir
    • Polinomları FFT ile frekans alanına dönüştürmek: O(n log n)
    • Frekans alanında eleman bazında çarpmak: O(n)
    • Sonucu IFFT ile yeniden zaman alanına dönüştürmek: O(n log n)
  • Genel olarak FFT kullanıldığında polinom çarpımı O(n log n) karmaşıklıkla yapılabilir
  • Büyük polinomlarda, lise yöntemi O(n²) çarpımdan daha hızlıdır

Python uygulaması ve benchmark

  • multiply_naive, iç içe döngülerle tüm katsayı çiftlerini çarpıp sonuç konumu i + j’ye ekler
    • Sonuç uzunluğu len(p) + len(q) - 1 olur
    • Karmaşıklığı O(n²)’dir
  • multiply_fft, katsayı çarpımını FFT/IFFT tabanlı gerçekleştirir
    • Sonuç uzunluğunu kapsayabilmek için len(p) + len(q) - 1 veya daha büyük, 2’nin kuvveti olan bir uzunluk hesaplar
    • İki girdiyi np.pad ile doldurur
    • np.fft.fft ile dönüştürülen değerleri eleman bazında çarpar
    • np.fft.ifft ile geri döndürdükten sonra gerçek kısmı yuvarlayarak tam sayı katsayılara dönüştürür
  • Örnek girdi p = [2, 3, 4], q = [5, 6, 7] için iki yöntem de [10, 27, 52, 45, 28] döndürür
  • Benchmark’ta multiply_naive yerine np.convolve kullanan multiply_convolve ile FFT yöntemi karşılaştırılır
    • Bunun nedeni multiply_naive’in Python döngülerinin yavaş olması ve np.fft.fft kullanan FFT yöntemiyle doğrudan karşılaştırmanın zor olmasıdır
    • np.convolve aynı işlemi düşük seviyeli C koduyla gerçekleştirir
  • Derece, range(1, 30000, 1000) aralığında artırılır ve her derecede 1 ile 999999 arasında rastgele katsayılara sahip iki polinom oluşturulur
    • Her yöntem için n_runs = 5 ile ortalama süre ölçülür
    • Düşük derecelerde FFT/IFFT gidiş-dönüş dönüşüm maliyeti nedeniyle FFT yöntemi avantajlı olmayabilir
    • Derece arttıkça FFT yöntemi çok daha verimli sonuçlar gösterir

İlgili okumalar

1 yorum

 
GN⁺ 2024-07-02
Hacker News yorumları

  • Bu tür açıklamalarda beni hep rahatsız eden şey, genelde sayısal hataların unutulması.
    Katsayı çarpımını öylece “sabit zamanlı” diye soyutlayamazsınız. Bunu yapacaksanız en baştan çarpmanın tamamını soyutlamak da aynı kapıya çıkar. Sayısal hassasiyet hesaba katıldığında O(n (log n)^3)’e daha yakındır [1]
    [1]: http://numbers.computation.free.fr/Constants/Algorithms/fft....

    • O yazıda alıntılanan hata sınırı aşırı kötümser. Knuth’un son baskısında doğru sınır var; çünkü ona ben bildirdim
    • OP yazısındaki kuaterniyon tabanlı işlemlerden yararlanarak çarpma hatasını azaltmak, hatta tamamen ortadan kaldırmak mümkün olsa güzel olurdu [1],[2],[3]
      [1] One-Dimensional Quaternion Discrete Fourier Transform and an Approach to Its Fast Computation:
      https://www.mdpi.com/2079-9292/12/24/4974
      [2] Convolution Theorems for Quaternion Fourier Transform: Properties and Applications:
      https://onlinelibrary.wiley.com/doi/10.1155/2013/162769
      [3] On the Matrix Form of the Quaternion Fourier Transform and Quaternion Convolution:
      https://arxiv.org/abs/2307.01836
    • Katsayılar tamsayıysa, yeterince büyük bir modül (modulus) kullanan NTT ile kesin sonuç elde edebilirsiniz; özellikle donanımda çarpma süresi de daha hızlı olabilir
    • Bu yüzden bilgisayar bilimi ile yazılım mühendisliğini ayırıyoruz :)

  • Bu yöntemle uzun sayıları birbiriyle çarpabilirsiniz. Kilit nokta, polinom çarpımının elde (carry) yapmadan yapılan sıradan uzun sayı çarpımıyla aynı olması.
    Örneğin 1000 basamaklı bir sayınız varsa, her basamağı 1000 elemanlı bir polinomun katsayısı yaparsınız. Sonra yazıda anlatılan FFT yöntemiyle bu polinomları çarpabilirsiniz. Sonucu tekrar sayıya çevirmek için elde işlemini yapmanız gerekir. Bir eleman 10’dan büyükse fazlalığı bir sonraki basamağa aktarır, katsayıları da sayıya çevirirsiniz.
    Temel fikir bu; elde işlemi için gereken hassasiyet ve FFT sonucunu en yakın tamsayıya yuvarlamanın doğru sonucu vereceğini garanti etme kısmında ince noktalar var. Bu yöntem, alanın önde gelen kütüphanesi GMP’nin büyük sayı çarpımı yapma biçimidir

    • Dediğiniz gibi ondalık sayı x=10 olan bir polinom olarak ifade edilebildiği için mantıklı. Örneğin 983 = 9x^2 + 8x + 3, yani [9, 8, 3].
      Pratikte anlamlı olması için sayıların ne kadar büyük olması gerektiğini ve nerelerde kullanıldığını merak ediyorum

  • Henüz izlemediyseniz bu videoya bakmanız iyi olur
    https://youtu.be/h7apO7q16V0?si=bmgUEMTQSqU3flIv
    Polinom çarpımı üzerinden FFT algoritmasını türetiyor; gerçekten harika. Yaklaşık 6 ayda bir tekrar izliyorum

  • FFT’nin “konvolüsyon noktasal çarpımdır” özelliği, herhangi bir döngüsel çarpma grubu için de geçerlidir. Daha cebirsel bir türetme için https://www.sciencedirect.com/science/article/pii/S002200007... bakın
    Buna bazen “harmonik FFT” denir; harmonik olmayan FFT’ler de vardır: GF(2^n) üzerinde [LCH14] “additive NTT”, sonlu cisimdeki birim çember X^2+Y^2=1 üzerinde [HLP24] circle FFT, eliptik eğri izojeni dizileri üzerinde [BCKL21] ecfft
    [LCH14]: https://arxiv.org/abs/1404.3458
    [HLP24]: https://eprint.iacr.org/2024/278
    [BCKL21]: https://arxiv.org/pdf/2107.08473

  • Daha hızlı polinom çarpımı için FFT kullanmayı ilk kim önermişti?
    Geçenlerde merak edip baktım; atıf zincirini çok iyi izleyemesem de David Eppstein’in 1995 tarihli makalesine [0] kadar geri gidebildim. Orada bunu, artımlı güncellemelerden sonra kısmi toplam problemini verimli biçimde çözmek için kullanıyor. Eminim Knuth’un TAOCP’sinde daha da erken bir yerde vardır.
    FFT polinom çarpımıyla, tekrara izin veren kesin kısmi toplam probleminin altüssel zamanda çözülebilmesi de epey şaşırtıcıydı [1]. Önemli nokta şu: Bu algoritma O(N log N), ama buradaki N kümenin boyutu değil, en büyük eleman; dolayısıyla P ≠ NP’ye karşı bir örnek falan değil.
    [0] https://escholarship.org/content/qt6sd695gn/qt6sd695gn.pdf
    [1] https://x.com/festivitymn/status/1788362552998580473?s=46&t=...

  • Bence tüm makine öğrenmesi, konvolüsyon denklemleri çözme işidir.
    Bu makale konuyu pekiştirmeli öğrenme bağlamında ele alıyor https://arxiv.org/abs/1712.06115, ama yaklaşımların çoğu bu paradigmanın içine oturuyor.

    • Temelde kernel yöntemleri demek değil mi bu?

  • Az önce FFT kullanarak, zaman serisi alt dizilerinin büyük bir kümesi için iç çarpımları hesaplayan bir algoritma (matrix profile) implemente ettim. Zaman serisi uzunluğu n yüz milyonlar mertebesine çıkabiliyor.
    FFT ile hızlı konvolüsyon hesabı sayesinde hesaplama süresi O(n)’den O(log n)’ye düşüyor; bu ölçekte hızlanma muazzam. GPU da kullanınca daha da hızlanıyor; örneğin dizüstünde 10 milyon veri noktasını 0,1 saniyede işlemek gibi.

  • Bu işlemin temel “numarası” şu fark ediş gibi görünüyor:

    Başka bir deyişle, zaman alanında iki sinyalin konvolüsyonunu yapmak, frekans alanında iki sinyali çarpmakla aynıdır.
    Karmaşık bir fikri çok daha küçük adımlara bölüp matematiği zayıf olan benim bile bir şekilde anlayabileceğim hale getiren iyi bir yazı. Ama arada bir adım mı atlanmış? Yoksa okuyucuya araştırması için alıştırma olarak mı bırakılmış? O noktaya kadar matematik kapasitemi zaten sonuna kadar kullanıyordum; biraz “ve geri kalan lanet baykuşu çizin” hissi verdi. Sadece bana mı öyle geldi? Yazının kendisi gerçekten çok iyiydi.

    • İşe yarar mı bilmiyorum ama: Okulda öğrendiğimiz iki polinomun çarpımı aslında konvolüsyondur.
      “Zaman alanında iki sinyalin konvolüsyonunu yapmak, frekans alanında iki sinyali çarpmakla aynıdır” şeklinde bir özellik var; FFT de zaman alanından frekans alanına geçmemizi sağlar. Bu yüzden polinomları FFT ile frekans alanına taşıyıp, o alanda yalnızca çarpma yapmak yeterlidir. Konvolüsyondan daha hızlıdır. Eksik adımı bunun netleştirip netleştirmediğini merak ediyorum; eksik kalan bir yer varsa yazıyı güncelleyebilirim.

  • Öyleyse tamsayı çarpanlara ayırma ayrık dekonvolüsyon mudur? FFT gösterimini, yani noktasal çarpmanın ters işlemini, tableax ile, yani klasik uzun çarpma/elde toplama ile yan yana koyunca simetri bozulur da hızlı bir algoritma için yeterli bilgi elde edilebilir mi, merak ediyorum.

  • Elbette naif polinom çarpımı, polinom derecesine göre yavaştır. Peki pratikte iki 100. dereceden polinom ile uğraşmak ne zaman gerekir?
    Bu nedenle bilgisayar cebiri sistemlerinde bu yöntemin kullanılmadığı izlenimi var

    • Bilgisayar cebiri sistemleri; örneğin Matlab’in chebfun’ı, kökleri, optimum değerleri vb. daha kolay bulmak için keyfi fonksiyonları 100. derece ve üzeri polinomlara dönüştürür
    • Hata düzeltme ve sinyal işlemede çok yaygındır
      https://www.youtube.com/watch?v=CcZf_7Fb4Us
      https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_cor... buna bir örnektir
    • Büyük bir dosyanın CRC checksum parametrelerini tersine mühendislikle çıkarmak istediğim için, dosyayı milyonlarca dereceli bir GF(2) polinomuna dönüştürüp en büyük ortak böleni hesaplayan bir program[1] yaptım. FFT tabanlı çarpım olmadan makul sürede mümkün değil
      [1]: https://github.com/8051enthusiast/delsum
    • Bu konvolüsyon bakış açısı ve FFT için hızlı GPU çekirdekleri, Mamba öncesi bazı durum uzayı modellerinde uzun sekans modellemesi için kullanılıyordu; burada polinom, giriş sekansıdır
      Hazy Research’ün 2020~2023 arasındaki blog yazılarında bu yaklaşım hakkında çok bilgi var
    • https://news.ycombinator.com/item?id=40306339 bkz.
      “(...) fizik araştırmalarında neredeyse 1 terabayt uzunluğunda ve 100 milyondan fazla terim içeren ifadelerle uğraştığım oldu”