Abstract—This paper presents a rate

Abstract—This paper presents a rate distortion approach to
Markov graph learning. It provides lower bounds on the number
of samples required for any algorithm to learn the Markov graph
structure of a probability distribution, up to edit distance. We
first prove a general result for any probability distribution, and
then specialize it for Ising and Gaussian models. In particular,
for both Ising and Gaussian models on p variables with degree
at most d, we show that at least Ω((d − s
p ) log p) samples are
required for any algorithm to learn the graph structure up to
edit distance s. Our bounds represent a strong converse; i.e.,
we show that for a lower number of samples, the probability of
error goes to 1 as the problem size increases. These results show
that substantial gains in sample complexity may not be possible
without paying a significant price in edit distance error.
Index Terms—Markov networks, graphical models, strong
converse, Ising model, Gaussian Markov mode

ผลลัพธ์ (ไทย) 1:

นามธรรมซึ่งเอกสารนี้แสดงวิธีการบิดเบือนอัตราการการเรียนรู้กราฟ Markov มีขอบเขตล่างบนหมายเลขตัวอย่างที่จำเป็นสำหรับขั้นตอนวิธีใด ๆ การเรียนกราฟ Markovโครงสร้างการกระจายความน่าเป็น ขึ้นอยู่กับระยะทางในการแก้ไข เราต้อง พิสูจน์ผลการทั่วไปสำหรับการแจกแจงความน่าเป็นใด ๆ และแล้ว ชำนาญรุ่น Ising และ Gaussian โดยเฉพาะสำหรับรุ่น Ising และ Gaussian ในตัวแปร p กับปริญญาd มากที่สุด เราแสดงว่าน้อยΩ ((d − sตัวอย่างที่ p p) บันทึก)จำเป็นสำหรับขั้นตอนวิธีใด ๆ การเรียนรู้โครงสร้างกราฟถึงแก้ไขระยะทาง s ตรงกันข้ามแรง แสดงถึงขอบเขตของเรา เช่นเราแสดงว่าการลดจำนวนของตัวอย่าง ความเป็นไปได้ข้อผิดพลาดไป 1 เป็นการเพิ่มขนาดปัญหา แสดงผลเหล่านี้ว่า พบกำไรอย่างซับซ้อนอาจไม่สามารถโดยไม่ต้องจ่ายราคาที่สำคัญในการแก้ไขข้อผิดพลาดจากคำดัชนี — Markov เครือข่าย รูปแบบกราฟิก แข็งแรงรูปแบบตรงกันข้าม Ising โหมด Gaussian Markov

ผลลัพธ์ (ไทย) 2:

บทคัดย่อนี้กระดาษที่นำเสนอวิธีการบิดเบือนอัตราการเรียนรู้กราฟมาร์คอฟ
มันมีขอบเขตที่ลดลงในจำนวนของกลุ่มตัวอย่างที่จำเป็นสำหรับขั้นตอนวิธีการที่จะเรียนรู้รูปแบบของกราฟมาร์คอฟใด ๆ โครงสร้างของการกระจายความน่าจะเป็นสูงสุดในการแก้ไขระยะ เราครั้งแรกที่พิสูจน์ผลทั่วไปสำหรับการกระจายความน่าจะเป็นใด ๆ และจากนั้นมันมีความเชี่ยวชาญIsing และรูปแบบการเสียน โดยเฉพาะอย่างยิ่งสำหรับทั้ง Ising และรูปแบบการเสียนกับตัวแปรพีที่มีระดับที่ดีที่สุดที่เราแสดงให้เห็นว่าอย่างน้อยΩ ((ง - เอพี) เข้าสู่ระบบ P) ตัวอย่างจะจำเป็นสำหรับขั้นตอนวิธีการที่จะเรียนรู้โครงสร้างกราฟถึงใดๆแก้ไข s ระยะทาง . ขอบเขตของเราเป็นตัวแทนของการสนทนาที่แข็งแกร่ง; คือเราแสดงให้เห็นว่าเป็นจำนวนที่ลดลงของกลุ่มตัวอย่างที่น่าจะเป็นของความผิดพลาดไป1 ปัญหาการเพิ่มขึ้นของขนาด ผลการศึกษานี้แสดงให้เห็นว่าผลกำไรเป็นกอบเป็นกำในความซับซ้อนตัวอย่างไม่อาจจะเป็นไปได้โดยไม่ต้องจ่ายราคาที่สำคัญในการแก้ไขข้อผิดพลาดทางไกล. เครือข่ายดัชนีข้อตกลง-มาร์คอฟรูปแบบกราฟิกที่แข็งแกร่งสนทนาแบบ Ising โหมดเสียนมาร์คอฟ

ผลลัพธ์ (ไทย) 3:

บทคัดย่อบทความนี้เสนออัตราการบิดเบือนแนวทาง
กราฟแบบมาร์คอฟ มันมีขอบเขตล่างบนหมายเลข
ตัวอย่างที่ต้องการสำหรับขั้นตอนวิธีการเรียนรู้แบบกราฟ
โครงสร้างของการแจกแจงความน่าจะเป็น ถึงระยะทางที่ถูกแก้ไข . เรา
ก่อนพิสูจน์ผลทั่วไปสำหรับการแจกแจงความน่าจะเป็นและ
จากนั้นเชี่ยวชาญเพื่อการโฆษณาและรูปแบบ ) . โดย
ทั้งเพื่อการโฆษณา ) รุ่น P และตัวแปรที่มีระดับ
ที่สุด D เราแสดงให้เห็นว่าอย่างน้อยΩ ( D − s
P ) log P ) ตัวอย่างที่จำเป็นสำหรับใด ๆเพื่อเรียนรู้
ขั้นตอนวิธีกราฟโครงสร้างขึ้น

แก้ไขระยะห่างของเรา S . ขอบเขตเป็นตัวแทนแข็งแรง Converse ; I ,
เราแสดงให้เห็นว่า สำหรับเลขล่างของตัวอย่างความน่าจะเป็น
ผิดพลาดไป 1 ขนาดของปัญหาที่เพิ่มขึ้น ผลลัพธ์เหล่านี้แสดง
ที่สำคัญจากตัวอย่างความซับซ้อนอาจเป็นไปได้
โดยไม่ต้องจ่ายราคาที่สำคัญในการแก้ไขข้อผิดพลาดระยะไกล
แง่ดัชนีแบบเครือข่าย รูปแบบกราฟิกที่แข็งแกร่ง
Converse , ไอโหมดแบบเกาส์เซียนแบบ