We examine linear program (LP) appr

We examine linear program (LP) approaches to boosting and demonstrate their efficient solution
using LPBoost, a column generation based simplex method. We formulate the problem as if all possible
weak hypotheses had already been generated. The labels produced by the weak hypotheses become
the new feature space of the problem. The boosting task becomes to construct a learning function in
the label space that minimizes misclassification error and maximizes the soft margin. We prove that
for classification, minimizing the 1-norm soft margin error function directly optimizes a generalization
error bound. The equivalent linear program can be efficiently solved using column generation techniques
developed for large-scale optimization problems. The resulting LPBoost algorithm can be used to solve
any LP boosting formulation by iteratively optimizing the dual misclassification costs in a restricted
LP and dynamically generating weak hypotheses to make new LP columns. We provide algorithms for
soft margin classification, confidence-rated, and regression boosting problems. Unlike gradient boosting
algorithms which may converge in the limit only, LPBoost converges in a finite number of iterations to
a global solution satisifying mathematically well-defined optimality conditions. The optimal solutions
of LPBoost are very sparse in contrast with gradient based methods. Computationally, LPBoost is
competitive in quality and computational cost to those of AdaBoost.

ผลลัพธ์ (ไทย) 1:

เราตรวจสอบวิธีโปรแกรมเชิงเส้น (LP) ในการส่งเสริม และสาธิตโซลูชั่นที่มีประสิทธิภาพของพวกเขาใช้ LPBoost สร้างคอลัมน์ตามวิธี simplex เรากำหนดปัญหาเป็นถ้าเป็นไปได้ทั้งหมดมีการสร้างสมมุติฐานที่อ่อนแอแล้ว ป้ายที่ผลิต โดยสมมุติฐานอ่อนแอกลายเป็นพื้นที่คุณลักษณะใหม่ของปัญหา งานเพิ่มกลายเป็นการ สร้างฟังก์ชันการเรียนรู้ในพื้นที่ป้ายที่ช่วยลดข้อผิดพลาด misclassification และวางขอบนุ่ม เราพิสูจน์ที่การจัด ลดขอบนุ่มปกติ 1 ข้อผิดพลาดฟังก์ชันโดยตรงปรับเป็น generalizationข้อผิดพลาดในการผูก โปรแกรมเชิงเส้นเทียบเท่าสามารถมีประสิทธิภาพแก้ไขโดยใช้เทคนิคการสร้างคอลัมน์พัฒนาเพิ่มประสิทธิภาพขนาดใหญ่ปัญหา อัลกอริทึม LPBoost ผลใช้แก้ห้างหุ้นส่วนจำกัดใด ๆ ส่งเสริมกำหนด โดยซ้ำ ๆ เพิ่มประสิทธิภาพต้นทุนสอง misclassification ในที่จำกัดห้างหุ้นส่วนจำกัดและสร้างสมมุติฐานอ่อนไหวทำให้ห้างหุ้นส่วนจำกัดคอลัมน์ใหม่ เรามีอัลกอริทึมสำหรับขอบนุ่มประเภท ความเชื่อมั่นคะแนน และเพิ่มปัญหาการถดถอย ซึ่งแตกต่างจากการส่งเสริมการไล่ระดับสีอัลกอริทึมซึ่งอาจมาบรรจบกันในจำกัดเฉพาะ LPBoost converges ในจำนวนการวนซ้ำจะจำกัดการแก้ปัญหาสากล satisifying optimality mathematically โดยสภาพ โซลูชั่นเหมาะสมของ LPBoost มีมากบ่อ in contrast with วิธีไล่ระดับตาม Computationally, LPBoost เป็นแข่งขันในคุณภาพและต้นทุนที่คำนวณกับ AdaBoost

ผลลัพธ์ (ไทย) 2:

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

ผลลัพธ์ (ไทย) 3:

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

satisifying ทางคณิตศาสตร์ต่อเงื่อนไขความเหมาะที่สุด . โซลูชั่นที่เหมาะสม
ของ lpboost จะเบาบางมาก เมื่อเทียบกับการใช้วิธี computationally lpboost คือ , แข่งขันในการคำนวณต้นทุนคุณภาพ
และที่ adaboost .