สนามสุ่มแบบมีเงื่อนไข

ฟิลด์สุ่มแบบมีเงื่อนไข ( CRF ) เป็น วิธีการสร้างแบบจำลองทางสถิติประเภทหนึ่งที่มักใช้ในการรู้จำรูปแบบและการเรียนรู้ของเครื่องและใช้สำหรับการทำนายแบบมีโครงสร้างในขณะที่ตัวจำแนกประเภททำนายป้ายกำกับสำหรับตัวอย่างเดียวโดยไม่พิจารณาตัวอย่าง "ข้างเคียง" แต่ CRF สามารถคำนึงถึงบริบทได้ ในการทำเช่นนั้น การทำนายจะถูกสร้างแบบจำลองเป็นแบบจำลองกราฟิกซึ่งแสดงถึงความสัมพันธ์ระหว่างการทำนาย ชนิดของกราฟที่ใช้ขึ้นอยู่กับการใช้งาน ตัวอย่างเช่น ในการประมวลผลภาษาธรรมชาติ CRF แบบ "ลูกโซ่เชิงเส้น" เป็นที่นิยม ซึ่งการทำนายแต่ละครั้งจะขึ้นอยู่กับเพื่อนบ้านที่อยู่ติดกันเท่านั้น ในการประมวลผลภาพ กราฟมักจะเชื่อมต่อตำแหน่งต่างๆ กับตำแหน่งใกล้เคียงและ/หรือตำแหน่งที่คล้ายคลึงกัน เพื่อให้แน่ใจว่าได้รับการทำนายที่คล้ายคลึงกัน

ตัวอย่างอื่นๆ ที่ใช้ CRF ได้แก่การติดฉลากหรือการแยกวิเคราะห์ข้อมูลลำดับสำหรับ การ ^{ประมวล}ผลภาษาธรรมชาติหรือลำดับทางชีววิทยา [ ^{1 ]}การติดแท็กส่วนของคำพูดการ แยก วิเคราะห์ แบบ ตื้น^{[ 2 ]}การระบุเอนทิตีที่มีชื่อ^{[ 3 ]} การค้นหายีนการค้นหาบริเวณการทำงานที่สำคัญของเปปไทด์^{[ 4 ]}และการจดจำวัตถุ^{[ 5 ]}และการแบ่งส่วนภาพในคอมพิวเตอร์วิชั่น^{[ 6 ]}

CRFs เป็นแบบจำลองกราฟิกเชิงความน่า จะเป็นแบบ ไม่กำหนดทิศทางและจำแนก ประเภท หนึ่ง

Lafferty , McCallumและ Pereira ^{[ 1 ]}กำหนด CRF บนการสังเกตและตัวแปรสุ่มดังต่อไปนี้: ${\displaystyle {\boldสัญลักษณ์ {X}}}$${\displaystyle {\boldสัญลักษณ์ {Y}}}$

ให้G เป็นกราฟ โดยที่ดังนั้น จึงถูกกำหนดดัชนีโดยจุดยอดของG ${\displaystyle G=(V,E)}$${\displaystyle {\boldสัญลักษณ์ {Y}}=({\boldสัญลักษณ์ {Y}__{v})_{v\in V}}$${\displaystyle {\boldสัญลักษณ์ {Y}}}$${\displaystyle G}$

ดังนั้นจึงเป็นสนามสุ่มแบบมีเงื่อนไข เมื่อตัวแปรสุ่มแต่ละตัวซึ่งมีเงื่อนไขอยู่บนจะเป็นไปตามคุณสมบัติของมาร์คอฟเมื่อเทียบกับกราฟ กล่าวคือ ความน่าจะเป็นของมันขึ้นอยู่กับเพื่อนบ้านใน G เท่านั้น และไม่ขึ้นอยู่กับสถานะในอดีตของมัน ${\displaystyle ({\boldsymbol {X}},{\boldsymbol {Y}})}$${\displaystyle {\boldสัญลักษณ์ {Y}__{v}}$${\displaystyle {\boldสัญลักษณ์ {X}}}$

${\displaystyle P({\boldสัญลักษณ์ {Y}__{v}|{\boldสัญลักษณ์ {X}},\{{\boldสัญลักษณ์ {Y}}`$โดยที่หมายความ ว่าและเป็นเพื่อนบ้านกันใน${\displaystyle {\มาทิต {w}}\sim v}$${\displaystyle w}$${\displaystyle v}$${\displaystyle G}$

สิ่งนี้หมายความว่า CRF เป็นแบบจำลองกราฟิกแบบไม่มีทิศทางซึ่งโหนดสามารถแบ่งออกเป็นสองเซตที่ไม่ซ้ำกันอย่างแม่นยำคือ และซึ่งเป็นตัวแปรที่สังเกตได้และตัวแปรผลลัพธ์ตามลำดับจากนั้นจึงสร้างแบบจำลอง การแจกแจงแบบมีเงื่อนไข${\displaystyle {\boldสัญลักษณ์ {X}}}$${\displaystyle {\boldสัญลักษณ์ {Y}}}$${\displaystyle p({\boldsymbol {Y}}|{\boldsymbol {X}})}$

สำหรับกราฟทั่วไป ปัญหาของการอนุมานที่แม่นยำใน CRF นั้นไม่สามารถแก้ไขได้ ปัญหาการอนุมานสำหรับ CRF นั้นโดยพื้นฐานแล้วเหมือนกับสำหรับMRFและข้อโต้แย้งเดียวกันก็ใช้ได้^{[ 7 ]} อย่างไรก็ตาม มีกรณีพิเศษบางกรณีที่การอนุมานที่แม่นยำเป็นไปได้:

• หากกราฟเป็นแบบลูกโซ่หรือแบบต้นไม้ อัลกอริทึมการส่งข้อความจะให้คำตอบที่แม่นยำ อัลกอริทึมที่ใช้ในกรณีเหล่านี้จะคล้ายคลึงกับอัลกอริทึมแบบส่งต่อ-ย้อนกลับและอัลกอริทึม Viterbiสำหรับกรณีของ HMMs
• หาก CRF มีเพียงศักยภาพแบบคู่ และพลังงานเป็นแบบซับโมดูลาร์ อัลก อริทึมการตัดขั้นต่ำ/การไหลสูงสุดเชิงคอมบินาทอรีจะให้คำตอบที่แม่นยำ

หากไม่สามารถอนุมานได้อย่างแม่นยำ สามารถใช้อัลกอริธึมหลายวิธีเพื่อหาคำตอบโดยประมาณ ซึ่งได้แก่:

• การเผยแพร่ความเชื่อที่ผิดเพี้ยน
• ส่วนขยายอัลฟ่า
• การอนุมานสนามเฉลี่ย
• การผ่อนคลายการเขียนโปรแกรมเชิงเส้น

การเรียนรู้พารามิเตอร์มักจะทำโดย การเรียนรู้ความ น่าจะเป็นสูงสุดสำหรับถ้าโหนดทั้งหมดมีการกระจายแบบตระกูลเอกซ์โพเนนเชียลและโหนดทั้งหมดได้รับการสังเกตในระหว่างการฝึกอบรมการเพิ่มประสิทธิภาพ นี้ จะเป็นแบบนูน^{[ 7 ]}สามารถแก้ไขได้โดยใช้ อัลกอริทึม การลดระดับความชันหรือวิธีการควาซี-นิวตันเช่น อัลกอริทึม L-BFGSในทางกลับกัน หากตัวแปรบางตัวไม่ได้รับการสังเกต ปัญหาการอนุมานจะต้องได้รับการแก้ไขสำหรับตัวแปรเหล่านี้ การอนุมานที่แม่นยำไม่สามารถทำได้ในกราฟทั่วไป ดังนั้นจึงต้องใช้การประมาณค่า ${\displaystyle \theta }$${\displaystyle p(Y_{i}|X_{i};\theta )}$

ในการสร้างแบบจำลองลำดับ กราฟที่สนใจมักจะเป็นกราฟลูกโซ่ ลำดับอินพุตของตัวแปรที่สังเกตได้แสดงถึงลำดับของการสังเกต และแสดงถึงตัวแปรสถานะที่ซ่อนอยู่ (หรือไม่ทราบค่า) ซึ่งจำเป็นต้องอนุมานจากข้อมูลที่สังเกตได้โครงสร้างของตัวแปรเหล่านี้เรียงตัวเป็นลูกโซ่ โดยมีเส้นเชื่อมระหว่างแต่ละตัวแปรและนอกจากจะมีการตีความที่ง่ายของตัวแปรเหล่านี้ว่าเป็น "ป้ายกำกับ" สำหรับแต่ละองค์ประกอบในลำดับอินพุตแล้ว โครงสร้างนี้ยังเอื้อต่ออัลกอริธึมที่มีประสิทธิภาพสำหรับ: ${\displaystyle X}$${\displaystyle Y}$${\displaystyle Y_{i}}$${\displaystyle Y_{i-1}}$${\displaystyle Y_{i}}$${\displaystyle Y_{i}}$

• การฝึกโมเดลคือการเรียนรู้การแจกแจงแบบมีเงื่อนไขระหว่างฟังก์ชันคุณลักษณะและฟังก์ชันอื่นๆ จากชุดข้อมูลฝึกฝนบางส่วน${\displaystyle Y_{i}}$
• การถอดรหัสคือ การหาความน่าจะเป็นของลำดับป้ายกำกับที่กำหนดให้${\displaystyle Y}$${\displaystyle X}$
• การอนุมานคือ การกำหนดลำดับป้ายกำกับที่น่าจะเป็นไปได้มากที่สุดโดยกำหนดให้${\displaystyle Y}$${\displaystyle X}$

ความสัมพันธ์แบบมีเงื่อนไขของแต่ละตัวแปรถูกกำหนดโดยชุดฟังก์ชันคุณลักษณะ คง ที่ในรูปแบบซึ่งสามารถมองได้ว่าเป็นการวัดลำดับอินพุตที่กำหนดความน่าจะเป็นของแต่ละค่าที่เป็นไปได้สำหรับแบบจำลองจะกำหนดน้ำหนักเชิงตัวเลขให้กับแต่ละคุณลักษณะและรวมเข้าด้วยกันเพื่อกำหนดความน่าจะเป็นของค่าใดค่าหนึ่งสำหรับ ${\displaystyle Y_{i}}$${\displaystyle X}$${\displaystyle f(i,Y_{i-1},Y_{i},X)}$${\displaystyle Y_{i}}$${\displaystyle Y_{i}}$

CRF แบบลูกโซ่เชิงเส้นมีแอปพลิเคชันหลายอย่างคล้ายคลึงกับแบบจำลองมาร์คอฟที่ซ่อนอยู่ (HMM) ซึ่งมีแนวคิดที่เรียบง่ายกว่า แต่ผ่อนคลายข้อสมมติบางประการเกี่ยวกับการกระจายลำดับอินพุตและเอาต์พุต HMM สามารถเข้าใจอย่างคร่าวๆ ได้ว่าเป็น CRF ที่มีฟังก์ชันคุณลักษณะเฉพาะที่ใช้ความน่าจะเป็นคงที่ในการจำลองการเปลี่ยนสถานะและการปล่อยสัญญาณ ในทางกลับกัน CRF สามารถเข้าใจอย่างคร่าวๆ ได้ว่าเป็นการขยาย HMM ที่เปลี่ยนความน่าจะเป็นการเปลี่ยนสถานะคงที่ให้เป็นฟังก์ชันตามอำเภอใจซึ่งแตกต่างกันไปตามตำแหน่งในลำดับของสถานะที่ซ่อนอยู่ ขึ้นอยู่กับลำดับอินพุต

ที่สำคัญคือ เมื่อเปรียบเทียบกับ HMM แล้ว CRF สามารถมีฟังก์ชันคุณลักษณะได้จำนวนเท่าใดก็ได้ ฟังก์ชันคุณลักษณะสามารถตรวจสอบลำดับอินพุตทั้งหมดได้ทุกจุดในระหว่างการอนุมาน และช่วงของฟังก์ชันคุณลักษณะไม่จำเป็นต้องมีการตีความเชิงความน่าจะเป็น ${\displaystyle X}$

CRF สามารถขยายไปสู่โมเดลลำดับที่สูงขึ้นได้โดยทำให้แต่ละโมเดล ขึ้นอยู่กับ ตัวแปรก่อนหน้าจำนวนคงที่ในสูตรดั้งเดิมของ CRF ลำดับที่สูงขึ้น การฝึกอบรมและการอนุมานจะใช้งานได้จริงเฉพาะกับค่าเล็ก ๆ ของ(เช่นk ≤ 5) ^{[ 8 ]}เนื่องจากต้นทุนการคำนวณจะเพิ่มขึ้นแบบทวีคูณตาม ${\displaystyle Y_{i}}$${\displaystyle k}$${\displaystyle Y_{ik},...,Y_{i-1}}$${\displaystyle k}$${\displaystyle k}$

อย่างไรก็ตาม ความก้าวหน้าล่าสุดอีกประการหนึ่งได้ช่วยบรรเทาปัญหาเหล่านี้ได้โดยการใช้ประโยชน์จากแนวคิดและเครื่องมือจากสาขา Bayesian nonparametrics โดยเฉพาะอย่างยิ่ง วิธีการ CRF-infinity ^{[ 9 ]}ประกอบด้วยแบบจำลอง CRF ที่สามารถเรียนรู้พลวัตเชิงเวลาที่ยาวไม่สิ้นสุดในลักษณะที่ปรับขนาดได้ ซึ่งทำได้โดยการแนะนำฟังก์ชันศักยภาพใหม่สำหรับ CRF ที่อิงตาม Sequence Memoizer (SM) ซึ่งเป็นแบบจำลอง Bayesian nonparametric สำหรับการเรียนรู้พลวัตที่ยาวไม่สิ้นสุดในการสังเกตตามลำดับ^{[ 10 ]}เพื่อให้แบบจำลองดังกล่าวสามารถคำนวณได้ง่ายขึ้น CRF-infinity ใช้การประมาณค่าสนามเฉลี่ย^{[ 11 ]}ของฟังก์ชันศักยภาพใหม่ที่ตั้งสมมติฐานไว้ (ซึ่งขับเคลื่อนโดย SM) ซึ่งช่วยให้สามารถคิดค้นอัลกอริทึมการฝึกอบรมและการอนุมานโดยประมาณที่มีประสิทธิภาพสำหรับแบบจำลอง โดยไม่บั่นทอนความสามารถในการจับภาพและสร้างแบบจำลองการพึ่งพาเชิงเวลาที่มีความยาวตามอำเภอใจ

มีการวางนัยทั่วไปของ CRF อีกแบบหนึ่งคือฟิลด์สุ่มแบบมีเงื่อนไขกึ่งมาร์คอฟ (semi-CRF)ซึ่งจำลองการแบ่งส่วน ที่มีความยาวแปรผัน ของลำดับป้ายกำกับ[ ^{12 ] สิ่ง}นี้ให้พลังส่วนใหญ่ของ CRF ลำดับสูงกว่าในการจำลองการพึ่งพาระยะไกลของโดยมีต้นทุนการคำนวณที่สมเหตุสมผล ${\displaystyle Y}$${\displaystyle Y_{i}}$

สุดท้ายนี้ โมเดลที่มีขอบเขตขนาดใหญ่สำหรับการทำนายโครงสร้างเช่นSupport Vector Machine แบบมีโครงสร้างสามารถมองได้ว่าเป็นขั้นตอนการฝึกอบรมทางเลือกแทน CRFs

แบบ จำลองฟิลด์สุ่มแบบมีเงื่อนไขเชิงพลวัตแฝง ( LDCRF ) หรือแบบจำลองตัวแปรแฝงเชิงความน่าจะเป็นแบบจำแนก ( DPLVM ) เป็นแบบจำลอง CRF ประเภทหนึ่งสำหรับงานติดแท็กซีเควนซ์ โดยเป็นแบบจำลองตัวแปรแฝงที่ได้รับการฝึกฝนแบบจำแนก

ใน LDCRF เช่นเดียวกับงานติดแท็กลำดับใดๆ เมื่อกำหนดลำดับการสังเกตx = ปัญหาหลักที่แบบจำลองต้องแก้ไขคือวิธีการกำหนดลำดับของป้ายกำกับy = จากชุดป้ายกำกับY ที่จำกัดชุดหนึ่ง แทนที่จะสร้างแบบจำลอง P ( y | x ) โดยตรงเหมือนที่ CRF แบบลูกโซ่เชิงเส้นทั่วไปจะทำ ชุดของตัวแปรแฝงhจะถูก "แทรก" ระหว่างxและyโดยใช้กฎลูกโซ่ของความน่าจะเป็น : ^{[ 13 ]}${\displaystyle x_{1},\dots ,x_{n}}$${\displaystyle y_{1},\dots ,y_{n}}$

${\displaystyle P(\mathbf {y} |\mathbf {x} )=\sum _{\mathbf {h} }P(\mathbf {y} |\mathbf {h} ,\mathbf {x} )P(\mathbf {h} |\mathbf {x} )}$

สิ่งนี้ช่วยให้สามารถจับโครงสร้างแฝงระหว่างการสังเกตและป้ายกำกับได้^{[ 14 ]}ในขณะที่ LDCRF สามารถฝึกฝนได้โดยใช้วิธีการแบบควาซี-นิวตัน เวอร์ชันเฉพาะของ อัลกอริ ทึม เพอร์เซปตรอน ที่เรียกว่าเพอร์เซปตรอนตัวแปรแฝงได้รับการพัฒนาขึ้นสำหรับพวกมันเช่นกัน โดยอิงจากอัลกอริทึมเพอร์เซปตรอนโครงสร้าง ของคอลลินส์ ^{[ 13 ]}โมเดลเหล่านี้พบการประยุกต์ใช้ในด้านคอมพิวเตอร์วิชั่นโดยเฉพาะอย่างยิ่งการจดจำท่าทางจากสตรีมวิดีโอ^{[ 14 ]}และ การแยก วิเคราะห์แบบตื้น^{[ 13 ]}

• ทฤษฎีบทแฮมเมอร์สลีย์-คลิฟฟอร์ด
• แบบจำลองเอนโทรปีมาร์คอฟสูงสุด (MEMM)

• McCallum, A.: การเหนี่ยวนำคุณลักษณะของฟิลด์สุ่มแบบมีเงื่อนไขอย่างมีประสิทธิภาพใน: รายงานการประชุมวิชาการครั้งที่ 19 ว่าด้วยความไม่แน่นอนในปัญญาประดิษฐ์ (2003)
• Wallach, HM : Conditional random fields: An introduction . รายงานทางเทคนิค MS-CIS-04-21, มหาวิทยาลัยเพนซิลเวเนีย (2004)
• Sutton, C., McCallum, A.: บทนำสู่ฟิลด์สุ่มแบบมีเงื่อนไขสำหรับการเรียนรู้เชิงสัมพันธ์ ใน "บทนำสู่การเรียนรู้เชิงสัมพันธ์ทางสถิติ" บรรณาธิการโดยLise Getoorและ Ben Taskar สำนักพิมพ์ MIT (2006) ไฟล์ PDF ออนไลน์
• Klinger, R., Tomanek, K.: แบบจำลองความน่าจะเป็นแบบคลาสสิกและฟิลด์สุ่มแบบมีเงื่อนไข รายงานวิศวกรรมอัลกอริทึม TR07-2-013 ภาควิชาวิทยาการคอมพิวเตอร์ มหาวิทยาลัยเทคโนโลยีดอร์ทมุนด์ ธันวาคม 2007 ISSN 1864-4503 ไฟล์PDF ออนไลน์