Perceptron จากศูนย์: นิวรอนคำนวณอะไร

perceptron รับค่าที่วัดมา คูณแต่ละค่าด้วยตัวเลขที่มันควบคุมเอง บวกทั้งหมดเข้าด้วยกัน บวกตัวเลขอีกหนึ่งค่า แล้วดูเครื่องหมาย

เขียนค่าที่วัดจากชิ้นส่วนหนึ่งเป็นเวกเตอร์ $\mathbf{x} = (x_1, x_2)$ — ความกว้างและน้ำหนัก perceptron ถือเวกเตอร์น้ำหนัก $\mathbf{w} = (w_1, w_2)$ และ bias $b$ คะแนนของมันคือ

และคำตอบของมันคือเครื่องหมายของคะแนนนั้น: ยอมรับถ้า $s(\mathbf{x}) \geq 0$ ไม่เช่นนั้นปฏิเสธ

นี่คือโมเดลทั้งหมด ทุกอย่างที่ perceptron จะรู้เกี่ยวกับโรงงานได้ตลอดไปอยู่ในตัวเลขสามค่า

เราควรหยุดดูเรขาคณิตของมันสักครู่ เพราะนี่คือภาพที่จะยังใช้ได้ตลอดอีกยี่สิบเก้าบท แม้เมื่อสมการเริ่มยาวเกินหนึ่งบรรทัด ชุดของจุดที่ $s(\mathbf{x}) = 0$ — จุดที่ perceptron ยังตัดสินไม่ได้พอดี — คือเส้นตรงในระนาบ ด้านหนึ่งคะแนนเป็นบวกและทุกอย่างถูกยอมรับ อีกด้านหนึ่งคะแนนเป็นลบและทุกอย่างถูกปฏิเสธ สำหรับ perceptron แล้ว การเรียนรู้หมายถึง การเลื่อนเส้นนั้น

ข้อเท็จจริงสองข้อเกี่ยวกับเส้นนั้นตามมาจากพีชคณิตโดยตรง และทั้งสองข้อสำคัญในภายหลัง:

• $\mathbf{w}$ ตั้งฉากกับเส้นนั้น เวกเตอร์น้ำหนักไม่ได้วางไปตาม boundary แต่มันชี้ข้าม boundary ไปยังด้านที่ถูกยอมรับ
• $b$ เลื่อนเส้นได้โดยไม่หมุนมัน ถ้าไม่มี bias เส้นจะถูกบังคับให้ผ่านจุดกำเนิด ซึ่งสำหรับโรงงานที่วัดมิลลิเมตรกับกรัมแล้วเป็นข้อจำกัดที่ไร้เหตุผล — มันจะหมายความว่าชิ้นส่วนที่กว้างศูนย์และหนักศูนย์อยู่บนรั้วพอดี

perceptron เริ่มต้นโดยไม่รู้อะไรเลย: $\mathbf{w} = (0, 0)$ และ $b = 0$ ทุกคะแนนเป็นศูนย์ ดังนั้นมันยอมรับทุกอย่าง

ตอนนี้ให้มันดูตัวอย่างทีละตัว ติด label ชิ้นส่วนที่ถูกยอมรับเป็น $y = +1$ และชิ้นส่วนที่ถูกปฏิเสธเป็น $y = -1$ สำหรับแต่ละตัวอย่าง ให้ถามคำถามเดียว: เครื่องหมายออกมาถูกไหม? วิธีเขียนคำถามนี้แบบกระชับคือเช็กว่า $y \cdot s(\mathbf{x})$ เป็นบวกหรือไม่ — ถ้า label กับคะแนนมีเครื่องหมายตรงกัน ผลคูณของมันเป็นบวก และถ้าไม่ตรงกันก็เป็นลบ

ถ้าคำตอบคือใช่ ไม่ต้องเปลี่ยนอะไร ถ้าคำตอบคือไม่ ให้ขยับนิดหนึ่ง:

นี่คือ algorithm ทั้งหมด และคุ้มค่าที่จะเข้าใจว่า ทำไม นี่คือการขยับที่ถูกต้อง แทนที่จะท่องจำมัน สมมติว่าชิ้นส่วนหนึ่งควรถูกยอมรับ ($y = +1$) แต่คะแนนออกมาเป็นลบ การเพิ่ม $\mathbf{x}$ เข้าไปใน $\mathbf{w}$ เปลี่ยนคะแนนของชิ้นส่วนนั้นเองเป็น

ซึ่งเป็นจำนวนบวก คะแนนของชิ้นส่วนที่มันเพิ่งตอบผิด สูงขึ้น ซึ่งเป็นทิศทางที่มันควรไป กฎนี้ไม่ใช่ heuristic ที่ใครสักคนเดาเอาเอง; มันคือการเปลี่ยนแปลงที่เล็กที่สุดซึ่งพิสูจน์ได้ว่าปรับปรุงกรณีตรงหน้า แน่นอนว่ามันอาจทำให้กรณีอื่นเสียได้ นั่นคือเหตุผลที่คุณต้องวนอีกรอบ

สังเกตสิ่งที่ไม่มีอยู่ ไม่มี derivative ที่ไหนเลย นี่ไม่ใช่การมองข้าม และเป็นแนวคิดสำคัญจริง ๆ ข้อแรกของคอร์สนี้

สิ่งที่คุณอยาก differentiate คือ error — จำนวนชิ้นส่วนที่ถูกจัดประเภทผิด แต่จำนวนนั้นเป็นขั้นบันได: มันราบอยู่ที่ 4 ขณะที่คุณขยับเส้น แล้วลดลงเป็น 3 ทันทีเมื่อเส้นข้ามจุดหนึ่ง derivative ของมันเป็นศูนย์แทบทุกที่ และไม่ถูกนิยามตรงขั้นบันได Calculus ไม่มีอะไรให้จับ กฎ perceptron ทำงาน อ้อม สิ่งนั้นโดยไม่ถามหา slope เลย: มันถามแค่ว่า “ถูกหรือผิด?” แล้วเคลื่อนที่ในทิศทางที่มันให้เหตุผลทางเรขาคณิตได้

นี่เป็นคำตอบจริง ๆ และก็เป็นทางตันด้วย ใน บทที่ 2 เราจะต้องการ loss ที่มีที่มามากกว่าถูกเลือกขึ้นมาเฉย ๆ ใน บทที่ 4 ต้องการโมเดลที่รายงานว่า มั่นใจแค่ไหน และใน บทที่ 5 ต้องการสิ่งที่มีมากกว่าหนึ่ง layer — และไม่มีสิ่งใดไปถึงได้จากกฎที่รู้แค่ “ผิด” การได้ slope ที่ใช้งานได้กลับมาคือสิ่งที่บังคับให้เกิดสองบทถัดไป แต่ perceptron ได้ทำสิ่งที่ผู้สืบทอดของมันทำไม่ได้เลย: เรียนรู้โดยไม่ต้องใช้ calculus แม้แต่น้อย

Python ล้วน ๆ ไม่มี NumPy มีแค่ list กับ loop NumPy จะมาในบทหน้า เมื่อคณิตศาสตร์เริ่มไม่พอดีกับ loop ที่คุณอยากอ่าน; การนำมันเข้ามาตอนนี้จะซ่อน arithmetic ไว้หลัง library ในจังหวะที่คุณอยากเห็นมันพอดี

def score(w, b, x):
    return w[0] * x[0] + w[1] * x[1] + b


def predict(w, b, x):
    return 1 if score(w, b, x) >= 0 else -1


def train(data, epochs=200):
    """Returns (w, b, epoch_it_converged) — or None for the epoch if it never did."""
    w, b = [0.0, 0.0], 0.0
    for epoch in range(epochs):
        mistakes = 0
        for x, y in data:
            if y * score(w, b, x) <= 0:          
                w[0] += y * x[0]                 
                w[1] += y * x[1]                 
                b += y                           
                mistakes += 1
        if mistakes == 0:
            return w, b, epoch + 1
    return w, b, None

สี่บรรทัดที่ไฮไลต์คือ algorithm นอกนั้นทั้งหมดเป็นงาน bookkeeping

และนี่คือสายพาน พร้อมชิ้นส่วนแปดชิ้นที่วัดจากมัน — สี่ชิ้นที่ส่งออก และสี่ชิ้นที่ถูกตีกลับ:

BELT = [
    ((18.0, 47.0), +1), ((19.5, 52.0), +1), ((20.2, 49.0), +1), ((21.0, 55.0), +1),
    ((24.0, 61.0), -1), ((25.5, 66.0), -1), ((23.0, 70.0), -1), ((26.0, 58.0), -1),
]

w, b, epoch = train(BELT, epochs=200)
print(epoch, w, b)

ชิ้นส่วนทั้งแปดนี้ แยกได้ ด้วยเส้นตรง — ทุกชิ้นที่ยอมรับกว้างต่ำกว่า 22 มม. และทุกชิ้นที่ปฏิเสธกว้าง 23 มม. ขึ้นไป รั้วแนวตั้งที่ 22 มิลลิเมตรก็ทำงานได้ ดังนั้น perceptron ควรหาเจอ

รันมัน:

None [-142.1, -13.0] 54.0

สองร้อย epoch, การแก้ไข 454 ครั้ง และมันยังไม่ converged น้ำหนักมีค่ามากและเครื่องหมายผิด มีบางอย่างผิด — ยกเว้นว่าไม่มีอะไรผิดเลย และเหตุผลนั้นคือสิ่งที่มีประโยชน์ที่สุดในบทนี้

perceptron มีการรับประกัน ซึ่งพิสูจน์โดย Novikoff ในปี 1962¹ ถ้าข้อมูลสามารถถูกแยกด้วยเส้นได้เลย algorithm จะทำการแก้ไขไม่เกิน

ครั้งก่อนที่มันจะหยุดแก้ — โดย $R$ คือ radius ของข้อมูล ความยาวของเวกเตอร์ตัวอย่างที่ยาวที่สุด และ $\gamma$ คือ margin: ระยะจาก hyperplane ที่ใช้แยกไปยังจุดที่ใกล้ที่สุด ใน augmented space ที่ bias เป็นพิกัดที่สาม นั่นคือเหตุผลที่การทำ centering ข้อมูลเปลี่ยนมันได้ แม้ระยะในหน่วยมิลลิเมตรจะไม่เปลี่ยน

การรับประกันนี้ไม่มีเงื่อนไข และไม่ได้พูดถึง epoch, learning rate หรือโชค มันก็ไม่ได้พูดถึง เวลา เช่นกัน และการละเว้นตรงนั้นคือประเด็น

ใส่ตัวเลขของเราเข้าไป วัดโดยตรงจากชิ้นส่วนทั้งแปด โดยพับ bias เข้าไปเป็น feature คงที่:

ทฤษฎีไม่เคยถูกละเมิด รันเวอร์ชันดิบให้นานพอแล้วมันก็ converge จริง — ที่ epoch 11,976 หลังการแก้ไข 29,870 ครั้ง — อยู่ใน bound 2,633,550 อย่างสบาย และช่องว่างนั้นเองคือประเด็น: ทฤษฎีให้ bound ของกรณีเลวร้ายที่สุด ไม่ใช่กรณีทั่วไป มันแค่ต้องใช้ epoch มากกว่าที่ใครจะนั่งรอถึงหกสิบเท่า

แถวที่สองคือชิ้นส่วนแปดชิ้นเดิม โค้ดยี่สิบบรรทัดเดิม โดยเพิ่มสามบรรทัดเพื่อลบค่าเฉลี่ยความกว้างและค่าเฉลี่ยน้ำหนักออกจากทุกการวัด แค่นั้น นั่นคือการเปลี่ยนแปลงทั้งหมด มันย้ายกลุ่มจุดให้คร่อมจุดกำเนิด แทนที่จะลอยอยู่ที่ (22, 57) และผลต่อ bound คือ หนึ่งหมื่นห้าพันเท่า เพราะทั้งสองพจน์ดีขึ้นพร้อมกัน: $R$ ลดจาก 74 เป็น 13 เพราะจุดต่าง ๆ ไม่ได้ถูกวัดจากจุดกำเนิดที่ไกลออกไปอีกแล้ว และ $\gamma$ เพิ่มจาก 0.045 เป็น 0.989 เพราะ margin ถูกวัดเทียบกับเวกเตอร์น้ำหนักที่ไม่ต้องแบก bias ขนาดใหญ่เพื่อเอื้อมถึงข้อมูลอีกต่อไป

mean_w = sum(x[0] for x, _ in BELT) / len(BELT)   # 22.15
mean_g = sum(x[1] for x, _ in BELT) / len(BELT)   # 57.25
CENTRED = [(((x[0] - mean_w), (x[1] - mean_g)), y) for x, y in BELT]

w, b, epoch = train(CENTRED, epochs=200)
print(epoch, w, b)

2 [-4.15, -10.25] 1.0

Converged ในสอง epoch หลังจากแก้ตัวเองไปพอดี หนึ่งครั้ง

บทเรียนจริง ๆ ตรงนี้ไม่ใช่ “อย่าลืม normalise input” แม้คุณควรทำก็ตาม แต่มันคือ การรับประกันว่า algorithm จะจบหรือไม่ ไม่ได้บอกอะไรเลยว่าคุณจะยังอยู่ตอนที่มันจบไหม และช่องว่างระหว่างสองสิ่งนี้มักเป็นเรื่องของเรขาคณิต นี่คือครั้งแรกของ pattern ที่คุณจะเจออีกใน บทที่ 6 กับ initialisation, ใน บทที่ 10 กับ learning-rate schedules และใน บทที่ 13 กับ quantisation: คณิตศาสตร์บอกว่าสิ่งนั้นเป็นไปได้ ส่วนวิศวกรรมตัดสินว่ามันทำได้จริงไหม คอร์สที่สอนคุณแค่ทฤษฎีจะส่งโมเดลที่ train สามวันมาให้ แล้วโทษคุณ

ตอนนี้คือความล้มเหลวที่จบยุคแรกของ neural networks และมันใส่ได้ในสี่แถว

ลืมโรงงานไปก่อน ใช้ input สองตัวที่แต่ละตัวเป็นได้แค่ 0 หรือ 1 และขอให้คำตอบเป็น $+1$ เมื่อมีเพียงตัวใดตัวหนึ่งเท่านั้นที่เป็น 1:

นี่คือ XOR — exclusive or ก่อนอ่านต่อ ลองวาดจุดทั้งสี่บนกระดาษ: มุมสามมุมของสี่เหลี่ยมจัตุรัสหนึ่งหน่วย และมุมที่สี่ ทำเครื่องหมายมุมทแยง $(0,1)$ และ $(1,0)$ เป็นยอมรับ และ $(0,0)$ กับ $(1,1)$ เป็นปฏิเสธ ตอนนี้ลองวาด เส้นตรงหนึ่งเส้น ให้จุดที่ยอมรับสองจุดอยู่ด้านหนึ่ง และจุดที่ปฏิเสธสองจุดอยู่อีกด้านหนึ่ง

คุณทำไม่ได้ ไม่ใช่ว่ามันยาก หรือคุณต้องการ algorithm ที่ฉลาดกว่านี้; แต่เพราะเส้นนั้นไม่มีอยู่ พีชคณิตสามบรรทัดแสดงให้เห็นว่าทำไม ถ้า perceptron ทำทั้งสี่แถวถูก เมื่ออ่านสี่แถวตามลำดับจะได้

บวกอสมการกลางสองอัน: $w_1 + w_2 + 2b \geq 0$ ดังนั้น $w_1 + w_2 \geq -2b$ อันสุดท้ายบอกว่า $w_1 + w_2 < -b$ รวมกันได้: $-2b \leq w_1 + w_2 < -b$ ซึ่งต้องการ $-2b < -b$ ซึ่งต้องการ $b > 0$ และอสมการแรกบอกว่า $b < 0$ ไม่มี $b$ แบบนั้น ดังนั้นจึงไม่มีน้ำหนักแบบนั้น ไม่มี perceptron ตัวใด ไม่ว่าตัวเลขใด ๆ ก็ตาม ที่ classify XOR ได้

รันมันอยู่ดี เพราะการดู algorithm ล้มเหลวมีค่ามากกว่าการถูกบอกว่ามันจะล้มเหลว:

     100 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4
   1,000 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4
 100,000 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4

มันไม่ diverge และมันไม่ได้แกว่งไปมาใกล้คำตอบที่พอใช้ได้ มัน วนรอบ: มันเดินเป็น loop สั้น ๆ ผ่าน weight space แล้วกลับมาที่จุดเริ่มต้นเดิมเป๊ะ ตลอดไป ทำถูกสองจากสี่ — ซึ่งก็คือสิ่งที่คุณจะได้จากการเดา epoch หนึ่งแสนกับหนึ่งร้อยแยกกันไม่ออก เพราะ algorithm ไม่ได้กำลังก้าวหน้าชนิดที่การรันนานขึ้นจะทำให้เสร็จได้ เทียบกับสายพานซึ่งดูติดอยู่ที่ 200 epoch แต่จริง ๆ กำลังบดไปหาคำตอบจริง จากภายนอก สองกรณีนี้ดูคล้ายกันในไม่กี่วินาทีแรก การแยกมันออกจากกันโดยไม่มีทฤษฎีเป็นไปไม่ได้ — และนั่นคืออีกเหตุผลหนึ่งที่ควรรู้ทฤษฎี

ในปี 1969 Marvin Minsky และ Seymour Papert ตีพิมพ์ Perceptrons งานศึกษาทางคณิตศาสตร์ขนาดหนังสือเกี่ยวกับสิ่งที่โมเดลนี้แทนค่าได้และแทนค่าไม่ได้อย่างแม่นยำ² XOR คือผลลัพธ์ที่ถูกอ้างบ่อยที่สุด และคำอ้างนั้นมักถูกใช้เป็นข้อกล่าวหา: ว่าหนังสือเล่มนี้ฆ่างานวิจัย neural network ไปสิบห้าปีเพราะการแข่งขันหรือความอาฆาต

คณิตศาสตร์ในหนังสือถูกต้อง และน่าสนใจกว่าตัวอย่าง XOR มาก Minsky และ Papert ไม่ได้สนใจหลัก ๆ ว่า perceptron เดี่ยวทำ XOR ได้ไหม; พวกเขาสนใจว่าจะเกิดอะไรขึ้นเมื่อ perceptron มี limited receptive fields — แต่ละ unit เห็น input เพียงบางส่วน — และพวกเขาพิสูจน์ว่า property ระดับ global บางอย่างของภาพ เช่น รูปหนึ่งเชื่อมต่อกันหรือไม่ ไม่สามารถคำนวณด้วยวิธีนั้นได้ ไม่ว่าคุณจะใช้ unit กี่ตัวก็ตาม นั่นคือผลลัพธ์ที่ลึกจริง ๆ เกี่ยวกับ locality และไม่มีอะไรเกี่ยวกับเรื่องเล่ายอดนิยม

เรื่องเล่ายอดนิยมยังผิดในทางประวัติศาสตร์ด้วย Minsky และ Papert พูดถึง multi-layer perceptrons อย่างชัดเจน และบอกว่าคำถามเรื่องพลังของมันยังเปิดอยู่ — พวกเขาสงสัยว่าการขยายทฤษฎีจะ “ไร้ผล” ซึ่งเป็นการคาดการณ์ ไม่ใช่การพิสูจน์ และมันผิด สิ่งที่ขาดไปในปี 1969 ไม่ใช่ไอเดียของการซ้อน layer; แต่เป็นวิธี train stack หนึ่ง กฎ perceptron ทำไม่ได้: มันต้องรู้ว่าแต่ละ unit ผิดแค่ไหน และสำหรับ unit ที่ถูกฝังอยู่ตรงกลาง ไม่มี label ให้เทียบ ช่องว่างนั้นเปิดค้างอยู่จนกระทั่ง backpropagation ถูกทำให้แพร่หลายในปี 1986³ และการปิดช่องว่างนี้คือสิ่งที่บทที่ 5 ทำ

ดังนั้นสรุปอย่างซื่อสัตย์คือแบบนี้ หนังสือพิสูจน์ข้อจำกัดจริงของโมเดลจริง การล่มสลายของเงินทุนในสาขานี้ช่วงทศวรรษ 1970 มีหลายสาเหตุ หนึ่งในนั้นคือคำสัญญาที่ให้ไว้กับ perceptron ช่วงต้นทศวรรษ 1960 นั้นเกินจริง และอุปสรรคทางเทคนิคแก้ได้ แต่ยังไม่มีใครมีเครื่องมือนั้น

perceptron มีอายุหกสิบแปดปี และคุณเพิ่งเขียนมันขึ้นมาตัวหนึ่ง คุ้มค่าที่จะพูดให้แม่นว่าส่วนไหนของมันยังอยู่ในเครื่องที่คุณจะสร้างเสร็จเมื่อจบคอร์สนี้ เพราะคำตอบคือ: มากกว่าที่คุณเดา

perceptron ติดอยู่กับสองสิ่งพร้อมกัน และสุดท้ายมันกลายเป็นสิ่งเดียวกัน

มันแทน XOR ไม่ได้ เพราะเส้นหนึ่งเส้นไม่พอ การแก้สิ่งนั้นหมายถึงการซ้อน layer — layer แรกที่ดัด space, layer ที่สองที่วาดเส้นใน space ที่ถูกดัดแล้ว นั่นคือบทที่ 5

แต่คุณ train stack ด้วยกฎ perceptron ไม่ได้ เพราะมันรู้แค่ “ผิด” และ unit ที่อยู่กลาง network ไม่มี label ของตัวเองให้ผิดเกี่ยวกับมัน การ train stack ต้องรู้ว่า ผิดอย่างไร และผิดในทิศทางไหน สำหรับทุกน้ำหนัก — คุณต้องการ slope และ error function ของ perceptron ซึ่งเป็นขั้นบันได ไม่มีสิ่งนั้น

ดังนั้นก่อน stack ต้องมี loss function ที่มี derivative ใช้งานได้ และไม่ใช่สิ่งที่เลือกมาเพราะ differentiate สะดวกด้วย: แต่เป็นสิ่งที่มีที่มา บอกความจริงบางอย่างเกี่ยวกับข้อมูล และ gradient ของมันไหลออกมาจากความหมายนั้น แทนที่จะถูก reverse-engineered ให้ดูเรียบร้อย

นั่นคือบทที่ 2 และมันเริ่มจากการถามคำถามที่ perceptron ไม่เคยต้องตอบ: ไม่ใช่ “ชิ้นส่วนนี้ดีไหม?” แต่เป็น “ค่าที่อ่านเหล่านี้ น่าจะเป็นไปได้แค่ไหน ถ้านี่คือความจริง?”

สิ่งที่ควรอ่านควบคู่กับบทนี้ด้วย: บทความดั้งเดิมของ Rosenblatt, The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Psychological Review 65(6), 1958) ซึ่งอ่านง่ายกว่าชื่อเสียงของมันชวนให้คิด; McCulloch and Pitts, A Logical Calculus of the Ideas Immanent in Nervous Activity (Bulletin of Mathematical Biophysics 5, 1943) บทความที่ model นิวรอนเป็น threshold เหนือผลรวมถ่วงน้ำหนักเป็นครั้งแรก; ส่วน perceptron ใน A Course in Machine Learning ของ Hal Daumé III ซึ่ง derive update เดียวกันด้วยน้ำหนักเน้นที่ต่างออกไป; และบทที่ 2 กับ 3 ของ Mathematics for Machine Learning โดย Deisenroth, Faisal และ Ong สำหรับ linear algebra หากกล่องด้านบนทำให้คุณอยากได้มากกว่าที่มันให้ไว้