อัลกอริทึม Winnow ^{[ 1 ]}เป็นเทคนิคจากการเรียนรู้ของเครื่องสำหรับการเรียนรู้ตัวจำแนกเชิงเส้นจากตัวอย่างที่มีป้ายกำกับ มันคล้ายกับ อัลก อริทึมเพอร์เซปตรอน มาก อย่างไรก็ตาม อัลกอริทึมเพอร์เซปตรอนใช้รูปแบบการอัปเดตน้ำหนักแบบบวก ในขณะที่ Winnow ใช้รูปแบบการคูณซึ่งทำให้ทำงานได้ดีขึ้นมากเมื่อมิติหลายมิติไม่เกี่ยวข้อง (จึงเป็นที่มาของชื่อWinnow ) มันเป็นอัลกอริทึมที่เรียบง่ายและปรับขนาดได้ดีกับข้อมูลที่มีมิติสูง ในระหว่างการฝึกอบรม Winnow จะได้รับลำดับของตัวอย่างบวกและลบ จากนั้นจะเรียนรู้ระนาบ การตัดสินใจ ซึ่งสามารถนำไปใช้ในการติดป้ายกำกับตัวอย่างใหม่ว่าเป็นบวกหรือลบได้ อัลกอริทึมนี้ยังสามารถใช้ใน การตั้งค่า การเรียนรู้แบบออนไลน์ซึ่งขั้นตอนการเรียนรู้และการจำแนกประเภทไม่ได้แยกออกจากกันอย่างชัดเจน

อัลกอริทึมพื้นฐาน Winnow1 มีดังนี้ พื้นที่ของอินสแตนซ์คือนั่นคือ แต่ละอินสแตนซ์ถูกอธิบายด้วยชุดของคุณลักษณะที่มีค่าเป็นบูลีนอัลกอริทึมจะรักษาน้ำหนักที่ไม่เป็นลบสำหรับซึ่งเริ่มต้นที่ 1 โดยมีน้ำหนักหนึ่งค่าสำหรับแต่ละคุณลักษณะ เมื่อตัวเรียนรู้ได้รับตัวอย่างมันจะใช้กฎการทำนายทั่วไปสำหรับตัวจำแนกเชิงเส้น: ${\displaystyle X=\{0,1\}^{n}}$${\displaystyle w_{i}}$${\displaystyle i\in \{1,\ldots ,n\}}$${\displaystyle (x_{1},\ldots ,x_{n})}$

• ถ้า เช่นนั้นให้ทำนาย 1${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}>\Theta }$
• มิฉะนั้นให้ทำนายเป็น 0

นี่คือจำนวนจริงที่เรียกว่าค่าเกณฑ์เมื่อรวมกับค่าน้ำหนักแล้ว ค่าเกณฑ์จะกำหนดระนาบแบ่งในพื้นที่อินสแตนซ์ จะได้ขอบเขตที่ดีหาก(ดูด้านล่าง) ${\displaystyle \Theta }$${\displaystyle \Theta =n/2}$

สำหรับแต่ละตัวอย่างที่นำเสนอ ผู้เรียนจะใช้กฎการปรับปรุงต่อไปนี้:

• หากตัวอย่างนั้นได้รับการจำแนกประเภทอย่างถูกต้องแล้ว ไม่ต้องทำอะไรเพิ่มเติม
• หากตัวอย่างถูกทำนายผิดพลาดและผลลัพธ์ที่ถูกต้องคือ 0 สำหรับแต่ละคุณลักษณะน้ำหนักที่เกี่ยวข้องจะถูกตั้งค่าเป็น 0 (ขั้นตอนการลดระดับ) ${\displaystyle x_{i}=1}$${\displaystyle w_{i}}$

  ${\displaystyle \forall x_{i}=1,w_{i}=0}$

• หากตัวอย่างถูกทำนายผิดพลาดและผลลัพธ์ที่ถูกต้องคือ 1 สำหรับแต่ละคุณลักษณะน้ำหนักที่สอดคล้องกันจะถูกคูณด้วยα (ขั้นตอนการส่งเสริม) ${\displaystyle x_{i}=1}$${\displaystyle w_{i}}$

  ${\displaystyle \forall x_{i}=1,w_{i}=\alpha w_{i}}$

ค่าทั่วไปของαคือ 2

มีรูปแบบต่างๆ มากมายสำหรับแนวทางพื้นฐานนี้ Winnow2 ^{[ 1 ]}คล้ายกัน ยกเว้นว่าในขั้นตอนการลดระดับ น้ำหนักจะถูกหารด้วยαแทนที่จะตั้งค่าเป็น 0 Balanced Winnowรักษาน้ำหนักไว้สองชุด และด้วยเหตุนี้จึงมีระนาบไฮเปอร์สองระนาบ จากนั้นสามารถขยายความทั่วไปสำหรับการจำแนกประเภทหลายป้ายกำกับได้

ในบางสถานการณ์ สามารถแสดงให้เห็นได้ว่าจำนวนข้อผิดพลาดที่ Winnow ทำในขณะที่เรียนรู้นั้นมีขอบเขตบนที่ไม่ขึ้นอยู่กับจำนวนอินสแตนซ์ที่นำเสนอ หากอัลกอริทึม Winnow1 ใช้และกับฟังก์ชันเป้าหมายที่เป็นการแยกแบบโมโนโทนของตัวอักษรที่กำหนดโดยแล้วสำหรับลำดับอินสแตนซ์ใดๆ จำนวนข้อผิดพลาดทั้งหมดจะถูกจำกัดโดย : ^{[ 2 ]}${\displaystyle \alpha >1}$${\displaystyle \ทีต้า \geq 1/\อัลฟา }$${\displaystyle k}$${\displaystyle f(x_{1},\ldots ,x_{n})=x_{i_{1}}\lor \cdots \lor x_{i_{k}}}$${\displaystyle \alpha k(\log _{\alpha }\Theta +1)+{\frac {n}{\Theta }}}$