[Information Retrieval#1] Information Retrieval คืออะไร? รู้จักกับ Boolean Retrieval Model

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

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

เบื้องหลังการทำงานของระบบค้นหา ไม่ว่าจะเป็น Google, Bing หรือการใช้เครื่องมือเช่น Apache Lucene, Apache Solr และ Elastic Search ล้วนตั้งอยู่บนศาสตร์ที่เรียกว่า Information Retrieval นั่นหละครับคือองค์ความรู้ที่เราจะพูดถึงกันในชุดบทความนี้

Information Retrieval คืออะไร

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

ความต้องการของมนุษย์อย่างเราๆที่มีต่อเอกสารเหล่านั้น คือต้องการดึงข้อมูลที่อยากรู้ออกจากกลุ่มเอกสารที่ไม่ได้มีการจัดโครงสร้างเหล่านี้ นี่หละครับที่เราเรียกว่า Information Retrieval หรือ IR

Mac OS X เป็นระบบปฏิบัติการที่เราสามารถใช้ Spotlight เพื่อค้นหาข้อมูลไฟล์หรือเอกสารที่เราต้องการได้ search engine อย่าง Google ก็อนุญาตให้เราค้นหาข้อมูลได้เช่นเดียวกัน ระบบค้นหาหนังสือจากห้องสมุดก็เป็นส่วนหนึ่งของการค้นหา จึงกล่าวได้ว่าระบบทั้งหลายนี้ล้วนเป็น Information Retrieval

แรกเริ่มนั้น IR ยังไม่ฉลาดขนาดที่จะจัด rank ได้แบบที่ Google ทำหรอกครับ เราผ่านร้อนผ่านหนาวกันมาเยอะ มีการพัฒนาโมเดลและทฤษฎีต่างๆมากมายกว่าจะมาเป็นระบบค้นหาที่ชาญฉลาดแบบทุกวันนี้ บทความนี้จะเริ่มพูดถึงวิธีการค้นหาแบบแรกๆที่เรียกว่า Boolean Retrieval กันครับ

รู้จัก Boolean Retrieval

โดยปกติแล้วสิ่งใดก็ตามที่เราจะใช้เพื่อสร้างระบบ IR เราจะเรียกว่า document และเราเรียกกลุ่มของ document เหล่านั้นที่มีส่วนร่วมในการค้นหาของเราว่า collection หรืออาจเรียกว่า corpus ก็ได้

ถ้าเราใช้หนังสือหนึ่งเล่มเป็นข้อมูลเพื่อสร้าง IR หรือระบบค้นหา (ซึ่งโดยปกติไม่มีใครเขาทำกันหรอกฮะ การค้นหาข้อมูลจากหนังสือเล่มเดียวมันน้อยไป) เราอาจแบ่งบท (chapter) แต่ละบทออกเป็น document โดยทุกๆบทรวมกันจะมีความหมายเป็น collection นั่นเอง

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

ถ้าหนังสือเล่มนี้ของเราประกอบด้วยเนื้อหา 4 บทดังนี้

บทที่1: Vue.js มีเนื้อหาคือ

1You can use a pattern similar to the EventEmitter in Node.js: a centralized event hub
2that allows components to communicate, no matter where they are in the component
3tree.

บทที่2: Ember.js มีเนื้อหาคือ

1Ember makes Handlebars templates even better, by ensuring your HTML stays up-to-date
2when the underlying model changes. To get started, you don't even need to write any
3JavaScript.

บทที่3: Angular.js มีเนื้อหาคือ

1A more sophisticated application would have child components that descended from
2AppComponent in a visual tree. A more sophisticated app would have more files and
3modules, at least as many as it had components.

บทที่4: React.js มีเนื้อหาคือ

1React components implement a render() method that takes input data and returns what
2to display. This example uses an XML-like syntax called JSX. Input data that is
3passed into the component can be accessed by render() via this.props.

โจทย์ของผมคือต้องการค้นหาด้วยเงื่อนไขที่ว่า component AND tree หรือก็คือหาเอกสารที่มีทั้งคำว่า component และคำว่า tree อยู่ในเอกสารนั้น เพื่อนๆเห็นใช่ไหมครับว่าสิ่งที่ผมกำลังค้นหานั้นใช้เงื่อนไขทางตรรกศาสตร์ (AND, OR, NOT) ซึ่งผลลัพธ์ที่ได้จากการเชื่อมกันนี้มันได้ค่าความจริงออกมาเป็น boolean เราจึงเรียกวิธีการค้นหาแบบนี้ว่า boolean retrieval

ถ้าเราจะค้นหาเอกสารโดยการเขียนโปรแกรมให้วนลูปหาแต่ละคำในเอกสาร มันก็จะเสียเวลามากใช่ไหมครับ ดังนั้นวิธีที่มีประสิทธิภาพมากกว่าคือการตารางที่เราเรียกว่า binary term-document หรือ incidence metrix ขึ้นมา

ตอนนี้เรารู้จักคำว่า document ไปแล้ว แต่ยังไม่ได้แนะนำคำว่า term ครับ ขอให้เพื่อนๆอ่านประโยคนี้ดูก่อนครับ He went to church yesterday. ถ้าเราถามว่าประโยคนี้มีกี่คำ เราก็จะตอบได้ว่ามี 5 คำใช่ไหมครับ คือ He, went, to, church และ yesterday แต่ไม่ใช่ทุกคำในประโยคนี้ที่เราจะจัดเก็บลงในคอมพิวเตอร์เพื่อทำระบบค้นหาครับ

คำเช่น the, to หรือ He เป็นคำที่ทุกเอกสารต้องมี ดังนั้นแล้วเราจะเก็บคำเหล่านี้ไปทำไมกัน เก็บไปก็ไม่มีประโยชน์เพราะถ้าค้นหาคำว่า the จากระบบเรา มันก็จะเจอในทุกเอกสารนั่นเอง ดังนั้นแล้วประโยค He went to church yesterday. คำว่า He และ to จึงไม่ใช่คำที่ควรเก็บเพื่อทำ IR

ระบบค้นหาต้องฉลาดครับ ถ้าเราค้นหาคำว่า go ระบบควรจะคืนผลลัพธ์เป็นเอกสารที่มีคำว่า go หรือ went หรือ gone อยู่ในเอกสารนั้น ไม่ใช่ไปหาเฉพาะเอกสารที่มีคำว่า go (แต่ถ้าค้นหา pokemon go ต้องได้เอกสารที่มีคำว่า pokemon go นะ ไม่ใช่เอา pokemon went และ pokemon gone ออกมาให้เรา) คำประเภทที่เปลี่ยนไปตามกาล (tense) เช่น went เวลาเก็บในระบบเราจึงควรเปลี่ยนกลับให้เป็นกริยาช่อง 1 คือ go เพื่อให้คอมพิวเตอร์รู้ว่าถ้าค้นหา go จะได้เอกสารเหล่านี้เช่นกัน

จากหลักการที่พิมพ์มาแสนยาวนี้จึงได้ข้อสรุปว่าประโยค He went to church yesterday. ของเราควรเก็บคำต่อไปนี้ในระบบคือ go, church และ yesterday สามคำสุดท้ายที่ได้จากการคัดกรองดังกล่าวข้างต้นนี้เรียกว่า term ครับ

กลับมาที่โจทย์ของเรากันอีกรอบ เราจะสร้างตาราง binary term-document โดยให้ term อยู่คอลัมภ์ซ้ายสุดของตาราง และ document อยู่บนแถวแรกของตาราง ถ้าเอกสารไหนมี term นั้นให้ใส่เลข 1 แต่ถ้าเอกสารไหนไม่มี term นั้นอยู่เลยให้ใส่เลข 0

แต่ละแถวของ term-document incidence matrix นี้จะเรียกว่า vector ของ term นั้นๆ เช่น แถวแรกเรามี term เป็น component และมี vector เป็น (1, 0, 1, 1) เป็นต้น

วิธีการค้นหาคำตอบของ component AND tree จึงได้จากการนำ vector ของ component มาเชื่อมด้วย AND กับ vector ของ tree นั่นเองครับ โดยวิธีการเชื่อมด้วย AND นั้นเราจะพิจารณาทีละตัวแหน่งที่ตรงกัน โดย

• 1 AND 1 มีค่าเป็น 1
• 1 AND 0 มีค่าเป็น 0
• 0 AND 0 มีค่าเป็น 0

vector ของ component คือ 1011 vector ของ tree คือ 1010 component AND tree = 1011 AND 1010 = 1010

เมื่อเราได้ผลลัพธ์สุดท้ายออกมาแล้วให้เอาค่าที่ได้นี้กลับไปเทียบกับ document ที่เราสร้างไว้ในตารางครับซึ่งก็คือ (Vue.js, Ember.js, Angular.js, React.js) เราทำการเทียบผลลัพธ์ที่ได้กับเวกเตอร์ของ document นี้แบบ 1 ต่อ 1 ครับ ถ้า document ตัวไหนตรงกับเลข 0 แสดงว่า document นั้นไม่ใช่ component AND tree แต่ถ้าได้ 1 แสดงว่าเป็น component AND tree

(Vue.js, Ember.js, Angular.js, React.js) = (1, 0, 1, 0) จะได้ว่า

• Vue.js เป็น 1
• Ember.js เป็น 0
• Angular.js เป็น 1
• React.js เป็น 0

จึงสรุปได้ว่ามีเพียงสองเอกสารคือ Vue.js และ Angular.js ที่ตรงกับคำถามในการค้นหา component AND tree นั่นเองครับ

term-document matrix ที่เราใช้งานอยู่มีข้อจำกัดครับ ลองพิจารณาจากตารางข้างบนดูก็ได้ครับ เพื่อนๆจะพบว่าส่วนใหญ่แล้ว term ต่างๆจะมีลักษณะเฉพาะและปรากฎอยู่เพียงไม่กี่เอกสาร ทำให้ตารางของเราอุดมไปด้วยเลขศูนย์ครับ แบบนี้แล้วเราจะเก็บเลขศูนย์ในความหมายว่าไม่มีไว้ทำไมให้เปลืองหน่วยความจำเล่นๆใช่ไหมครับ?

ในบทความถัดไปเราจะมารู้จักกับ Inverted Index วิธีการที่ดีกว่าในการค้นหาด้วย boolean โปรดติดตามครับ