BFGS หน่วยความจำจำกัด ( L-BFGSหรือLM-BFGS ) เป็น อัลก อริธึมการหาค่าเหมาะสมที่สุด ในกลุ่มวิธีควาซี-นิวตันที่ประมาณค่าอัลกอริธึม Broyden–Fletcher–Goldfarb–Shanno (BFGS) โดยใช้ หน่วยความจำคอมพิวเตอร์จำนวนจำกัด^{[ 1 ]}เป็นอัลกอริธึมที่ได้รับความนิยมสำหรับการประมาณค่าพารามิเตอร์ใน การเรียน รู้ของเครื่อง^{[ 2 ] [ 3 ]}ปัญหาเป้าหมายของอัลกอริธึมนี้คือการลดค่าให้น้อยที่สุดเหนือค่าที่ไม่จำกัดของเวกเตอร์จริงโดยที่เป็นฟังก์ชันสเกลาร์ที่หาอนุพันธ์ได้ ${\displaystyle f(\mathbf {x} )}$${\displaystyle \mathbf {x} }$${\displaystyle f}$

เช่นเดียวกับ BFGS ดั้งเดิม L-BFGS ใช้การประมาณค่าเมทริกซ์เฮสเซียน ผกผัน เพื่อนำทางการค้นหาผ่านพื้นที่ตัวแปร แต่ในขณะที่ BFGS เก็บค่าประมาณหนาแน่นของเมทริกซ์เฮสเซียนผกผัน ( โดยที่ nคือจำนวนตัวแปรในปัญหา) L-BFGS จะเก็บเพียงเวกเตอร์ไม่กี่ตัวที่แสดงถึงค่าประมาณโดยปริยาย เนื่องจากความต้องการหน่วยความจำเชิงเส้นที่เกิดขึ้น วิธี L-BFGS จึงเหมาะอย่างยิ่งสำหรับปัญหาการหาค่าเหมาะสมที่สุดที่มีตัวแปรจำนวนมาก แทนที่จะใช้เมทริกซ์เฮสเซียนผกผันH _k L-BFGS จะเก็บประวัติการอัปเดตตำแหน่งxและเกรเดียนต์ ∇ f ( x ) ในอดีต m ครั้ง โดยทั่วไปขนาดของประวัติmอาจมีขนาดเล็ก (มักจะ) การอัปเดตเหล่านี้ใช้เพื่อดำเนินการโดยปริยายที่ต้องใช้ผลคูณเวกเตอร์ H _k${\displaystyle n\times n}$${\displaystyle m<10}$

อัลกอริทึมเริ่มต้นด้วยการประมาณค่าเบื้องต้นของค่าที่เหมาะสมที่สุดและดำเนินการปรับปรุงค่าประมาณนั้นซ้ำๆ ด้วยลำดับของการประมาณค่าที่ดีขึ้นเรื่อยๆอนุพันธ์ของฟังก์ชันถูกใช้เป็นตัวขับเคลื่อนหลักของอัลกอริทึมเพื่อระบุทิศทางของการลดลงที่ชันที่สุด และยังใช้ในการสร้างค่าประมาณของเมทริกซ์เฮสเซียน (อนุพันธ์อันดับสอง) ของด้วย ${\displaystyle \mathbf {x} _{0}}$${\displaystyle \mathbf {x} _{1},\mathbf {x} _{2},\ldots }$${\displaystyle g_{k}:=\nabla f(\mathbf {x} _{k})}$${\displaystyle f(\mathbf {x} )}$

L-BFGS มีคุณสมบัติหลายอย่างร่วมกับอัลกอริธึมควาซี-นิวตันอื่นๆ แต่แตกต่างกันมากในวิธีการคูณเมทริกซ์-เวกเตอร์ โดยที่คือทิศทางโดยประมาณของนิวตัน คือเกรเดียนต์ปัจจุบัน และคือเมทริกซ์เฮสเซียนผกผัน มีแนวทางที่เผยแพร่แล้วหลายวิธีที่ใช้ประวัติการอัปเดตเพื่อสร้างเวกเตอร์ทิศทางนี้ ในที่นี้ เราจะนำเสนอแนวทางทั่วไปที่เรียกว่า "การเรียกซ้ำแบบสองลูป" ^{[ 4 ] [ 5 ]}${\displaystyle d_{k}=-H_{k}g_{k}}$${\displaystyle d_{k}}$${\displaystyle g_{k}}$${\displaystyle H_{k}}$

เรากำหนดให้ คือตำแหน่งในการวนซ้ำครั้งที่kและคือฟังก์ชันที่กำลังหาค่าต่ำสุด โดยเวกเตอร์ทั้งหมดเป็นเวกเตอร์คอลัมน์ นอกจากนี้ เรายังสมมติว่าเราได้จัดเก็บ การอัปเดต m ครั้งล่าสุด ในรูปแบบ ${\displaystyle x_{k}}$${\displaystyle g_{k}\equiv \nabla f(x_{k})}$${\displaystyle f}$

${\displaystyle s_{k}=x_{k+1}-x_{k}}$

${\displaystyle y_{k}=g_{k+1}-g_{k}}$.

เรากำหนดและจะเป็นค่าประมาณ 'เริ่มต้น' ของเมทริกซ์เฮสเซียนผกผัน ซึ่งเป็นจุดเริ่มต้น ของการประมาณค่าของเราในรอบการทำซ้ำ k${\displaystyle \rho _{k}={\frac {1}{y_{k}^{\top }s_{k}}}}$${\displaystyle H_{k}^{0}}$

อัลกอริทึมนี้ใช้การเรียกซ้ำแบบ BFGS สำหรับเมทริกซ์เฮสเซียนผกผัน ดังนี้

${\displaystyle H_{k+1}=(I-\rho _{k}s_{k}y_{k}^{\top })H_{k}(I-\rho _{k}y_{k}s_{k}^{\top })+\rho _{k}s_{k}s_{k}^{\top }.}$

สำหรับค่าk ที่กำหนดไว้ เรากำหนดลำดับของเวกเตอร์เป็นและจากนั้นอัลกอริทึมแบบเรียกซ้ำสำหรับการคำนวณจากคือการกำหนดและ นอกจาก นี้เรายังกำหนดลำดับของเวกเตอร์อีกชุดหนึ่งเป็นมีอัลกอริทึมแบบเรียกซ้ำอีกแบบหนึ่งสำหรับการคำนวณเวกเตอร์เหล่านี้ ซึ่งก็คือการกำหนดและจากนั้นกำหนดและ แบบเรียกซ้ำ ค่าของจะเป็นทิศทางการเพิ่มขึ้นของเรา ${\displaystyle q_{km},\ldots ,q_{k}}$${\displaystyle q_{k}:=g_{k}}$${\displaystyle q_{i}:=(I-\rho _{i}y_{i}s_{i}^{\top })q_{i+1}}$${\displaystyle q_{i}}$${\displaystyle q_{i+1}}$${\displaystyle \alpha _{i}:=\rho _{i}s_{i}^{\top }q_{i+1}}$${\displaystyle q_{i}=q_{i+1}-\alpha _{i}y_{i}}$${\displaystyle z_{km},\ldots ,z_{k}}$${\displaystyle z_{i}:=H_{i}q_{i}}$${\displaystyle z_{km}=H_{k}^{0}q_{km}}$${\displaystyle \beta _{i}:=\rho _{i}y_{i}^{\top }z_{i}}$${\displaystyle z_{i+1}=z_{i}+(\alpha _{i}-\beta _{i})s_{i}}$${\displaystyle z_{k}}$

ดังนั้นเราสามารถคำนวณทิศทางการลงได้ดังนี้:

${\displaystyle {\begin{array}{l}q=g_{k}\\{\mathtt {For}}\ i=k-1,k-2,\ldots ,k-m\\\qquad \alpha _{i}=\rho _{i}s_{i}^{\top }q\\\qquad q=q-\alpha _{i}y_{i}\\\gamma _{k}={\frac {s_{k-m}^{\top }y_{k-m}}{y_{k-m}^{\top }y_{k-m}}}\\H_{k}^{0}=\gamma _{k}I\\z=H_{k}^{0}q\\{\mathtt {For}}\ i=k-m,k-m+1,\ldots ,k-1\\\qquad \beta _{i}=\rho _{i}y_{i}^{\top }z\\\qquad z=z+s_{i}(\alpha _{i}-\beta _{i})\\z=-z\end{array}}}$

สูตรนี้ให้ทิศทางการค้นหาสำหรับปัญหาการหาค่าต่ำสุด นั่นคือ. สำหรับปัญหาการหาค่าสูงสุด จึงควรใช้-zแทน โปรดทราบว่าเมทริกซ์เฮสเซียนผกผันโดยประมาณเริ่มต้นถูกเลือกให้เป็นเมทริกซ์แนวทแยงหรือแม้แต่เมทริกซ์เอกลักษณ์ เนื่องจากวิธีนี้มีประสิทธิภาพทางตัวเลขมากกว่า ${\displaystyle z=-H_{k}g_{k}}$${\displaystyle H_{k}^{0}}$

การปรับขนาดของเมทริกซ์เริ่มต้นทำให้มั่นใจได้ว่าทิศทางการค้นหาได้รับการปรับขนาดอย่างเหมาะสม ดังนั้นความยาวขั้นตอนหน่วยจึงได้รับการยอมรับในการวนซ้ำส่วนใหญ่การค้นหาเส้นแบบ Wolfeใช้เพื่อให้แน่ใจว่าเงื่อนไขความโค้งเป็นไปตามที่กำหนด และการอัปเดต BFGS มีเสถียรภาพ โปรดทราบว่าซอฟต์แวร์บางตัวใช้การค้นหาเส้นแบบ Armijo backtrackingแต่ไม่สามารถรับประกันได้ว่าเงื่อนไขความโค้งจะเป็นไปตามที่กำหนดโดยขั้นตอนที่เลือก เนื่องจากอาจต้องใช้ความยาวขั้นตอนที่มากกว่าเพื่อให้เป็นไปตามเงื่อนไขนี้ การใช้งานบางอย่างแก้ไขปัญหานี้โดยการข้ามการอัปเดต BFGS เมื่อมีค่าเป็นลบหรือใกล้เคียงกับศูนย์มากเกินไป แต่โดยทั่วไปแล้วไม่แนะนำวิธีการนี้ เนื่องจากอาจมีการข้ามการอัปเดตบ่อยเกินไปจนทำให้การประมาณค่า Hessian ไม่สามารถจับข้อมูลความโค้งที่สำคัญได้ ตัวแก้ปัญหาบางตัวใช้การอัปเดต BFGS แบบลดทอน (L)BFGS ซึ่งปรับเปลี่ยนปริมาณและเพื่อให้เป็นไปตามเงื่อนไขความโค้ง ${\displaystyle \gamma _{k}}$${\displaystyle y_{k}^{\top }s_{k}>0}$${\displaystyle 1}$${\displaystyle y_{k}^{\top }s_{k}}$${\displaystyle H_{k}}$${\displaystyle s_{k}}$${\displaystyle y_{k}}$

สูตรการเรียกซ้ำแบบสองลูปถูกใช้กันอย่างแพร่หลายโดยตัวเพิ่มประสิทธิภาพแบบไม่มีข้อจำกัดเนื่องจากมีประสิทธิภาพในการคูณด้วยเมทริกซ์เฮสเซียนผกผัน อย่างไรก็ตาม สูตรนี้ไม่อนุญาตให้สร้างเมทริกซ์เฮสเซียนโดยตรงหรือผกผันอย่างชัดเจน และไม่เข้ากันกับข้อจำกัดที่ไม่ใช่แบบกล่อง แนวทางอื่นคือการแสดงแบบกระชับซึ่งเกี่ยวข้องกับการแสดงแบบอันดับต่ำสำหรับเมทริกซ์เฮสเซียนโดยตรงและ/หรือผกผัน^{[ 6 ]}ซึ่งแสดงเมทริกซ์เฮสเซียนเป็นผลรวมของเมทริกซ์แนวทแยงและการอัปเดตอันดับต่ำ การแสดงแบบนี้ทำให้สามารถใช้ L-BFGS ในการตั้งค่าที่มีข้อจำกัดได้ เช่น เป็นส่วนหนึ่งของวิธี SQP

L-BFGS ได้รับการขนานนามว่าเป็น "อัลกอริทึมที่เลือกใช้" สำหรับการปรับโมเดลลอจลิเนียร์ (MaxEnt)และฟิลด์สุ่มแบบมีเงื่อนไขด้วยการปรับค่า -regularization ^{[ 2 ] [ 3 ]}${\displaystyle \ell _{2}}$

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

อั ลกอริทึม L-BFGS-Bขยาย L-BFGS เพื่อจัดการกับข้อจำกัดแบบกล่องอย่างง่าย ( หรือที่เรียกว่าข้อจำกัดขอบเขต) บนตัวแปร กล่าวคือ ข้อจำกัดในรูปแบบl _i ≤ x _i ≤ u _iโดยที่l _iและu _iเป็นขอบเขตล่างและขอบเขตบนคงที่ต่อตัวแปรตามลำดับ (สำหรับแต่ละx _iอาจละเว้นขอบเขตใดขอบเขตหนึ่งหรือทั้งสองขอบเขตก็ได้) ^{[ 7 ] [ 8 ]}วิธีการนี้ทำงานโดยการระบุตัวแปรคงที่และตัวแปรอิสระในแต่ละขั้นตอน (โดยใช้วิธีการไล่ระดับอย่างง่าย) จากนั้นใช้วิธี L-BFGS กับตัวแปรอิสระเท่านั้นเพื่อให้ได้ความแม่นยำที่สูงขึ้น จากนั้นจึงทำซ้ำกระบวนการ

ควอซี-นิวตันหน่วยความจำจำกัดแบบออร์แธนต์ ( OWL-QN ) เป็นรูปแบบ L-BFGS สำหรับการปรับโมเดลแบบมีการควบคุม โดยใช้ประโยชน์จากความเบาบางโดยธรรมชาติของโมเดลดังกล่าว^{[ 3 ]} โดยจะลดฟังก์ชันในรูปแบบ ${\displaystyle \ell _{1}}$

${\displaystyle f({\vec {x}})=g({\vec {x}})+C\|{\vec {x}}\|_{1}}$

โดยที่เป็นฟังก์ชันความสูญเสียแบบนูนที่สามารถหาอนุพันธ์ได้วิธีนี้เป็นวิธีการแบบแอคทีฟเซต: ในแต่ละรอบการทำซ้ำ จะประมาณค่าเครื่องหมายของแต่ละองค์ประกอบของตัวแปร และจำกัดให้ขั้นตอนถัดไปมีเครื่องหมายเดียวกัน เมื่อกำหนดเครื่องหมายแล้วเทอมที่ไม่สามารถหาอนุพันธ์ได้จะกลายเป็นเทอมเชิงเส้นเรียบที่สามารถจัดการได้ด้วย L-BFGS หลังจากขั้นตอน L-BFGS แล้ว วิธีการนี้จะอนุญาตให้ตัวแปรบางตัวเปลี่ยนเครื่องหมายได้ และทำซ้ำกระบวนการ ${\displaystyle g}$${\displaystyle \|{\vec {x}}\|_{1}}$

Schraudolph และคณะนำเสนอ การประมาณค่าแบบ ออนไลน์สำหรับทั้ง BFGS และ L-BFGS ^{[ 9 ]}คล้ายกับการไล่ระดับแบบสุ่มซึ่งสามารถใช้เพื่อลดความซับซ้อนในการคำนวณโดยการประเมินฟังก์ชันข้อผิดพลาดและการไล่ระดับบนชุดย่อยที่สุ่มเลือกจากชุดข้อมูลทั้งหมดในแต่ละรอบการทำซ้ำ พบว่า O-LBFGS มีการลู่เข้าเกือบแน่นอนทั่วโลก^{[ 10 ]}ในขณะที่การประมาณค่าแบบออนไลน์ของ BFGS (O-BFGS) ไม่จำเป็นต้องลู่เข้าเสมอไป^{[ 11 ]}

ตัวอย่างการใช้งานแบบโอเพนซอร์สที่โดดเด่น ได้แก่:

• ALGLIBนำเสนอการใช้งาน L-BFGS ในภาษา C++ และ C# รวมถึงเวอร์ชันแยกต่างหากที่มีข้อจำกัดแบบกล่อง/เชิงเส้น ที่เรียกว่า BLEIC
• รูทีนตัวเพิ่มประสิทธิภาพอเนกประสงค์ ของRoptimใช้เมธอด L-BFGS-B
• โมดูลการเพิ่มประสิทธิภาพของSciPy มีเมธอด minimize ซึ่งรวมถึงตัวเลือกในการใช้ L-BFGS-B ด้วย
• นอกจาก นี้ Julia ยังOptim.jlใช้อัลกอริธึม L-BFGS และ L-BFGS-B อีกด้วย^{[ 12 ]}
• Stanใช้ L-BFGS ร่วมกับการหาอนุพันธ์อัตโนมัติเป็นทางเลือกในการแก้ปัญหาการประมาณค่าความน่าจะเป็นสูงสุดและการประมาณค่าความน่าจะเป็นสูงสุดภายหลัง

ตัวอย่างการใช้งานที่ไม่ใช่โอเพนซอร์สที่น่าสนใจ ได้แก่:

• ตัวแปร L-BFGS-B ยังมีอยู่ในอัลกอริทึม ACM TOMS หมายเลข 778 ^{[ 8 ] [ 13 ]}ในเดือนกุมภาพันธ์ 2011 ผู้เขียนบางส่วนของโค้ด L-BFGS-B ดั้งเดิมได้โพสต์การอัปเดตครั้งใหญ่ (เวอร์ชัน 3.0)
• การใช้งานอ้างอิงในFortran 77 (และมี อินเทอร์เฟซ Fortran 90 ) ^{[ 14 ] [ 15 ]}เวอร์ชันนี้ รวมถึงเวอร์ชันเก่ากว่า ได้ถูกแปลงเป็นภาษาอื่นๆ อีกมากมาย
• การใช้งาน OWL-QN C++ โดยนักออกแบบ^{[ 3 ] [ 16 ]}

• Liu, DC; Nocedal, J. (1989). "เกี่ยวกับวิธีการหน่วยความจำที่จำกัดสำหรับการเพิ่มประสิทธิภาพขนาดใหญ่" . การเขียนโปรแกรมคณิตศาสตร์ B . 45 (3): 503– 528. CiteSeerX  10.1.1.110.6443 . doi : 10.1007/BF01589116 . S2CID  5681609 .
• Haghighi, Aria (2 ธันวาคม 2014). "การหาค่าเหมาะสมที่สุดเชิงตัวเลข: ทำความเข้าใจ L-BFGS" .
• Pytlak, Radoslaw (2009). "อัลกอริทึมควาซี-นิวตันที่มีหน่วยความจำจำกัด" . อัลกอริทึมการไล่ระดับแบบสังยุคในการเพิ่มประสิทธิภาพแบบไม่นูน . Springer. หน้า  159–190 . ISBN 978-3-540-85633-7.