The query complexity of estimating entropy
Entropi kestiriminin sorgu karmaşıklığı
- Tez No: 433938
- Danışmanlar: PROF. DR. AHMET CELAL CEM SAY
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2016
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 71
Özet
Bu çalışmada, ayrık olasılık dağılımının entropisinin toplanır hata payıyla kestirimi iki farklı kurguda irdelenmektedir. Buna göre bilinmeyen bir olasılık dağılımı p'ye erişim iki farklı sorgu türüyle sağlanmaktadır. Herhangi bir girdisi olmayan SAMP sorgusu p[x] olasılığıyla x döndürmektedir. Girdi olarak x alan PMF sorgusunun ise çıktısı p[x]'dir. SAMP modeli ismini verdiğimiz ilk kurguda p ile sadece SAMP sorgusu vasıtasıyla iletişim sağlanmaktadır. SAMP+PMF modeli olarak adlandırdığımız ikinci kurgudaysa hem SAMP hem de PMF sorguları kullanılabilmektedir. Daha kesin bir ifadeyle, çalışmanın odak noktası olasılık dağılımı p'nin entropisinin yüksek ihtimalle toplanır hata payıyla kestirimi problemidir. Shannon entropisinin kestirimini incelediğimiz bölümde Valiant ve Valiant'ın SAMP modelinde göstermiş olduğu eşleşen alt ve üst sınırları ve Canonne ve Rubinfeld'in SAMP+PMF modelinde inşa etmiş olduğu algoritmayı tasvir ediyoruz. Renyi entropisini incelediğimiz bölümdeyse Acharya ve diğerleri tarafından sunulan üç farklı eşleşen alt ve üst sınır çiftini analiz ediyoruz. Kendi katkımız olarak, önce SAMP+PMF modelinde Shannon entropisinin kestirimi probleminin en az poli-logaritmik sayıda sorgu gerektirdiğini kanıtlayarak Canonne ve Rubinfeld'in sunduğu üst sınırın optimal olduğunu gösteriyoruz. İkinci olarak, yine SAMP+PMF modelinde Renyi entropisinin kestirimi probleminin eşleşen üst ve alt sınırlarını inşa ediyoruz.
Özet (Çeviri)
We investigate the query complexity of additively estimating entropy of a discrete probability distribution in two settings. Let p be an unknown probability distribution on [n]:= {1, 2, ..., n}, and define two kinds of queries: A SAMP query takes no input and returns x with probability p[x]; a PMF query takes as input x and returns the value p[x]. In the SAMP model of query complexity, the only allowed interaction with p is via SAMP queries. In the SAMP+PMF model, both SAMP and PMF queries are utilized to interact with p. In particular, we consider the task of estimating the entropy of a probability distribution. For the usual Shannon entropy, we review the matching upper and lower bounds established by Valiant and Valiant in the SAMP model, and describe the algorithm constructed by Canonne and Rubinfeld in the SAMP+PMF model. For the Renyi entropy, we analyze three different matching upper and lower bound pairs introduced by Acharya et al. in the SAMP model. We show that at least poly-logarithmic number of queries are necessary to estimate the Shannon entropy in the SAMP+PMF model, matching a recent upper bound of Canonne and Rubinfeld. In addition, we prove matching upper and lower bounds to estimate the Renyi entropy in the SAMP+PMF model.
Benzer Tezler
- Dağıtık veri tabanlarında sorgu optimizasyonu
Query optimization of distributed database systems
BANU TEZEL
- Effective & efficient methods for web search result diversification
Web arama cevaplarının çeşitlendirilmesinde etkin ve verimli yöntemler
AHMET MURAT ÖZDEMİRAY
Doktora
İngilizce
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. İSMAİL SENGÖR ALTINGÖVDE
- Estimation of database query time before execution in a database management system
Bir veritabanı yönetim sisteminde sorgu çalıştırmadan önce sorgu süresi tahmini
ELİF EZGİ YUSUFOĞLU
Yüksek Lisans
İngilizce
2012
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. MURAT AYYILDIZ
PROF. DR. ENSAR GÜL
- Arama motorları için derin öğrenme tabanlı sorgu önerisi çerçevesi
Deep learning based query suggestion framework for search engines
FATİH ÇELİK
Yüksek Lisans
Türkçe
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Üniversitesi-CerrahpaşaBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. SİBEL SENAN
- Character-level dilated deep neural networks for web attack detection
Ağ yöresi saldırılarının belirlenmesi için karakter düzeyinde seyreltilmiş derin sinir ağları
NAZANIN MOARREF
Doktora
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. MEHMET TAHİR SANDIKKAYA