วิธีการ ไล่ระดับใกล้เคียง (การแยกไปข้างหน้าและย้อนกลับ) สำหรับการเรียนรู้เป็นสาขาการวิจัยใน ทฤษฎี การเพิ่มประสิทธิภาพและการเรียนรู้ทางสถิติ ซึ่งศึกษาอัลกอริธึมสำหรับปัญหา การปรับค่าแบบนูน ทั่วไปโดยที่ค่าปรับค่าอาจไม่สามารถหาอนุพันธ์ได้ตัวอย่างหนึ่งคือการปรับค่า (หรือที่เรียกว่า Lasso) ในรูปแบบ ${\displaystyle \ell _{1}}$

${\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}+\lambda \|w\|_{1},\quad {\text{ where }}x_{i}\in \mathbb {R} ^{d}{\text{ and }}y_{i}\in \mathbb {R} .}$

วิธีการไล่ระดับใกล้เคียงเสนอกรอบการทำงานทั่วไปสำหรับการแก้ปัญหาการควบคุมจากทฤษฎีการเรียนรู้ทางสถิติด้วยบทลงโทษที่ปรับให้เหมาะกับการประยุกต์ใช้ปัญหาเฉพาะ^{[ 1 ] [ 2 ]}บทลงโทษที่กำหนดเองดังกล่าวสามารถช่วยเหนี่ยวนำโครงสร้างบางอย่างในการแก้ปัญหา เช่นความเบาบาง (ในกรณีของlasso ) หรือโครงสร้างกลุ่ม (ในกรณีของ group lasso )

วิธีการไล่ระดับแบบใกล้เคียง (Proximal gradient methods)สามารถนำไปใช้ได้ในสถานการณ์ที่หลากหลายสำหรับการแก้ ปัญหา การหาค่าเหมาะสมที่สุดแบบนูน (convex optimization problems) ในรูปแบบต่างๆ

${\displaystyle \min _{x\in {\mathcal {H}}}F(x)+R(x),}$

โดยที่เป็นฟังก์ชันนูนและหาอนุพันธ์ได้ มีเกรเดียนต์ต่อเนื่องแบบลิปชิตซ์เป็น ฟังก์ชัน นูนกึ่งต่อเนื่องล่างซึ่งอาจหาอนุพันธ์ไม่ได้ และเป็นเซตบางเซต โดยทั่วไปคือปริภูมิฮิลเบิร์ตเกณฑ์ปกติที่ว่า จะทำให้ มีค่าน้อยที่สุดก็ต่อเมื่อในบริบทของฟังก์ชันนูนและหาอนุพันธ์ได้นั้น ถูกแทนที่ด้วย ${\displaystyle F}$${\displaystyle R}$${\displaystyle {\mathcal {H}}}$${\displaystyle x}$${\displaystyle F(x)+R(x)}$${\displaystyle \nabla (F+R)(x)=0}$

${\displaystyle 0\in \partial (F+R)(x),}$

โดยที่หมายถึงอนุพันธ์ย่อยของฟังก์ชันนูนที่มีค่าเป็นจำนวนจริง ${\displaystyle \partial \varphi }$${\displaystyle \varphi }$

เมื่อกำหนดฟังก์ชันนูนแล้วตัวดำเนินการที่สำคัญที่ต้องพิจารณาคือตัวดำเนินการใกล้เคียง (proximal operator)ซึ่งกำหนดโดย ${\displaystyle \varphi :{\mathcal {H}}\to \mathbb {R} }$${\displaystyle \operatorname {prox} _{\varphi }:{\mathcal {H}}\to {\mathcal {H}}}$

${\displaystyle \operatorname {prox} _{\varphi }(u)=\operatorname {arg} \min _{x\in {\mathcal {H}}}\varphi (x)+{\frac {1}{2}}\|u-x\|_{2}^{2},}$

ซึ่งกำหนดไว้อย่างดีเนื่องจากความนูนที่เข้มงวดของบรรทัดฐาน ตัวดำเนินการใกล้เคียงสามารถมองได้ว่าเป็นการวางนัยทั่วไปของการฉายภาพ^{[ 1 ] [ 3 ] [ 4 ]} เราเห็นว่าตัวดำเนินการใกล้เคียงมีความสำคัญเพราะเป็นตัวลดค่าต่ำสุดของปัญหาก็ต่อเมื่อ ${\displaystyle \ell _{2}}$${\displaystyle x^{*}}$${\displaystyle \min _{x\in {\mathcal {H}}}F(x)+R(x)}$

${\displaystyle x^{*}=\operatorname {prox} _{\gamma R}\left(x^{*}-\gamma \nabla F(x^{*})\right),}$โดยที่เป็นจำนวนจริงบวกใดๆ^{[ 1 ]}${\displaystyle \gamma >0}$

เทคนิคสำคัญอย่างหนึ่งที่เกี่ยวข้องกับวิธีการไล่ระดับใกล้เคียงคือการแยกส่วนโมโร (Moreau decomposition)ซึ่งแยกตัวดำเนินการเอกลักษณ์ออกเป็นผลรวมของตัวดำเนินการใกล้เคียงสองตัว^{[ 1 ]}กล่าวคือ ให้เป็น ฟังก์ชันกึ่ง ต่อเนื่องล่างและนูนบนปริภูมิเวกเตอร์ เรากำหนดคอน จูเกตเฟนเชล (Fenchel conjugate) ของฟังก์ชัน นี้ให้เป็นฟังก์ชัน ${\displaystyle \varphi :{\mathcal {X}}\to \mathbb {R} }$${\displaystyle {\mathcal {X}}}$${\displaystyle \varphi ^{*}:{\mathcal {X}}\to \mathbb {R} }$

${\displaystyle \varphi ^{*}(u):=\sup _{x\in {\mathcal {X}}}\langle x,u\rangle -\varphi (x).}$

รูปแบบทั่วไปของการสลายตัวของโมโรระบุว่า สำหรับสิ่งใดๆและสิ่งใดๆที่ ${\displaystyle x\in {\mathcal {X}}}$${\displaystyle \gamma >0}$

${\displaystyle x=\operatorname {prox} _{\gamma \varphi }(x)+\gamma \operatorname {prox} _{\varphi ^{*}/\gamma }(x/\gamma ),}$

ซึ่งสำหรับหมายความว่า[ ^{1 ] [ 3 ] การ}แยกส่วน Moreau สามารถมองได้ว่าเป็นการวางนัยทั่วไปของการแยกส่วนเชิงตั้งฉากปกติของปริภูมิเวกเตอร์คล้ายกับข้อเท็จจริงที่ว่าตัวดำเนินการความใกล้เคียงเป็นการวางนัยทั่วไปของการฉายภาพ^{[ 1 ]}${\displaystyle \gamma =1}$${\displaystyle x=\operatorname {prox} _{\varphi }(x)+\operatorname {prox} _{\varphi ^{*}}(x)}$

ในบางสถานการณ์ การคำนวณตัวดำเนินการความใกล้เคียงสำหรับคอนจูเกตอาจง่ายกว่าการคำนวณฟังก์ชันและด้วยเหตุนี้จึงสามารถใช้การแยกส่วนแบบโมโรได้ ซึ่งเป็นกรณีของ group lasso ${\displaystyle \varphi ^{*}}$${\displaystyle \varphi }$

พิจารณา ปัญหา การลดความเสี่ยงเชิงประจักษ์แบบปรับปรุง ด้วยฟังก์ชันความสูญเสียกำลังสอง และใช้ค่ามาตรฐานเป็นค่าปรับลด: ${\displaystyle \ell _{1}}$

${\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}+\lambda \|w\|_{1},}$

โดยที่ ปัญหา การทำให้เป็นระเบียบบางครั้งเรียกว่าlasso ( ตัวดำเนินการหดตัวและการเลือกสัมบูรณ์น้อยที่สุด ) ^{[ 5 ]} ปัญหาการทำให้เป็นระเบียบ ดังกล่าวมีความน่าสนใจเพราะทำให้เกิด โซลูชัน ที่เบาบางนั่นคือ โซลูชันของปัญหาการลดค่าจะมีส่วนประกอบที่ไม่เป็นศูนย์ค่อนข้างน้อย Lasso สามารถมองได้ว่าเป็นการผ่อนคลายแบบนูนของปัญหาที่ไม่นูน ${\displaystyle x_{i}\in \mathbb {R} ^{d}{\text{ and }}y_{i}\in \mathbb {R} .}$${\displaystyle \ell _{1}}$${\displaystyle \ell _{1}}$${\displaystyle w}$

${\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}+\lambda \|w\|_{0},}$

โดยที่หมายถึง"บรรทัดฐาน" ซึ่งเป็นจำนวนรายการที่ไม่เป็นศูนย์ของเวกเตอร์โซลูชันแบบเบาบางมีความน่าสนใจเป็นพิเศษในทฤษฎีการเรียนรู้สำหรับการตีความผลลัพธ์: โซลูชันแบบเบาบางสามารถระบุปัจจัยสำคัญจำนวนน้อยได้^{[ 5 ]}${\displaystyle \|w\|_{0}}$${\displaystyle \ell _{0}}$${\displaystyle w}$

เพื่อความง่าย เราจะพิจารณาเฉพาะปัญหาที่. เพื่อแก้ปัญหานี้ ${\displaystyle \lambda =1}$

${\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}+\|w\|_{1},}$

เราพิจารณาฟังก์ชันเป้าหมายของเราเป็นสองส่วน คือ ส่วนที่เป็นฟังก์ชันนูนที่หาอนุพันธ์ได้และส่วนที่เป็นฟังก์ชันนูนโปรดทราบว่าไม่ใช่ฟังก์ชันนูนอย่างแท้จริง ${\displaystyle F(w)={\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}}$${\displaystyle R(w)=\|w\|_{1}}$${\displaystyle R}$

เรามาคำนวณตัวดำเนินการความใกล้เคียงสำหรับ กันก่อน ขั้นแรก เรามาหาลักษณะเฉพาะอีกแบบหนึ่งของตัวดำเนินการความใกล้เคียงกันดังต่อไปนี้: ${\displaystyle R(w)}$${\displaystyle \operatorname {prox} _{R}(x)}$

${\displaystyle {\begin{aligned}u=\operatorname {prox} _{R}(x)\iff &0\in \partial \left(R(u)+{\frac {1}{2}}\|u-x\|_{2}^{2}\right)\\\iff &0\in \partial R(u)+u-x\\\iff &x-u\in \partial R(u).\end{aligned}}}$

เนื่องจากสามารถคำนวณได้ง่าย: ค่าที่ th ของคือค่าที่แน่นอน ${\displaystyle R(w)=\|w\|_{1}}$${\displaystyle \partial R(w)}$${\displaystyle i}$${\displaystyle \partial R(w)}$

${\displaystyle \partial |w_{i}|={\begin{cases}1,&w_{i}>0\\-1,&w_{i}<0\\\left[-1,1\right],&w_{i}=0.\end{cases}}}$

โดยใช้การกำหนดลักษณะใหม่ของตัวดำเนินการความใกล้เคียงที่ระบุไว้ข้างต้น สำหรับการเลือกและเราจะได้ว่าถูกกำหนดโดยแต่ละรายการ ${\displaystyle R(w)=\|w\|_{1}}$${\displaystyle \gamma >0}$${\displaystyle \operatorname {prox} _{\gamma R}(x)}$

${\displaystyle \left(\operatorname {prox} _{\gamma R}(x)\right)_{i}={\begin{cases}x_{i}-\gamma ,&x_{i}>\gamma \\0,&|x_{i}|\leq \gamma \\x_{i}+\gamma ,&x_{i}<-\gamma ,\end{cases}}}$

ซึ่งเรียกว่าตัวดำเนินการเกณฑ์อ่อน^{[ 1 ] [ 6 ]}${\displaystyle S_{\gamma }(x)=\operatorname {prox} _{\gamma \|\cdot \|_{1}}(x)}$

เพื่อแก้ปัญหาลาโซให้จบสิ้น เราจะพิจารณาสมการจุดตรึงที่แสดงไว้ก่อนหน้านี้:

${\displaystyle x^{*}=\operatorname {prox} _{\gamma R}\left(x^{*}-\gamma \nabla F(x^{*})\right).}$

เนื่องจากเราได้คำนวณรูปแบบของตัวดำเนินการความใกล้เคียงอย่างชัดเจนแล้ว เราจึงสามารถกำหนดขั้นตอนการวนซ้ำจุดตรึงมาตรฐานได้ กล่าวคือ กำหนดค่าเริ่มต้นบางค่าและกำหนด สำหรับ${\displaystyle w^{0}\in \mathbb {R} ^{d}}$${\displaystyle k=1,2,\ldots }$

${\displaystyle w^{k+1}=S_{\gamma }\left(w^{k}-\gamma \nabla F\left(w^{k}\right)\right).}$

โปรดสังเกตการแลกเปลี่ยนที่มีประสิทธิภาพระหว่างเทอมข้อผิดพลาดเชิงประจักษ์และค่าปรับการทำให้เป็นระเบียบวิธีจุดคงที่นี้ได้แยกผลกระทบของฟังก์ชันนูนสองฟังก์ชันที่แตกต่างกันซึ่งประกอบเป็นฟังก์ชันเป้าหมายออกเป็นขั้นตอนการลดระดับความชัน ( ) และขั้นตอนการกำหนดเกณฑ์แบบอ่อน (ผ่าน) ${\displaystyle F(w)}$${\displaystyle R(w)}$${\displaystyle w^{k}-\gamma \nabla F\left(w^{k}\right)}$${\displaystyle S_{\gamma }}$

การบรรจบกันของแผนการจุดคงที่นี้ได้รับการศึกษาอย่างดีในเอกสาร^{[ 1 ] [ 6 ]}และรับประกันได้ภายใต้การเลือกขนาดขั้นตอนและฟังก์ชันการสูญเสีย ที่เหมาะสม (เช่น การสูญเสียกำลังสองที่ใช้ในที่นี้) วิธีการเร่งความเร็วได้รับการแนะนำโดย Nesterov ในปี 1983 ซึ่งปรับปรุงอัตราการบรรจบกันภายใต้สมมติฐานความสม่ำเสมอบางประการ^{[ 7 ]}วิธีการดังกล่าวได้รับการศึกษาอย่างกว้างขวางในปีก่อนหน้า^{[ 8 ]} สำหรับปัญหาการเรียนรู้ทั่วไปมากขึ้นซึ่งตัวดำเนินการความใกล้เคียงไม่สามารถคำนวณได้อย่างชัดเจนสำหรับเงื่อนไขการทำให้เป็นระเบียบบางอย่างแผนการจุดคงที่ดังกล่าวยังคงสามารถดำเนินการได้โดยใช้การประมาณทั้งเกรเดียนต์และตัวดำเนินการความใกล้เคียง^{[ 4 ] [ 9 ]}${\displaystyle \gamma }$${\displaystyle F}$${\displaystyle R}$

ในช่วงทศวรรษที่ผ่านมามีการพัฒนามากมายใน เทคนิค การเพิ่มประสิทธิภาพแบบนูนซึ่งส่งผลต่อการประยุกต์ใช้วิธีการไล่ระดับใกล้เคียงในทฤษฎีการเรียนรู้ทางสถิติ ในที่นี้เราจะสำรวจหัวข้อสำคัญบางประการที่สามารถปรับปรุงประสิทธิภาพการทำงานของอัลกอริทึมในทางปฏิบัติของวิธีการเหล่านี้ได้อย่างมาก^{[ 2 ] [ 10 ]}

ในแผนการวนซ้ำจุดคงที่

${\displaystyle w^{k+1}=\operatorname {prox} _{\gamma R}\left(w^{k}-\gamma \nabla F\left(w^{k}\right)\right),}$

สามารถอนุญาตให้ใช้ขนาดขั้นตอนที่แปรผันได้แทนที่จะเป็นค่าคงที่มีการเสนอแผนการปรับขนาดขั้นตอนแบบปรับได้มากมาย ในเอกสาร ^{[ 1 ] [ 4 ] [ 11 ] [ 12 ]}การประยุกต์ใช้แผนการเหล่านี้^{[ 2 ] [ 13 ]} ชี้ให้เห็นว่าสิ่งเหล่านี้สามารถปรับปรุงจำนวนรอบที่จำเป็นสำหรับการบรรจบกันของจุดคงที่ได้อย่างมาก ${\displaystyle \gamma _{k}}$${\displaystyle \gamma }$

การปรับค่าแบบ Elastic netเป็นทางเลือกแทนการปรับค่าแบบบริสุทธิ์ ปัญหาของการปรับค่าแบบ Lasso ( ) เกี่ยวข้องกับเทอมปรับค่าซึ่งไม่ใช่ฟังก์ชันนูนอย่างเคร่งครัด ดังนั้น คำตอบของสมการ โดยที่เป็นฟังก์ชันความสูญเสียเชิงประจักษ์บางอย่าง จึงไม่เป็นเอกลักษณ์ ปัญหานี้มักหลีกเลี่ยงได้โดยการเพิ่มเทอมนูนอย่างเคร่งครัดเพิ่มเติม เช่นการปรับค่าแบบนอร์ม ตัวอย่างเช่น เราสามารถพิจารณาปัญหา ${\displaystyle \ell _{1}}$${\displaystyle \ell _{1}}$${\displaystyle R(w)=\|w\|_{1}}$${\displaystyle \min _{w}F(w)+R(w),}$${\displaystyle F}$${\displaystyle \ell _{2}}$

${\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}+\lambda \left((1-\mu )\|w\|_{1}+\mu \|w\|_{2}^{2}\right),}$

โดยที่เทอมปรับโทษนั้นเป็นแบบนูนอย่างเคร่งครัด ดังนั้นปัญหาการลดค่าให้น้อยที่สุดจึงมีคำตอบเดียวเท่านั้น พบว่าสำหรับค่าที่เล็กพอ เทอมปรับโทษเพิ่มเติมจะทำหน้าที่เป็นตัวปรับสภาพเบื้องต้นและสามารถปรับปรุงการล convergence ได้อย่างมากโดยไม่ส่งผลเสียต่อความเบาบางของคำตอบ^{[ 2 ] [ 14 ]}${\displaystyle x_{i}\in \mathbb {R} ^{d}{\text{ and }}y_{i}\in \mathbb {R} .}$${\displaystyle 0<\mu \leq 1}$${\displaystyle \lambda \left((1-\mu )\|w\|_{1}+\mu \|w\|_{2}^{2}\right)}$${\displaystyle \mu >0}$${\displaystyle \mu \|w\|_{2}^{2}}$

วิธีการไล่ระดับแบบใกล้เคียง (Proximal gradient methods) เป็นกรอบการทำงานทั่วไปที่สามารถนำไปใช้กับปัญหาต่างๆ มากมายในทฤษฎีการเรียนรู้ทางสถิติปัญหาบางอย่างในการเรียนรู้มักเกี่ยวข้องกับข้อมูลที่มีโครงสร้างเพิ่มเติมที่ทราบล่วงหน้าในช่วงหลายปีที่ผ่านมา มีการพัฒนาใหม่ๆ ที่รวมเอาข้อมูลเกี่ยวกับโครงสร้างกลุ่มเข้ามาเพื่อสร้างวิธีการที่เหมาะสมกับการใช้งานที่แตกต่างกัน ในที่นี้เราจะสำรวจวิธีการดังกล่าวบางส่วน

Group lasso เป็นการวางนัยทั่วไปของวิธี lassoเมื่อคุณลักษณะถูกจัดกลุ่มเป็นบล็อกที่ไม่ทับซ้อนกัน^{[ 15 ]}สมมติว่าคุณลักษณะถูกจัดกลุ่มเป็นบล็อกในที่นี้เราใช้เป็นค่าปรับการทำให้เป็นระเบียบ ${\displaystyle \{w_{1},\ldots ,w_{G}\}}$

${\displaystyle R(w)=\sum _{g=1}^{G}\|w_{g}\|_{2},}$

ซึ่งเป็นผลรวมของค่ามาตรฐานบนเวกเตอร์คุณลักษณะที่สอดคล้องกันสำหรับกลุ่มต่างๆ การวิเคราะห์ตัวดำเนินการความใกล้เคียงที่คล้ายคลึงกันข้างต้นสามารถใช้ในการคำนวณตัวดำเนินการความใกล้เคียงสำหรับค่าปรับนี้ได้ โดยที่ค่าปรับแบบลาซโซมีตัวดำเนินการความใกล้เคียงซึ่งเป็นการกำหนดเกณฑ์แบบอ่อนบนแต่ละองค์ประกอบ ตัวดำเนินการความใกล้เคียงสำหรับลาซโซแบบกลุ่มจะเป็นการกำหนดเกณฑ์แบบอ่อนบนแต่ละกลุ่ม สำหรับกลุ่มเรามีตัวดำเนินการความใกล้เคียงของซึ่งกำหนดโดย ${\displaystyle \ell _{2}}$${\displaystyle w_{g}}$${\displaystyle \lambda \gamma \left(\sum _{g=1}^{G}\|w_{g}\|_{2}\right)}$

${\displaystyle {\widetilde {S}}_{\lambda \gamma }(w_{g})={\begin{cases}w_{g}-\lambda \gamma {\frac {w_{g}}{\|w_{g}\|_{2}}},&\|w_{g}\|_{2}>\lambda \gamma \\0,&\|w_{g}\|_{2}\leq \lambda \gamma \end{cases}}}$

กลุ่มที่ th อยู่ที่ไหน${\displaystyle w_{g}}$${\displaystyle g}$

ตรงกันข้ามกับ lasso การได้มาซึ่งตัวดำเนินการความใกล้เคียงสำหรับ group lasso อาศัย^การแยกส่วน Moreauโดยที่ตัวดำเนินการความใกล้เคียงของคอนจูเกตของโทษ group lasso จะกลายเป็นการฉายภาพลงบนลูกบอลของบรรทัดฐานคู่ [ ^{2 ]}

ตรงกันข้ามกับปัญหา group lasso ซึ่งคุณลักษณะต่างๆ ถูกจัดกลุ่มเป็นบล็อกที่ไม่ทับซ้อนกัน อาจเป็นกรณีที่คุณลักษณะที่จัดกลุ่มนั้นทับซ้อนกันหรือมีโครงสร้างแบบซ้อนกัน การวางนัยทั่วไปของ group lasso ดังกล่าวได้รับการพิจารณาในบริบทต่างๆ^{[ 16 ] [ 17 ] [ 18 ] [ 19 ]}สำหรับกลุ่มที่ทับซ้อนกัน วิธีการทั่วไปวิธีหนึ่งคือlatent group lassoซึ่งแนะนำตัวแปรแฝงเพื่ออธิบายการทับซ้อน^{[ 20 ] [ 21 ]}โครงสร้างกลุ่มแบบซ้อนกันได้รับการศึกษาในการทำนายโครงสร้างแบบลำดับชั้นและด้วยกราฟแบบไม่มีวงจรทิศทาง^{[ 18 ]}

• การวิเคราะห์นูน
• วิธีการไล่ระดับใกล้เคียง
• การทำให้เป็นระเบียบ
• ทฤษฎีการเรียนรู้เชิงสถิติ