ไม่ว่าคุณคือนักวิทยาการคอมพิวเตอร์หรือแค่ต้องการจะสำรวจสู่โลกมหัศจรรย์ของอัลกอริทึม หนังสือเล่มนี้เหมาะกับคุณเลยค่ะ เพราะว่า มันสามารถอธิบายสิ่งที่ซับซ้อนให้เป็นคำพูดง่าย ๆ ซึ่งเข้ากับพาธที่ BB กำลังจะเริ่มทำในบล็อกนี้เลย พาธนี้ BB ตั้งชื่อว่า yoybooks ซึ่งจะเลือกบทความและหนังสือที่น่าสนใจเอามาย่อยสรุปลงบล็อก และบทความนี้ก็เป็นบทความแรกที่BB เอามาแปล หวังว่าทุกคนที่เข้ามาอ่านคงจะชอบกัน
Algorithms to Live By จะพาพวกเราเดินทางไปกับ 11 แนวคิดของโลกวิทยาการคอมพิวเตอร์ที่เราใช้กันอยู่ในชีวิตประจำวันซึ่งบางอย่างเราอาจจะรู้แล้วหรือยังไม่รู้ก็เป็นได้
1. Optimal Stopping
ลองนึกภาพสถานการณ์ต่อไปนี้:
คุณต้องการจ้างเลขาฯ จากกลุ่มผู้สมัครจำนวนหนึ่ง
คุณต้องสัมภาษณ์ผู้สมัคร ทีละคน
และตัดสินใจว่าจะ จ้าง หรือ ไม่จ้าง หลังจากการสัมภาษณ์ แต่ละครั้ง
หากว่าคุณปฏิเสธคนหนึ่ง คุณจะไม่สามารถกลับมาหาพวกเขาได้
แล้วถ้าหากคุณจ้างใครสักคน กระบวนการสัมภาษณ์ทั้งหมดจะหยุด
และคุณก็จะได้เลขาคนใหม่
คำถามคือ คุณจะเพิ่มโอกาสในการหาเลขาที่ดีที่สุดจากในกลุ่มได้อย่างไร?
นี่คือปัญหา Secretary Problem ที่มีชื่อเสียงและเป็นพื้นฐานในการการอภิปรายในบทนี้ค่ะ
คุณอาจยังไม่ต้องการจ้างคนแรกที่คุณสัมภาษณ์ เนื่องจากจุดนี้คุณยังไม่รู้ว่า อะไรคือตัวตั้งต้น (baseline) และคุณก็ไม่ต้องการจ้างคนสุดท้ายเช่นกัน: เพราะคุณอาจจะพลาดโอกาสพบผู้สมัครที่ดีที่สุดของคุณคนต่อไปก็ได้
ดังนั้นกลยุทธ์ที่ดีที่สุดในการสัมภาษณ์และการปฏิเสธผู้สมัครสองสามคนแรกไม่ว่าพวกเขาจะดีแค่ไหน: เพียงแค่ต้องมีค่าพื้นฐาน (baseline) ก่อนแล้วจึงว่าจ้างผู้สมัครที่ดีที่สุดจากที่คุณเคยเห็นมา
จุดที่ดีที่สุดนี้จะเป็น 1 / e หรือประมาณ 37%
ให้ปฏิเสธผู้สมัคร 37% จากนั้นค่อยจ้างคนต่อไปที่ดีกว่าทุกคนที่คุณเคยเห็น
ตัวแปรต่างๆของ ปัญหาการจ้างเลขานุการ และ กฎ 37% นี้ได้ถูกนำไปใช้ในชีวิตจริงอีกอย่างหลากหลายเช่นกัน ตั้งแต่การออกเดท การจอดรถ ไปจนถึงการซื้อ / ขายบ้าน
และการรู้ว่าเมื่อใดที่ควรหยุดมอง ก่อนที่คุณจะตื่นเต้นเกินไป – ปล.: กลยุทธ์นี้ล้มเหลว 63% นะ 555
2. Explore/Exploit
วันเสาร์เป็นวัน cheat day ของคุณ คุณจะเปิดแอพ วงใน เพื่อสำรวจคาเฟ่ และร้านอาหารใหม่ๆ หรือว่าคุณจะกลับไปที่ร้านอาหารตามสั่งที่คุณอยากทานมาตลอดทั้งสัปดาห์ดี? คุณจะฟังเพลย์ลิส Spotify รายวัน (your Daily Mix) บนแอพ Spotify หรือว่าจะกลับไปฟังเพลย์ลิสอัลบั้มโปรดของคุณดี?
อันที่จริงแล้ว คุณแค่สำรวจหรือคุณจะใช้ประโยชน์จากมันกันแน่?
ตั้งแต่การทดสอบ A / B บนเว็บไซต์ ไปจนถึงการทดสอบ A / B ในยาของมนุษย์ผ่านทางการทดลองทางคลินิก วิศวกรซอฟต์แวร์และบริษัทยาต่างกำลังพยายามหาจุดที่พอดีอยู่
นอกเหนือจากนี้ก็มีการพูดถึงกลยุทธ์ต่างๆ เช่น“ Win-Stay, Lose-Shift” เพื่อการเอาชนะตู้สล็อตแมชชีนในคาสิโน (รู้จักกันอย่างเป็นทางการว่าปัญหาโจรติดอาวุธหลายแขน – Multi-armed bandit)
บทนี้จะช่วยให้คุณประมวลความคิดดีขึ้นในครั้งต่อไปที่คุณต้องเลือกระหว่างสิ่งที่ใช้ล่าสุดกับสิ่งที่ดีที่สุด
3. Sorting
อัลกอริธึมการเรียงลำดับ มักเป็นวิชาพื้นฐานอันดับแรกๆที่หลักสูตรวิทยาการคอมพิวเตอร์ครอบคลุม หัวข้อที่กล่าวถึงในบทนี้เริ่มตั้งแต่สัญลักษณ์ Big O ที่ทำหน้าที่เป็นปทัฏฐานในการวัดประสิทธิภาพของอัลกอริทึม ไปจนถึงกลุ่มของอัลกอริทึมที่มีการเรียงลำดับตัวมันเอง:the bubble, insertion, merge and quick sorts
นอกเหนือจากนั้นการเรียงลำดับยังช่วยสำหรับการค้นหา: ถ้าคุณมีคอลเลกชั่นของการเรียงลำดับเอาไว้ การค้นหาก็จะง่ายขึ้นมาก บทนี้จบลงด้วยการอภิปรายเกี่ยวกับการแข่งขันประเภทต่างๆ: round-robin, ladder, elimination single และอื่น ๆ ท้ายที่สุดการแข่งขันก็เป็นอีกปัญหาหนึ่งในการเรียงลำดับ และเช่นกันกับการจัดลำดับชั้นของการปกครองในอาณาจักรสัตว์ (และมนุษย์) การจัดเรียงสิ่งต่าง ๆ นี้แหละที่ทำให้ชีวิตง่ายขึ้น
4. Caching
หรือลำดับชั้นของหน่วยความจำ – และสิ่งที่ควรนึกในใจเป็นอันดับแรก สิ่งที่ต้องใช้ปากกากับกระดาษจดเอาไว้ หรือแอพบันทึกข้อความต่างๆ การอภิปรายเกี่ยวกับการเก็บข้อมูลที่หน่วยความจำสำรอง(แคชชิ่ง) จำเป็นต้องพิจารณาถึงกลยุทธ์ต่าง ๆ สำหรับการตัดสินใจว่าสิ่งใดที่อยู่ในแคช
– กลยุทธ์อย่างการสุ่มจับ, เข้าก่อนออกก่อน, ที่ใช้ล่าสุด และอื่น
ๆ ที่ช่วยได้
มีอย่างหนึ่งที่ชอบมากคือ Least Recently Used วิธีนี้สามารถนำไปใช้กับห้องสมุดได้อย่างมีประสิทธิภาพ:
แทนที่จะวางหนังสือที่นำมาคืนกลับไปวางบนชั้นวางของห้องสมุดในทันที ห้องสมุดสามารถนำพวกมันวางในส่วนของแคชก่อน
– เพราะสุดท้ายแล้วหนังสือพวกนี้ที่ถูกยืมล่าสุดส่วนใหญ่แล้วจะมีแนวโน้มถูกยืมใหม่อีกรอบ
5. Scheduling
คุณทำสิ่งต่าง ๆ ให้สำเร็จได้ อย่างไร?
คุณจัดตารางวันของคุณ อย่างไร?
คุณจะจัดตารางงานอย่างไรเพื่อให้ได้งานมากที่สุดในเวลาอันน้อยที่สุด? นอกจากนี้ คุณจะจัดการกับสถานการณ์ที่งานที่มีลำดับความสำคัญต่ำกำลังขัดขวางงานที่มีลำดับความสำคัญสูงกว่าได้อย่างไร ?
และถ้าเกิดคุณกำลังติดอยู่ในการเลือกทำงานที่มีลำดับความสำคัญสูงคุณจะทำอย่างไร?
บทนี้เป็นเหมือนการเยือนเพื่อนเก่าอีกกลุ่มหนึ่งจากระดับปริญญาตรีเลยค่ะ: ในตอนนั้นคุณคงไม่ได้คิดถึงงานในอนาคตหรือการฟาดฟันกับการทำงานประจำวันของคุณมากเท่าไหร่ใช่มั้ยล่ะ
6. Bayes’s Rule
สมมติว่าคุณรู้กฎของเบย์อยู่แล้ว แต่ถ้าคุณยังไม่รู้ มันคือวิธีง่ายๆในการพิจารณาถึงความเป็นไปได้ของสิ่งหนึ่ง A แล้วเกิดเป็น B ได้อย่างไร โดยมักแสดงเป็น P (A | B) สมมติว่าคุณมีข้อมูลที่ดีมาก่อน: มีโอกาสที่ทั้งสองสิ่งจะเกิดขึ้นและคุณรู้ว่าสิ่งที่น่าจะเกิดขึ้นจะเป็นไปในอีกทาง: B | A ฉันจะเขียนมันออกมาให้ดู ในการหาผลลัพท์ของ P (A | B) ให้คูณ P (B | A) ด้วย P (A) แล้วหารด้วย P (B) ซึ่งมันง่ายมากจริงๆนะ เพียงให้แน่ใจว่าข้อมูลตั้งต้นของคุณดี : คำแนะนำที่ดีในบทนี้คือการได้รับข่าวสารที่ไม่มากไป เพราะจะทำให้คาดการณ์เหตุการณ์แย่ลง หลักการของโคเปอร์นิคัสกล่าวว่าการคาดการณ์ที่ดีในการบอกว่าสิ่งหนึ่งจะอยู่ได้นานแค่ไหนให้ดูว่ามันอยู่มานานแค่ไหนแล้ว
7. Overfitting
บทนี้จะเน้นในเรื่องของความซับซ้อนและทำให้แบบจำลองของคุณง่ายที่สุดเท่าที่จะทำได้ ไม่เพียงแค่มันจะทำงานได้ดีขึ้น แต่เค้าสามารถยืนยันได้ว่าความเรียบง่ายนั้นควรเป็นเป้าหมายในตัวมันเอง เพื่อนๆที่อยู่ในวงการ Machine Learning น่าจะชอบการอภิปรายไอเดียเกี่ยวกับ cross–validation (การเก็บข้อมูลบางส่วนกลับไปทดสอบ หลังจากนั้นคุณจะพบว่าแบบจำลองการเรียนรู้ของคุณทำได้ดี ไม่ใช่แค่กับข้อมูลตัวอย่างของคุณ), regularization :การทำให้เป็นมาตรฐาน (ทำโมเดลของคุณให้รองรับความซับซ้อน: ดังนั้นความเรียบง่ายเป็นจึงส่วนหนึ่งของเป้าหมาย) เช่น การหยุดตั้งแต่เนิ่น ๆ เป็นต้น
8. Relaxation
ความสมบูรณ์แบบคือศัตรูของสรรพสิ่ง ดังนั้นมันเป็นธรรมดาที่จะปล่อยวางบ้างในบางครั้ง ปัญหาใหญ่จำนวนมากในวิทยาการคอมพิวเตอร์นั้นรู้จักกันว่า NP–Hard Problems เป็นสิ่งที่ไม่สามารถแก้ได้ สำหรับชุดข้อมูลของจริงนั้นเราไม่มีทางแก้ปัญหาด้วยวิธีที่สมบูรณ์แบบได้ในระยะเวลาหนึ่งๆ ตัวอย่างที่มีชื่อเสียงที่สุดของปัญหานี้คือปัญหาการเดินทางของพนักงานขาย: หาเส้นทางที่พนักงานขายควรเดินทางไปเยี่ยมแต่ละจุดทั้งหมดด้วยระยะทางที่น้อยที่สุด: ความเป็นไปได้คือมีหลายวิธีที่ในการพิจารณาแต่ละจุด การผ่อนคลายข้อ จำกัด และการแก้ปัญหาที่คล้ายกัน แต่ปัญหาที่ง่ายกว่านั้นน่าจะเป็นคำตอบ การปรับปัญหาให้เหมาะสมมีสองส่วนคือ กฎ และ การบันทึกคะแนน มันอาจจะคุ้มค่าที่จะฝ่าฝืนกฎบางครั้งและได้คะแนนถ้ามันทำให้คุณก้าวต่อไปได้ (หรือที่เรียกว่า Lagrangian Relaxation)
9. Randomness
การสุ่มเป็นอีกวิธีหนึ่งที่ใช้ได้ดีเมื่อไม่มีสิ่งอื่นจะใช้ เริ่มต้นด้วยวิธีมอนติคาร์โล บทนี้พูดถึงอัลกอริธึมแบบสุ่ม – และคุณต้องตกหลุมรักส่วนนี้ของวิทยาศาสตร์คอมพิวเตอร์แน่นอน เพราะตรงนี้มันเป็นที่ๆทุกสิ่งหยุดอยู่บนความไม่แน่นอน ไม่เพียงเท่านั้น การสุ่มสามารถช่วยคุณในการ optimization ชอบมากตรงที่บทนี้จบลงด้วยการอภิปรายเกี่ยวกับความคิดสร้างสรรค์ และวิวัฒนาการของการสุ่ม ท้ายสุดแล้วคุณสามารถสร้างงานศิลปะที่เกิดจากรูปแบบของการสุ่มได้อีกด้วย
10. Networking
Packet Switching, ACKnowledgements, , triple handshakes, exponential backoff และอัลกอรึทึมของการให้อภัย: การสร้างเครือข่ายเป็นหัวข้อที่เต็มไปด้วยอัญมณีเลยทีเดียว เพราะการเชื่อมโยงกับผู้คนเป็นหนึ่งในพื้นฐานและมีผลกระทบมากที่สุดของวิทยาการคอมพิวเตอร์
– เรากำลังพูดถึงอินเทอร์เน็ต วิธีการควบคุมการไหล การหลีกเลี่ยงความแออัด (Additive Increase, Multiplicative Decrease) วิธีการสร้าง Backchannels (และบทบาทของสัญญาณรบกวนสีขาว และเกร็ดเล็กๆน้อยๆในการสนทนาในชีวิตประจำวัน) และวิธีการหลีกเลี่ยง bufferbloats หัวข้อทั้งหมดนี้เป็นส่วนหนึ่งในคลาส คอมพิวเตอร์เน็ตเวิร์ค แต่มันดีที่ได้เห็นอะไรในมุมมองใหม่ๆค่ะ
