เอนโทรปีของข้อมูล

จากวิกิพีเดีย สารานุกรมเสรี
เอนโทรปีของการทดลองแบร์นูลีซึ่งเป็นฟังก์ชันของโอกาสสำเร็จ

ในทฤษฎีข้อมูล เอนโทรปีของข้อมูล คือ เป็นลักษณะที่บ่งชี้ระดับการสุ่มของสัญญาณหรือเหตุการณ์สุ่ม ว่ามีมากน้อยเพียงใด หรือเราอาจมองอีกมุมหนึ่งว่าเป็นตัวบ่งบอกว่าสัญญาณอันหนึ่งบรรจุข้อมูลอยู่เท่าไร

เอนโทรปีเป็นแนวคิดของเทอร์โมไดนามิคส์ กลศาสตร์ทางสถิติ และ ทฤษฎีข้อมูล แนวคิดของเอนโทรปีกับเรื่องของข้อมูลมีความเกี่ยวพันกันอย่างมาก อย่างไรก็ตามกว่าที่กลศาสตร์ทางสถิติและทฤษฎีข้อมูล จะพัฒนามาจนความสัมพันธ์นี้ปรากฏขึ้น ก็ใช้เวลานานทีเดียว บทความนี้เป็นบทความเกี่ยวกับเอนโทรปีของข้อมูล (กฎเกณฑ์ของเอนโทรปีที่เกี่ยวข้องกับข้อมูลเชิงทฤษฎี)

ตัวอย่างเช่น พิจารณาข้อความในภาษาไทย ซึ่งประกอบด้วยตัวอักษรและเครื่องหมายต่าง ๆ (ซึ่งสัญญาณของเราในที่นี้ ก็คือลำดับของตัวอักษรและเครื่องหมายนั่นเอง) สังเกตว่าตัวอักษรบางตัวมีโอกาสปรากฏขึ้นมาน้อยมาก (เช่น ฮ) แต่บางตัวกลับปรากฏบ่อยมาก (เช่น อ) ดังนั้นข้อความภาษาไทยนั้นก็ไม่ได้เรียกว่าสุ่มซะทีเดียว (ถ้าสุ่มจริง ข้อความน่าจะออกมาเป็นคำมั่ว ๆ อ่านไม่ได้ใจความ) อย่างไรก็ตาม ถ้าเราได้คำชุดหนึ่งมา เราก็ไม่อาจคาดเดาได้ว่าคำต่อไปเป็นคำว่าอะไร แสดงว่ามันก็มี'ความสุ่ม'อยู่บ้าง ไม่ได้เที่ยงแท้ซะทีเดียว เอนโทรปีก็คือการวัดระดับความสุ่มนี้นั่นเอง โดยกำเนิดมาจากผลงานของ คลาวด์ อี แชนนอน ในปีพ.ศ. 2491 (ค.ศ. 1948) ชื่อ A Mathematical Theory of Communication [1]

แชนนอนสร้างบทนิยามของเอนโทรปีขึ้นจากข้อสมมติฐานว่า

  • ค่านี้จะต้องมีสัดส่วน (ที่ต่อเนื่อง) นั่นคือ หากเปลี่ยนค่าของความน่าจะเป็นอันหนึ่งเพียงเล็กน้อย ค่าเอนโทรปีก็ควรเปลี่ยนเพียงเล็กน้อยเช่นกัน
  • หากผลลัพธ์ (เช่น ตัวอักษรและเครื่องหมายในตัวอย่างข้างต้น) ทุกอันมีโอกาสเกิดเท่า ๆ กันแล้ว การเพิ่มจำนวนตัวอักษร (และเครื่องหมาย) จะต้องทำให้ค่าเอนโทรปีเพิ่มขึ้นด้วยเสมอ
  • เราต้องสามารถใช้วิธีเลือกผลลัพธ์ (ตัวอักษร) โดยทำเป็นสองขั้นตอน และในกรณีนี้ ค่าเอนโทรปีของผลลัพธ์สุดท้ายต้องเท่ากับเอนโทรปีของทั้งสองขั้นตอนบวกกัน (โดยมีการถ่วงน้ำหนัก)

นิยามทางการ[แก้]

สำหรับเหตุการณ์สุ่มแบบเต็มหน่วย x ซึ่งสมมุติให้มีสถานะ 1..n, เคลาด์ อี แชนนอน นิยามเอนโทรปีในเทอมของ x ว่า

H (x) =\sum_{i=1}^np (i) \log_2 \left (\frac{1}{p (i)}\right) =-\sum_{i=1}^np (i) \log_2 p (i).\,\!

นั่นคือ เอนโทรปีของเหตุการณ์ x คือ ผลรวม (บนทุกๆผลลัพธ์ i ที่เป็นไปได้) ของผลคูณของความน่าจะเป็นที่จะเกิดผลลัพธ์ i กับ ล็อกของความน่าจะเป็นนั้น นอกจากนี้ เราสามารถใช้สมการนี้กับกระจายตัวเชิงความน่าจะเป็นทั่วๆไปนอกเหนือจากเหตุการณ์แบบเต็มหน่วยได้อีกด้วย

แชนนอนแสดงว่า นิยามของเอนโทรปีทุกรูปแบบที่ตรงตามเงื่อนไขของเขาจะต้องอยู่ในรูป

-K\sum_{i=1}^np (i) \log p (i).\,\!

เมื่อ K เป็นค่าคงตัวใดๆ (และจะเห็นได้ว่ามันเป็นเพียงค่าที่เปลี่ยนไปตามหน่วยวัดเท่านั้นเอง)

แชนนอนให้นิยามการวัดเอนโทรปี (H = − p1 log2 p1 − … − pn log2 pn) ว่า เมื่อนำไปวัดที่แหล่งข้อมูล จะสามารถบ่งบอกขนาดที่เล็กที่สุดเท่าที่เป็นไปได้ ของช่องสัญญาณที่ใช้ในการส่งข้อมูลฐานสองได้อย่างถูกต้อง สูตรนี้สามารถสร้างขึ้นมาได้จากการคำนวณค่าคาดหวัง (expectation) ของ ปริมาณของข้อมูล ที่อยู่ในแต่ละหลักของ แหล่งข้อมูล ค่าเอนโทรปีของแชนนอนนี้ได้กลายมาเป็นตัววัดความไม่แน่นอนของตัวแปรสุ่ม และดังนั้นจึงเป็นตัวบอกเกี่ยวกับข้อมูลที่บรรจุอยู่ในข้อความ เมื่อเปรียบเทียบกับส่วนของข้อความที่สามารถคาดการณ์ได้โดยโครงสร้างของมันเอง ตัวอย่างเช่น การใช้คำฟุ่มเฟือยในภาษาสื่อสาร หรือความถี่ของการเกิดตัวอักษรหรือคำแต่ละคู่หรือแต่ละชุด ดูห่วงโซ่มาร์คอฟเพิ่มเติม

ที่มาของสมการเอนโทรปี[แก้]

ลองนึกถึงตัวอย่างของการส่งข้อมูลจากแหล่งหนึ่งไปอีกแหล่งหนึ่ง โดยที่ข้อความที่เป็นไปได้มีทั้งหมด s แบบ ซึ่งก็คือ  x_1, x_2, \ldots, x_s ข้อมูลแต่ละแบบมีความถี่ในการเกิดเป็น  k_1, k_2, \ldots, k_s ตามลำดับ โดยที่จำนวนการเกิดของข้อมูลทั้งหมดเป็น  k= k_1+k_2 + \ldots + k_s หากเรามีข้อมูลเพียงเท่านี้ โดยหลักการนับเบื้องต้น ความเป็นไปได้ของข้อความที่เกิดขึ้นทั้งหมดคือ

 {k \choose k_1, k_2, \ldots, k_s} = \frac{k!}{k_1! k_2! \ldots k_s!}

ในการที่ฝ่ายส่งข้อมูลส่งข้อความไปให้ฝ่ายรับ ฝ่ายส่งสามารถเลือกใช้การเข้ารหัสแบบใดก็ได้ แต่สิ่งสำคัญที่สุดอย่างหนึ่งที่ต้องคำนึงคือ "ฝ่ายรับต้องสามารถสร้างข้อความที่ได้รับมาให้กลับไปอยู่ในรูปแบบเดิมได้" นั่นก็คือ เราจะไม่สนใจการเข้ารหัสแบบแปลกประหลาดทั้งหลายที่ฝ่ายรับนำข้อมูลมาใช้ไม่ได้ ยกตัวอย่างเช่น ส่งข้อมูลทุกอย่างไปในรูปแบบของ "111" ฝ่ายรับไม่สามารถนำข้อมูลที่ได้รับมาไปใช้ได้เลย

วิธีส่งที่ฝ่ายส่งจะสามารถทำได้แบบหนึ่งคือ ส่งข้อมูลดังต่อไปนี้ไปให้ฝ่ายรับ

  • ส่งค่าของ  (k_1, k_2, \ldots, k_s) ใช้ปริมาณข้อมูลทั้งหมด  s \log k บิต
  • ส่งลำดับของข้อความที่ต้องการใน total ordering ที่นิยามบนเซ็ตความเป็นไปได้ของข้อความทั้งหมด (ordering นั้นจำเป็นที่จะต้องเป็น computable ordering, หรือพูดอีกอย่างหนึ่งก็คือ ฝ่ายรับสามารถคำนวณหาข้อความได้เมื่อรู้ลำดับของข้อความในเซ็ตนั้น) ใช้ปริมาณข้อมูลเท่ากับค่าลอกการิธึมของขนาดของเซ็ต

(สังเกตอย่างหนึ่งว่าการส่งข้อมูลที่พิจารณากันในที่นี้ ไม่สนใจประสิทธิภาพของการถอดข้อมูลกลับไปเป็นรูปแบบเดิม นั่นก็คือ ผู้ส่งนั้นไม่สนใจว่าฝ่ายรับจะใช้เวลานานเพียงใดในการคำนวณหาข้อความที่ต้องการส่งจากสิ่งที่ส่งไป สิ่งที่ฝ่ายส่งสนใจมีเพียงว่า ถ้าฝ่ายรับมีชีวิตเป็นอนันต์ ซักวันคงถอดรหัสกลับมาได้)

ปริมาณข้อมูลที่ต้องการใช้ทั้งหมดก็คือ

 \log (\frac{k!}{k_1! k_2! \ldots k_s!}) \le H (X) \le \log ( \frac{k!}{k_1! k_2! \ldots k_s!}) + s \log k

ถ้าเราใช้สูตรของ Stirling ในการประมาณค่าแฟกทอเรียล และหาลิมิตของ H (X) โดยที่ค่า k เข้าใกล้อนันต์ เราจะได้ผลลัพธ์คือ

 H (X) = -K\sum_{i=1}^np (i) \log p (i).\,\!

โดยที่  p_i = k_i/ k เป็นความถี่ของการเกิดข้อมูลชนิดที่ i