ในปี 1973 Andrey Kolmogorovได้เสนอแนวทางที่ไม่ใช้ความน่าจะเป็นสำหรับสถิติและการเลือกแบบจำลองให้แต่ละข้อมูลเป็นสตริงไบนารีแบบจำกัด และแบบจำลองเป็น เซต ของสตริงไบนารีแบบจำกัด พิจารณาคลาสของแบบจำลองที่ประกอบด้วยแบบจำลอง ที่มีความซับซ้อน Kolmogorov สูงสุดที่กำหนด ฟังก์ชันโครงสร้าง Kolmogorovของสตริงข้อมูลแต่ละตัวแสดงความสัมพันธ์ระหว่างข้อจำกัดระดับความซับซ้อนของคลาสแบบจำลองกับค่าลอการิทึมของจำนวนสมาชิกน้อยที่สุดของแบบจำลองในคลาสที่ประกอบด้วยข้อมูลนั้น ฟังก์ชันโครงสร้างจะกำหนด คุณสมบัติ เชิงสุ่ม ทั้งหมด ของสตริงข้อมูลแต่ละตัว: สำหรับคลาสแบบจำลองที่มีข้อจำกัดแต่ละคลาส มันจะกำหนดแบบจำลองที่เหมาะสมที่สุดในคลาสนั้นโดยไม่คำนึงว่าแบบจำลองที่แท้จริงอยู่ในคลาสแบบจำลองที่พิจารณาหรือไม่ ในกรณีคลาสสิก เราพูดถึงชุดข้อมูลที่มีการกระจายความน่าจะเป็นและคุณสมบัติต่างๆ ก็คือคุณสมบัติของค่าคาดหวัง ในทางตรงกันข้าม ที่นี่เราจัดการกับสตริงข้อมูลแต่ละตัวและคุณสมบัติของสตริงแต่ละตัวที่เราสนใจ ในบริบทนี้ คุณสมบัติจะเกิดขึ้นอย่างแน่นอนมากกว่าที่จะเป็นความน่าจะเป็นสูงเหมือนในกรณีคลาสสิก ฟังก์ชันโครงสร้างของ Kolmogorov ใช้ในการวัดความเหมาะสมของแบบจำลองแต่ละแบบกับข้อมูลแต่ละชุดได้อย่างแม่นยำ

ฟังก์ชันโครงสร้างของ Kolmogorov ถูกนำมาใช้ในทฤษฎีสารสนเทศเชิงอัลกอริทึมหรือที่รู้จักกันในชื่อทฤษฎีความซับซ้อนของ Kolmogorov เพื่ออธิบายโครงสร้างของสตริงโดยใช้แบบจำลองที่มีความซับซ้อนเพิ่มขึ้น

ฟังก์ชันโครงสร้างได้รับการเสนอครั้งแรกโดยKolmogorovในปี 1973 ในงานสัมมนาทฤษฎีสารสนเทศของโซเวียตที่เมืองทาลลินน์ แต่ผลลัพธ์เหล่านี้ไม่ได้ถูกตีพิมพ์^{[ 1 ]}หน้า 182 แต่ผลลัพธ์ดังกล่าวได้รับการประกาศใน^{[ 2 ]}ในปี 1974 ซึ่งเป็นบันทึกเป็นลายลักษณ์อักษรเพียงฉบับเดียวของ Kolmogorov เอง หนึ่งในข้อความทางวิทยาศาสตร์สุดท้ายของเขาคือ (แปลจากต้นฉบับภาษารัสเซียโดย LA Levin):

วัตถุเชิงสร้างสรรค์แต่ละชิ้นจะสอดคล้องกับฟังก์ชันของจำนวนธรรมชาติ k ซึ่งก็คือลอการิทึมของจำนวนสมาชิกขั้นต่ำของเซตที่มี x ซึ่งอนุญาตให้กำหนดนิยามที่มีความซับซ้อนไม่เกิน k หากองค์ประกอบ x เองอนุญาตให้กำหนดนิยามอย่างง่ายได้ ฟังก์ชันจะลดลงเหลือ 0 แม้สำหรับ k ขนาดเล็ก หากไม่มีนิยามดังกล่าว องค์ประกอบนั้นจะ "สุ่ม" ในความหมายเชิงลบ แต่จะ "สุ่มในเชิงความน่าจะเป็น" ในเชิงบวกก็ต่อเมื่อฟังก์ชันมีค่าที่ k ขนาดเล็กแล้วเปลี่ยนแปลงโดยประมาณตาม${\displaystyle \Phi _{x}(k)}$${\displaystyle \Phi }$${\displaystyle \Phi }$${\displaystyle \Phi _{0}}$${\displaystyle k=k_{0}}$${\displaystyle \Phi (k)=\Phi _{0}-(k-k_{0})}$

มีการกล่าวถึงใน Cover และ Thomas ^{[ 1 ]}มีการศึกษาอย่างกว้างขวางใน Vereshchagin และVitányi ^{[ 3 ]}ซึ่งคุณสมบัติหลักได้รับการแก้ไขแล้ว ฟังก์ชันโครงสร้าง Kolmogorov สามารถเขียนได้เป็น โดย ที่เป็นสตริงไบนารีที่มีความยาวโดยที่ เป็นแบบจำลองที่พิจารณา (ชุดของสตริงที่มีความยาว n) สำหรับคือความ ซับซ้อนของ Kolmogorovของและ คือค่าจำนวนเต็มที่ไม่เป็นลบซึ่งจำกัดความซับซ้อนของ's ที่พิจารณา เห็นได้ชัดว่าฟังก์ชันนี้ไม่เพิ่มขึ้นและถึงโดยที่คือจำนวนบิตที่ต้องการเปลี่ยนเป็นและคือ ความซับซ้อน ของ Kolmogorovของ$${\displaystyle h_{x}(\alpha )=\min _{S}\{\log |S|:x\in S,K(S)\leq \alpha \}}$$${\displaystyle x}$${\displaystyle n}$${\displaystyle x\in S}$${\displaystyle S}$${\displaystyle x}$${\displaystyle K(S)}$${\displaystyle S}$${\displaystyle \alpha }$${\displaystyle S}$${\displaystyle \log \left|\{x\}\right|=0}$${\displaystyle \alpha =K(x)+c}$${\displaystyle c}$${\displaystyle x}$${\displaystyle \{x\}}$${\displaystyle K(x)}$${\displaystyle x}$

เรากำหนดเซตที่ประกอบด้วยโดยที่ ฟังก์ชันจะไม่ลดลงมากกว่าค่าคงที่อิสระที่กำหนดไว้ด้านล่างเส้นทแยงมุมที่เรียกว่าเส้นความเพียงพอ L ซึ่งกำหนดโดย กราฟของ จะเข้าใกล้ ด้วยระยะทางคงที่สำหรับอาร์กิวเมนต์บางตัว (ตัวอย่างเช่น สำหรับ) สำหรับค่าเหล่านี้ เรามีและแบบจำลองที่เกี่ยวข้อง(พยานสำหรับ) เรียกว่าเซตที่เหมาะสมที่สุดสำหรับและคำอธิบายของบิตจึงเป็นสถิติเพียงพอเชิงอัลกอริทึมเราเขียนคำว่า 'อัลกอริทึม' แทน 'ความซับซ้อนของ Kolmogorov' ตามธรรมเนียม คุณสมบัติหลักของสถิติเพียงพอ เชิงอัลกอริทึม มีดังต่อไปนี้: ถ้าเป็นสถิติเพียงพอเชิงอัลกอริทึมสำหรับแล้ว นั่นคือ คำอธิบายสองส่วนของ โดยใช้แบบจำลองและดัชนีของในการแจงนับของเป็นบิต เป็นรหัสข้อมูลไปยังแบบจำลอง จะกระชับเท่ากับรหัสหนึ่งส่วนที่สั้นที่สุดของเป็นบิต สามารถมองเห็นได้ง่ายๆ ดังนี้: ${\displaystyle S}$${\displaystyle x}$$${\displaystyle K(S)+K(x|S)=K(x)+O(1).}$$${\displaystyle h_{x}(\alpha )}$$${\displaystyle L(\alpha )+\alpha =K(x).}$$${\displaystyle h_{x}}$${\displaystyle \alpha =K(x)+c}$${\displaystyle \alpha }$${\displaystyle \alpha +h_{x}(\alpha )=K(x)+O(1)}$${\displaystyle S}$${\displaystyle h_{x}(\alpha )}$${\displaystyle x}$${\displaystyle K(S)\leq \alpha }$${\displaystyle S}$${\displaystyle x}$$${\displaystyle K(S)+\log |S|=K(x)+O(1).}$$${\displaystyle x}$${\displaystyle S}$${\displaystyle x}$${\displaystyle S}$${\displaystyle \log |S|}$${\displaystyle x}$${\displaystyle K(x)}$$${\displaystyle {\begin{aligned}K(x)&\leq K(x,S)+O(1)\\&\leq K(S)+K(x|S)+O(1)\\&\leq K(S)+\log |S|+O(1)\\&\leq K(x)+O(1),\end{aligned}}}$$

โดยใช้ความไม่เท่าเทียมกันโดยตรงและคุณสมบัติความเพียงพอ เราพบว่า(ตัวอย่างเช่น เมื่อกำหนดเราสามารถอธิบายขอบเขตของตัวเองได้ (คุณสามารถกำหนดจุดสิ้นสุดได้) ในบิต) ดังนั้นความขาดแคลนความสุ่มของในจึงเป็นค่าคงที่ ซึ่งหมายความว่าเป็นองค์ประกอบทั่วไป (สุ่ม) ของ S อย่างไรก็ตาม อาจมีแบบจำลองที่มีที่ไม่ใช่สถิติที่เพียงพอ สถิติที่เพียงพอเชิงอัลกอริทึมสำหรับมีคุณสมบัติเพิ่มเติม นอกเหนือจากการเป็นแบบจำลองที่เหมาะสมที่สุดแล้ว คือ และด้วยเหตุนี้โดย สมมาตรความซับซ้อนของข้อมูลของ Kolmogorov (ข้อมูลเกี่ยวกับในเกือบจะเหมือนกับข้อมูลเกี่ยวกับใน x) เราจึงมี: สถิติที่เพียงพอเชิงอัลกอริทึมเป็นแบบจำลองที่เหมาะสมที่สุดซึ่งถูกกำหนดโดย เกือบทั้งหมด( คือโปรแกรมที่สั้นที่สุดสำหรับ) สถิติที่เพียงพอเชิงอัลกอริทึมที่เกี่ยวข้องกับ ที่น้อยที่สุดดังกล่าวเรียกว่าสถิติที่เพียงพอขั้นต่ำ เชิงอั ลก อริทึม${\displaystyle K(x|S)=\log |S|+O(1)}$${\displaystyle S\ni x}$${\displaystyle x}$${\displaystyle \log |S|+O(1)}$${\displaystyle \log |S|-K(x|S)}$${\displaystyle x}$${\displaystyle S}$${\displaystyle x}$${\displaystyle S}$${\displaystyle x}$${\displaystyle S}$${\displaystyle x}$${\displaystyle K(x,S)=K(x)+O(1)}$${\displaystyle x}$${\displaystyle S}$${\displaystyle S}$${\displaystyle K(S|x^{*})=O(1)}$${\displaystyle S}$${\displaystyle x}$${\displaystyle x^{*}}$${\displaystyle x}$${\displaystyle \alpha }$

เกี่ยวกับรูปภาพ: ฟังก์ชันโครงสร้าง MDL อธิบายไว้ด้านล่าง ฟังก์ชันโครงสร้างความเหมาะสมคือค่าความขาดแคลนแบบสุ่มน้อยที่สุด (ดูด้านบน) ของแบบจำลองใดๆสำหรับฟังก์ชันโครงสร้างนี้ให้ความเหมาะสมของแบบจำลอง(ที่มี x) สำหรับสตริง x เมื่อค่าต่ำ แบบจำลองจะเหมาะสมดี และเมื่อค่าสูง แบบจำลองจะไม่เหมาะสมดี ถ้าสำหรับบางค่าจะมีแบบจำลองทั่วไปสำหรับเช่นนั้นและเป็นแบบทั่วไป (สุ่ม) สำหรับ S นั่นคือเป็นแบบจำลองที่เหมาะสมที่สุดสำหรับ x สำหรับรายละเอียดเพิ่มเติม โปรดดู^{[ 1 ]}และโดยเฉพาะอย่างยิ่ง^{[ 3 ]}และ^{[ 4 ]}${\displaystyle \lambda _{x}(\alpha )}$${\displaystyle \beta _{x}(\alpha )}$${\displaystyle S\ni x}$${\displaystyle x}$${\displaystyle K(S)\leq \alpha }$${\displaystyle S}$${\displaystyle \beta _{x}(\alpha )=0}$${\displaystyle \alpha }$${\displaystyle S\ni x}$${\displaystyle x}$${\displaystyle K(S)\leq \alpha }$${\displaystyle x}$${\displaystyle S}$

ภายใต้ข้อจำกัดที่ว่ากราฟจะลงที่มุมอย่างน้อย 45 องศา เริ่มต้นที่ n และสิ้นสุดที่ประมาณกราฟทุกกราฟ (จนถึงพจน์บวกในอาร์กิวเมนต์และค่า) จะเกิดขึ้นได้ด้วยฟังก์ชันโครงสร้างของข้อมูล x บางอย่าง และในทางกลับกัน เมื่อกราฟกระทบเส้นทแยงมุมก่อน อาร์กิวเมนต์ (ความซับซ้อน) จะเป็นสถิติที่เพียงพอขั้นต่ำ ไม่สามารถคำนวณเพื่อกำหนดตำแหน่งนี้ได้ ดู^{[ 3 ]}${\displaystyle K(x)}$${\displaystyle O(\log n)}$

ได้รับการพิสูจน์แล้วว่าในแต่ละระดับความซับซ้อน ฟังก์ชันโครงสร้างช่วยให้เราสามารถเลือกโมเดลที่ดีที่สุดสำหรับสตริง x แต่ละตัวภายในแถบได้อย่างแน่นอน ไม่ใช่ด้วยความน่าจะเป็นสูง^{[ 3 ]}${\displaystyle \alpha }$${\displaystyle S}$${\displaystyle O(\log n)}$

ฟังก์ชัน ความยาวคำอธิบายขั้นต่ำ (MDL): ความยาวของรหัสสองส่วนที่น้อยที่สุดสำหรับ x ซึ่งประกอบด้วยต้นทุนแบบจำลอง K(S) และความยาวของดัชนีของ x ใน S ในคลาสแบบจำลองของเซตที่มีความซับซ้อนของ Kolmogorov สูงสุดที่กำหนดโดยความซับซ้อนของ S ถูกจำกัดไว้สูงสุดจะถูกกำหนดโดยฟังก์ชัน MDL หรือตัวประมาณค่า MDL ที่มีข้อจำกัด: ${\displaystyle \alpha }$${\displaystyle \alpha }$

$${\displaystyle \lambda _{x}(\alpha )=\min _{S}\{\Lambda (S):S\ni x,\;K(S)\leq \alpha \},}$$โดยที่ ความยาวรวมของรหัสสองส่วนของ x อยู่ ที่ใด โดยใช้โมเดล S${\displaystyle \Lambda (S)=\log |S|+K(S)\geq K(x)-O(1)}$

ได้รับการพิสูจน์แล้วว่าในแต่ละระดับความซับซ้อน ฟังก์ชันโครงสร้างช่วยให้เราสามารถเลือกโมเดล S ที่ดีที่สุดสำหรับสตริง x แต่ละตัวภายในแถบได้อย่างแน่นอน ไม่ใช่ด้วยความน่าจะเป็นสูง^{[ 3 ]}${\displaystyle \alpha }$${\displaystyle O(\log n)}$

คณิตศาสตร์ที่พัฒนาขึ้นข้างต้นถูกนำมาใช้เป็นพื้นฐานของMDL โดย Jorma Rissanenผู้คิดค้น^{[ 5 ]}

สำหรับการแจกแจงความน่าจะเป็นที่คำนวณได้ทุกประเภทสามารถพิสูจน์ได้^{[ 6 ]}ว่า ตัวอย่างเช่น ถ้าเป็นการแจกแจงที่คำนวณได้บนเซตของสตริงที่มีความยาวแล้วแต่ละสตริงจะมีความน่าจะเป็น ฟังก์ชันโครงสร้างของ Kolmogorov จะกลายเป็น โดยที่ x เป็นสตริงไบนารีที่มีความยาว n โดยที่ เป็นแบบจำลองที่พิจารณา (ความน่าจะเป็นที่คำนวณได้ของสตริงที่มีความยาว ) สำหรับคือความ ซับซ้อนของ Kolmogorovของและ คือค่าจำนวนเต็มที่จำกัดความซับซ้อนของ's ที่พิจารณา เห็นได้ชัดว่าฟังก์ชันนี้ไม่เพิ่มขึ้นและถึงสำหรับโดยที่ c คือจำนวนบิตที่จำเป็นในการเปลี่ยนเป็นและคือความซับซ้อนของ Kolmogorov ของจากนั้นสำหรับทุกระดับความซับซ้อนฟังก์ชัน คือเวอร์ชันความซับซ้อนของ Kolmogorov ของความน่าจะเป็นสูงสุด (ML) ${\displaystyle P}$$${\displaystyle -\log P(x)=\log |S|+O(\log n).}$$${\displaystyle P}$${\displaystyle S}$${\displaystyle n}$${\displaystyle x\in S}$${\displaystyle P(x)=\exp(O(\log n))/|S|=n^{O(1)}/|S|}$$${\displaystyle h'_{x}(\alpha )=\min _{P}\left\{-\log P(x):P(x)>0,K(P)\leq \alpha \right\}}$$${\displaystyle -\log P(x)>0}$${\displaystyle P}$${\displaystyle n}$${\displaystyle x}$${\displaystyle K(P)}$${\displaystyle P}$${\displaystyle \alpha }$${\displaystyle P}$${\displaystyle \log |\{x\}|=0}$${\displaystyle \alpha =K(x)+c}$${\displaystyle x}$${\displaystyle \{x\}}$${\displaystyle K(x)}$${\displaystyle x}$${\displaystyle h'_{x}(\alpha )=h_{x}(\alpha )+O(\log n)}$${\displaystyle \alpha }$${\displaystyle h'_{x}(\alpha )}$

ได้รับการพิสูจน์แล้วว่าในแต่ละระดับความซับซ้อน ฟังก์ชันโครงสร้างช่วยให้เราสามารถเลือกโมเดลที่ดีที่สุดสำหรับสตริงแต่ละสตริงภายในแถบได้อย่างแน่นอน ไม่ใช่ด้วยความน่าจะเป็นสูง^{[ 3 ]}${\displaystyle \alpha }$${\displaystyle S}$${\displaystyle x}$${\displaystyle O(\log n)}$

ฟังก์ชัน MDL: ความยาวของรหัสสองส่วนขั้นต่ำสำหรับ x ซึ่งประกอบด้วยต้นทุนแบบจำลอง K(P) และความยาวของในคลาสแบบจำลองของฟังก์ชันมวลความน่าจะเป็นที่คำนวณได้ของความซับซ้อน Kolmogorov สูงสุดที่กำหนดความซับซ้อนของ P ที่มีขอบเขตบนโดยจะกำหนดโดยฟังก์ชัน MDL หรือตัวประมาณ MDL ที่มีข้อจำกัด: ${\displaystyle -\log P(x)}$${\displaystyle \alpha }$${\displaystyle \alpha }$

$${\displaystyle \lambda '_{x}(\alpha )=\min _{P}\{\Lambda (P):P(x)>0,\;K(P)\leq \alpha \},}$$โดยที่ความยาวทั้งหมดของรหัสสองส่วนของ x อยู่ ที่ใด โดยใช้แบบจำลอง P${\displaystyle \Lambda (P)=-\log P(x)+K(P)\geq K(x)-O(1)}$

ได้รับการพิสูจน์แล้วว่าในแต่ละระดับความซับซ้อน ฟังก์ชัน MDL ช่วยให้เราสามารถเลือกโมเดลP ที่ดีที่สุด สำหรับสตริงx แต่ละตัว ภายในแถบได้อย่างแน่นอน ไม่ใช่ด้วยความน่าจะเป็นสูง^{[ 3 ]}${\displaystyle \alpha }$${\displaystyle O(\log n)}$

ปรากฏว่าแนวทางนี้สามารถขยายไปสู่ทฤษฎีของอัตราการบิดเบือนของลำดับจำกัดแต่ละรายการและการลดสัญญาณรบกวนของลำดับจำกัดแต่ละรายการ^{[ 7 ]}โดยใช้ความซับซ้อนของ Kolmogorov การทดลองโดยใช้โปรแกรมบีบอัดจริงประสบความสำเร็จ^{[ 8 ]}ในที่นี้สมมติฐานคือสำหรับข้อมูลธรรมชาติ ความซับซ้อนของ Kolmogorov จะไม่ห่างจากความยาวของเวอร์ชันที่บีบอัดโดยใช้ตัวบีบอัดที่ดี