請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/80842完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 王奕翔(I-Hsiang Wang) | |
| dc.contributor.author | Yu-Chieh Huang | en |
| dc.contributor.author | 黃禹傑 | zh_TW |
| dc.date.accessioned | 2022-11-24T03:18:43Z | - |
| dc.date.available | 2022-10-10 | |
| dc.date.available | 2022-11-24T03:18:43Z | - |
| dc.date.copyright | 2021-11-04 | |
| dc.date.issued | 2021 | |
| dc.date.submitted | 2021-10-14 | |
| dc.identifier.citation | [1] D. Bajovic, D. Jakovetic, J. M. Moura, J. Xavier, and B. Sinopoli. Large deviations performance of consensus+ innovations distributed detection with non-Gaussian observations. IEEE Transactions on Signal Processing, 60(11):5987–6002, 2012. [2] D. Bajović, D. Jakovetić, J. Xavier, B. Sinopoli, and J. M. Moura. Distributed detection over time varying networks: large deviations analysis. In 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 302–309. IEEE, 2010. [3] D. Bajović, J. M. Moura, J. Xavier, and B. Sinopoli. Distributed inference over directed networks: Performance limits and optimal design. IEEE Transactions on Signal Processing, 64(13):3308–3323, 2016. [4] H. Cramér. Random variables and probability distributions, volume 36. Cambridge University Press, 2004. [5] A. Dembo and O. Zeitouni. Large deviations techniques and applications. Springer, 2010. [6] P. Diaconis and D. Stroock. Geometric bounds for eigenvalues of Markov chains. The Annals of Applied Probability, pages 36–61, 1991. [7] B. Efron and D. Traux. Large deviations theory in exponential families. The Annals of Mathematical Statistics, pages 1402–1424, 1968. [8] C.-G. Esseen. Fourier analysis of distribution functions. a mathematical study of the Laplace-Gaussian law. Acta Mathematica, 77(1):1–125, 1945. [9] A. Jadbabaie, P. Molavi, A. Sandroni, and A. TahbazSalehi. Non-Bayesian social learning. Games and Economic Behavior, 76(1):210–225, 2012. [10] A. Jadbabaie, P. Molavi, and A. TahbazSalehi. Information heterogeneity and the speed of learning in social networks. Columbia Business School Research Paper, (13-28), 2013. [11] A. Lalitha, T. Javidi, and A. D. Sarwate. Social learning and distributed hypothesis testing. IEEE Transactions on Information Theory, 64(9):6161–6179, 2018. [12] V. Matta, A. Santos, and A. H. Sayed. Exponential collapse of social beliefs over weakly-connected heterogeneous networks. In ICASSP 20192019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5267–5271. IEEE, 2019. [13] A. Mitra, J. A. Richards, and S. Sundaram. A new approach to distributed hypothesis testing and non-Bayesian learning: Improved learning rate and Byzantine-resilience. arXiv:1907.03588, 2019. [14] A. Nedić, A. Olshevsky, and C. A. Uribe. A tutorial on distributed (non-Bayesian) learning: Problem, algorithms and results. In IEEE 55th Conference on Decision and Control (CDC), pages 6795–6801, 2016. [15] A. Nedić, A. Olshevsky, and C. A. Uribe. Fast convergence rates for distributed non-Bayesian learning. IEEE Transactions on Automatic Control, 62(11):5538–5553, 2017. [16] A. H. Sayed, S.-Y. Tu, J. Chen, X. Zhao, and Z. J. Towfic. Diffusion strategies for adaptation and learning over networks: an examination of distributed strategies and network behavior. IEEE Signal Processing Magazine, 30(3):155–171, 2013. [17] S. Shahrampour, A. Rakhlin, and A. Jadbabaie. Distributed detection: Finite-time analysis and impact of network topology. IEEE Transactions on Automatic Control, 61(11):3256–3268, November 2016. [18] V. Strassen. Asymptotische abschatzugen in Shannon’s informationstheorie. In Transactions of the Third Prague Conference on Information Theory, pages 689–723, 1962. [19] V. Strassen. Asymptotic estimates in Shannon’s information theory. In Proc. Trans. 3rd Prague Conf. Inf. Theory, pages 689–723, 2009. [20] L. Su and N. H. Vaidya. Asynchronous distributed hypothesis testing in the presence of crash failures. arXiv preprint arXiv:1606.03418, 2016. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/80842 | - |
| dc.description.abstract | 我們探討在去中心化假說檢定的問題中，考慮一眾類於[11]所提出之演算法的做法下的理論極限。文獻[11]所提出的演算法保有良好的去中心化特性，網路中的各節點可自由選擇給予其各鄰居的權重，並在每回合根據自身所抽取的樣本及自己的概似函數構成與相鄰節點交換的訊息。然就錯誤機率而論，其演算法所能達到的錯誤率和經典假說檢定問題中的錯誤率之間存在著明顯的落差，而此落差正是受到在去中心化的情況下網路中某種“不平衡”影響而產生。 我們將此情形下的錯誤率刻畫為一最佳化問題，並提出原始演算法的推廣來補償此網路的不平衡性。佐以些許網路的全域訊息，我們證明在我們提出的廣義演算法下，網路中各節點進行假說檢定的錯誤率的首項漸進項能表現的和中心化的情況下一樣好。接著，我們也透過更高次項的漸進項來刻畫去中心化的代價—去中心化最多對錯誤率帶來常數倍的影響。 對於如何讓各節點獲得所需的全域訊息，我們也提出了相似的估計演算法，並刻畫估計量的收斂速度。除了理論結果之外，我們也針對數種情形進行模擬，模擬結果也支持我們提出的演算法以及前述的理論結果。最後，我們也提供了後續的討論以及如何將我們的結果延伸至較一般的問題。 | zh_TW |
| dc.description.provenance | Made available in DSpace on 2022-11-24T03:18:43Z (GMT). No. of bitstreams: 1 U0001-2909202116463400.pdf: 8842848 bytes, checksum: e6dcbd5be01e39c067362c8e489b819a (MD5) Previous issue date: 2021 | en |
| dc.description.tableofcontents | Verification Letter from the Oral Examination Committee i Acknowledgements iii 摘要 v Abstract vii Contents ix List of Figures xiii Chapter 1 Introduction 1 1.1 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Chapter 2 Background 7 2.1 Binary Hypothesis Testing . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.1 Drawing i.i.d. Observations . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Markov Chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Chapter 3 Decentralized Hypothesis Testing 13 3.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 Social Learning Rule . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.3 Log-Belief Ratio Test and the Probability of Error . . . . . . . . . . 16 3.4 The Error Exponent Gap . . . . . . . . . . . . . . . . . . . . . . . . 17 3.5 Modified Learning Rule . . . . . . . . . . . . . . . . . . . . . . . . 19 3.6 First-Order Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.7 Higher-Order Asymptotics . . . . . . . . . . . . . . . . . . . . . . . 24 Chapter 4 Proofs of the Main Theorems 29 4.1 Proof of Theorem 3.6.1 . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.2 Proof of Theorem 3.6.2 . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.3 Proof of Theorem 3.6.3 . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.4 Proof of Theorem 3.7.1 . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.5 Proof of Theorem 3.7.2 . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.6 Proof of Lemma 4.4.1 . . . . . . . . . . . . . . . . . . . . . . . . . 47 Chapter 5 Obtaining the Geometric Weights 49 5.1 Estimating the Stationary Distribution . . . . . . . . . . . . . . . . . 49 5.2 Alternative Learning Rules . . . . . . . . . . . . . . . . . . . . . . . 51 Chapter 6 Simulations 55 6.1 Impact of Network Imbalance . . . . . . . . . . . . . . . . . . . . . 55 6.2 Compensating the Network Imbalance . . . . . . . . . . . . . . . . . 56 6.3 The Effect of Initial and Ongoing Estimations . . . . . . . . . . . . . 58 6.4 Quantization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Chapter 7 Discussion 63 7.1 The Essence of Social Learning . . . . . . . . . . . . . . . . . . . . 63 7.2 Removing the Assumptions on the Network . . . . . . . . . . . . . . 64 7.3 Gaussian Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 7.4 Multiple Hypothesis Testing . . . . . . . . . . . . . . . . . . . . . . 71 7.5 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 7.5.1 Matching lower bound . . . . . . . . . . . . . . . . . . . . . . . . 73 7.5.2 Beyond hypothesis testing . . . . . . . . . . . . . . . . . . . . . . 73 Chapter 8 Conclusion 75 References 77 | |
| dc.language.iso | en | |
| dc.subject | 假說檢定 | zh_TW |
| dc.subject | 分散式學習 | zh_TW |
| dc.subject | decentralized hypothesis testing | en |
| dc.subject | distributed learning | en |
| dc.subject | social learning | en |
| dc.title | 去中心化在分散式學習中對錯誤率的影響 | zh_TW |
| dc.title | On the Price of Decentralization in Distributed Learning | en |
| dc.date.schoolyear | 109-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 張正尚(Hsin-Tsai Liu),洪樂文(Chih-Yang Tseng) | |
| dc.subject.keyword | 分散式學習,假說檢定, | zh_TW |
| dc.subject.keyword | distributed learning,decentralized hypothesis testing,social learning, | en |
| dc.relation.page | 79 | |
| dc.identifier.doi | 10.6342/NTU202103459 | |
| dc.rights.note | 同意授權(限校園內公開) | |
| dc.date.accepted | 2021-10-15 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電信工程學研究所 | zh_TW |
| 顯示於系所單位： | 電信工程學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| U0001-2909202116463400.pdf 授權僅限NTU校內IP使用（校園外請利用VPN校外連線服務） | 8.64 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。