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