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

จากวิกิพีเดีย สารานุกรมเสรี

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

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

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

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

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

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

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

สำหรับเหตุการณ์สุ่มแบบเต็มหน่วย 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 = − p₁ log₂ p₁ − … − p_n log₂ p_n) ว่า เมื่อนำไปวัดที่แหล่งข้อมูล จะสามารถบ่งบอกขนาดที่เล็กที่สุดเท่าที่เป็นไปได้ ของช่องสัญญาณที่ใช้ในการส่งข้อมูลฐานสองได้อย่างถูกต้อง สูตรนี้สามารถสร้างขึ้นมาได้จากการคำนวณค่าคาดหวัง (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

เอนโทรปีของข้อมูล เป็นบทความเกี่ยวกับ คอมพิวเตอร์ อุปกรณ์คอมพิวเตอร์ หรือ เครือข่าย ที่ยังไม่สมบูรณ์ ต้องการตรวจสอบ เพิ่มเนื้อหา หรือเพิ่มแหล่งอ้างอิง คุณสามารถช่วยเพิ่มเติมหรือแก้ไข เพื่อให้สมบูรณ์มากขึ้น
ข้อมูลเกี่ยวกับ เอนโทรปีของข้อมูล ในภาษาอื่น อาจสามารถหาอ่านได้จากเมนู ภาษาอื่น ด้านซ้ายมือ หรือ ดูเพิ่มที่ สถานีย่อย:เทคโนโลยีสารสนเทศ

See also ebooksgratis.com: no banners, no cookies, totally FREE.

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

จากวิกิพีเดีย สารานุกรมเสรี

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

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

Views

ป้ายบอกทาง

มีส่วนร่วม

ค้นหา

ภาษาอื่น