การถดถอยเชิงเส้นและวิธีการกู้คืน

ที่มา: xkcd

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

แต่บทความนี้ไม่เกี่ยวกับการใช้การถดถอยเชิงเส้นในการแก้ปัญหาเชิงปฏิบัติ ที่นี่เราจะพิจารณาคุณสมบัติที่น่าสนใจของการนำอัลกอริธึมแบบกระจายไปใช้เพื่อการกู้คืนซึ่งเราพบเมื่อเขียนโมดูลการเรียนรู้ของเครื่อง อาปาเช่จุดชนวน. คณิตศาสตร์พื้นฐานเล็กๆ น้อยๆ การเรียนรู้ของเครื่อง และการคำนวณแบบกระจายสามารถช่วยให้คุณทราบวิธีดำเนินการถดถอยเชิงเส้น แม้ว่าข้อมูลของคุณจะถูกกระจายไปยังโหนดหลายพันโหนดก็ตาม

มันเกี่ยวกับอะไร?

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

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

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

ที่มา: วิกิพีเดีย

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

วิธีความน่าจะเป็นสูงสุด

ดังนั้นเราจึงสันนิษฐานว่ามีสัญญาณรบกวนที่กระจายตามปกติแบบสุ่ม จะทำอย่างไรในสถานการณ์เช่นนี้? สำหรับกรณีนี้ในทางคณิตศาสตร์ก็มีและใช้กันอย่างแพร่หลาย วิธีความน่าจะเป็นสูงสุด. ในระยะสั้นสาระสำคัญอยู่ที่การเลือก ฟังก์ชันความน่าจะเป็น และการเพิ่มประสิทธิภาพสูงสุดในภายหลัง

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

เรามาทดแทนกันตอนนี้เลย и ตัวแปรที่เราต้องการคือ:

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

ซึ่งในทางกลับกันก็ต้องลดฟังก์ชันต่อไปนี้ให้เหลือน้อยที่สุด:

โดยวิธีการนี้เรียกว่าวิธีการ กำลังสองน้อยที่สุด. บ่อยครั้งข้อพิจารณาข้างต้นทั้งหมดถูกละเว้น และใช้วิธีนี้เพียงอย่างเดียว

การสลายตัวของ QR

ค่าต่ำสุดของฟังก์ชันข้างต้นสามารถพบได้โดยการหาจุดที่ความชันของฟังก์ชันนี้เป็นศูนย์ และการไล่ระดับสีจะถูกเขียนดังนี้:

การสลายตัวของ QR เป็นวิธีเมทริกซ์สำหรับการแก้ปัญหาการย่อเล็กสุดที่ใช้ในวิธีกำลังสองน้อยที่สุด ในเรื่องนี้ เราเขียนสมการใหม่ในรูปแบบเมทริกซ์:

เราก็เลยแยกเมทริกซ์ออกมา ถึงเมทริกซ์ и และทำการแปลงเป็นชุด (อัลกอริธึมการสลายตัวของ QR เองจะไม่ได้รับการพิจารณาที่นี่ เฉพาะการใช้งานที่เกี่ยวข้องกับงานที่มีอยู่เท่านั้น):

มดลูก เป็นมุมฉาก สิ่งนี้ทำให้เราสามารถกำจัดงานได้ :

และถ้าคุณเปลี่ยน บน จากนั้นมันจะได้ผล . เมื่อพิจารณาแล้วว่า เป็นเมทริกซ์สามเหลี่ยมด้านบน มีลักษณะดังนี้:

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

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

การไล่ระดับโคตร

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

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

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

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

LSQR

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

วิธี LSQR ขึ้นอยู่กับ ขั้นตอนการทำให้เป็นแนวทแยง. นี่เป็นขั้นตอนการวนซ้ำ การวนซ้ำแต่ละครั้งประกอบด้วยขั้นตอนต่อไปนี้:


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

เป็นแนวทางนี้ที่ใช้เมื่อนำการถดถอยเชิงเส้นไปใช้ Apache Ignite ML.

ข้อสรุป

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

ที่มา: will.com