Lecture Note - Evaluation in Information Retrieval

เทอมนี้ลงวิชา Information Storage and Retrieval Research ซึ่งเป็นตัวต่อของ Information Retrieval เมื่อเทอมที่แล้ว อาจารย์ก็คนเดิมคือ Mark Sanderson

เผอิญว่าคาบล่าสุดเกิดคึกอะไรไม่รู้ตั้งใจเรียนเป็นพิเศษ ​(ปกติจะหลับเพราะมันเรียนเช้า 9 โมง) เลยมาจดไว้เสียหน่อย หัวข้อคือการประเมินผล search engine หรือ Evaluation in Information Retrieval ตามธรรมเนียมของการเรียนแบบฝรั่งที่ดี อาจารย์ต้องเดินเข้ามาในห้องแล้วถามว่า ใครมีไอเดียอะไรบ้างว่าเราควรวัดผล search engine กันอย่างไร นักเรียนในห้องซึ่งมีตั้งแต่ ป. ตรีถึง ป. เอกก็เสนอไอเดีย ตั้งแต่ relevance ไปจนถึง speed (ส่วนผมก็เป็นนักเรียนไทยที่ดีคือนั่งเฉยๆ)

พอมีคนพูดถึง speed อาจารย์บอกว่ามันเป็นเรื่องพูดง่ายแต่ทำยาก เขาเคยคุยกับนักจิตวิทยา บอกว่า threshold ในการประเมินผลของมนุษย์ต่อเหตุการณ์ใดๆ (เช่น การเปิดสวิตช์ไฟแล้วไฟสว่าง) อยู่ที่ 1/4 วินาที ซึ่งถ้ามากเกินกว่านี้ เราจะเริ่มสงสัยแล้วว่ามีอะไรผิดปกติหรือเปล่า (เช่น ไฟเสีย) การแสดงผลลัพธ์ของ search engine ก็ใช้หลักการเดียวกันนี้

แต่เรื่องสำคัญกว่าคือ relevant ของผลการค้นหา ว่าตรงเป้าหมายที่เราต้องการแค่ไหน โดยทั่วไปแล้วไม่ว่าได้ผลลัพธ์มากขนาดไหน คนมักสนใจแค่หน้าแรก (top 10) แต่เอาเข้าจริง ความสนใจอาจแคบลงไปแค่ top 4 (หรือ top 5) คือผลการค้นหาหน้าแรกที่ไม่ลง scroll down เพื่อลงไปดู

Indicator

ในวงการ search engine มีการวัดค่า relevance แบบดั้งเดิมอยู่ 2 ชนิด คือ precision กับ recall

Precision อธิบายง่ายๆ ว่า ในเอกสารทั้งหมดที่ search engine ค้นมาให้เรา มีเอกสารที่เข้าเป้ากี่อัน อธิบายแบบคณิตศาสตร์คือ Precision = (Relevant and Retrieved) / Retrieved

Recall คือในเอกสารที่เข้าเป้าทั้งหมดนั้น search engine มันไปหาเจอมาให้เรากี่อัน สูตรคณิตศาสตร์คือ Recall = (Relevant and Retrieved) / Total Relevant

ตัวอย่าง ถ้าเอกสารในระบบทั้งหมดมี 100 อัน มีเอกสารที่เข้าเป้าทั้งหมด 10 อัน (สมมติว่าเรารู้โดยการไล่อ่านทั้ง 100 อัน) ถ้า query แล้วมีผลการค้นหาออกมาทั้งหมด 20 อัน ในนี้มีเข้าเป้า 5 อัน เราจะประเมินได้ว่า precision = 5/20 = 0.25 และ recall = 5/10 = 0.50

Precision

โดยทั่วไปแล้วจะใช้ precision เป็นหลัก แต่ข้อเสียของการวัดด้วย precision ก็มาก

• precision เป็นการวัดเฉพาะเอกสารที่ค้นเจอ อันที่หาไม่เจอจะถูกกันออกไปไม่เอามาคิด
• ถ้ามีเอกสารใหม่เข้ามาในระบบ เราต้องวัดค่า precision ใหม่เสมอ
• precision เป็นค่าที่ subjective มาก การเปรียบเทียบ precision ระหว่าง search engine ทำได้ยาก (precision 0.7 ไม่จำเป็นต้องดีกว่า 0.3)

วิธีแก้ปัญหาเหล่านี้คือสร้าง test collections มาตรฐานขึ้นมา ให้ทุก search engine ที่ต้องการเปรียบเทียบใช้ร่วมกัน (จะได้เปรียบเทียบกันได้)

Test Collecions

Test collections ประกอบด้วยของ 3 อย่าง

• Set of documents - เอกสารทั้งหมดที่จะค้น
• Set of queries - ชุดคีย์เวิร์ดที่จะค้น
• Set of relevant judgements - ผลการประเมินล่วงหน้าว่า เอกสารไหนบ้างที่ตรงตามต้องการ

อันสุดท้ายนี่สำคัญที่สุด และสร้างได้ยากที่สุด ในสมัยโบราณที่ set of documents ยังแค่หลักร้อยหรือหลักพัน เราสามารถถึกทำมือได้ แต่พอจำนวนเอกสารมากขึ้นเรื่อยๆ ต้องมีเทคนิคเข้ามาช่วยสร้าง set of relevant judgements ซึ่งก็คือ pooling

Pooling

Pooling คือการสร้าง subset ของ set of documents ขึ้นมา เพื่อจำกัดวงการค้นหาไม่ให้มากเกินไป โดยเราหวังว่า (แค่หวัง) relevant documents ทั้งหมดนั้นจะอยู่ใน subset นี้ (ไม่การันตี) การสร้าง subset มีด้วยกันสองวิธี

• System pooling - ให้ search engine ทุกยี่ห้อที่จะเข้าทดสอบ รัน query เดียวกันใน set of documents เดียวกัน แล้วเอาผลที่ได้มารวมกันเป็น subset
• Query pooling - อันนี้ใช้ search engine เพียงตัวเดียว แต่รัน query ที่ใกล้เคียงกันหลายๆ แบบ (เช่น nuclear waste dumping, radioactive waste, hazardous waste เป็นต้น) แล้วเอาผลที่ได้มารวมกัน

เทคนิค pooling นี้ค่อนข้างประสบความสำเร็จในวงการ search engine อย่างไรก็ตามมีเปเปอร์หลายชิ้นประเมินว่าการทำ pooling นั้นเจอ relevant documents จริงๆ แค่ไหน ขาดตกบกพร่องอะไรบ้าง

พอได้ของทั้ง 3 อย่างครบแล้ว ก็รัน query แล้วเอาผลมาเปรียบเทียบกับ relevant judgement เพื่อหาค่า precision จากนั้นเราสามารถเอา precision ของต่าง search engine มาเปรียบเทียบกันได้เสียที (เพราะว่าตัวแปรอื่นๆ ถูกปรับให้เท่ากันหมดแล้วนี่)

ความหมายของ relevant

ย้อนกลับมาดูความหมายของ relevant บ้าง ว่ามีปัจจัยอื่นอะไรบ้าง ที่นำมาพิจารณาว่าเป็นเอกสารที่ relevant

• sitemap - สำหรับ enterprise search engine มักจะมี sitemap มาให้อยู่แล้วว่า หัวข้อนี้อยู่หน้าไหน
• clickthroughs - คลิกเยอะ แปลว่า relevant?
• references - จำนวนการอ้างถึง (ใกล้เคียงกับแนวคิดของ PageRank)
• ใช้ข้อมูลอื่นประกอบ เช่น จาก Open Directory Project

เปเปอร์ของ Andrew Broder ได้แบ่งชนิดของ query ออกเป็น 3 แบบ

1. Informational - query ทั่วไปที่เราใช้กัน คือหา "ข้อมูล" ของคำที่ค้นหา
2. Navigational - สำหรับกรณีที่เรารู้แบรนด์แล้ว แต่ไม่รู้ URL ก็ค้นหาชื่อแบรนด์เพื่อไปให้ถึงเว็บนั้น
3. Transactional - ค้นหาบริการ (transaction) ที่อยู่บนเว็บอื่น เช่น หาคำว่า "train ticket to london" เพื่อเข้าไปยังเว็บของบริษัทรถไฟ แล้วหาเที่ยวรถอีกครั้งหนึ่ง -- กรณีนี้มีน้อยที่สุดในทั้ง 3 แบบ

นอกจากนี้ยังมีเคสพิเศษอื่นๆ ที่อาจมีผลต่อ relevant ของผลการค้นหา เช่น

• recency - ความสดใหม่ ตัวอย่างง่ายๆ คือการค้นหาข่าวจาก Google News
• authoritative - ข้อมูลนั้นเป็นทางการแค่ไหน
• cheapest - หาราคาสินค้า
• readable - เด็กๆ ค้นหาข้อมูลเพื่อทำรายงาน ก็ไม่สนใจ Wikipedia หรือพวก paper
• sense - อย่างคำย่อที่แปลความหมายได้หลายแบบ แต่ละคนก็มีเป้าหมายที่ต่างกันไป