Skip to content
กลับไปยังผลการค้นหา

การเติมเต็มเมทริกซ์

ผู้เสนอ
Emmanuel Candès & Benjamin Recht
ปี
2009
ประเภท
Convex low-rank recovery
กลุ่มวิธี
Missing data

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

การเติมเต็มเมทริกซ์ (Matrix Completion) เป็นเทคนิคสำหรับการกู้คืนเมทริกซ์อันดับต่ำจากชุดข้อมูลย่อยขนาดเล็กที่อาจสุ่มมาบางส่วนของรายการข้อมูลในเมทริกซ์นั้น Emmanuel Candès และ Benjamin Recht ได้นำเสนอเทคนิคนี้ในปี 2009 โดยปรับเปลี่ยนปัญหาเป็นการลดขนาดนอร์มนิวเคลียร์ (nuclear norm minimization) ซึ่งเป็นตัวแทนแบบคอนเวกซ์ (convex surrogate) สำหรับการลดอันดับ (rank minimization) และให้การรับประกันทางทฤษฎีว่าการกู้คืนที่แม่นยำสามารถทำได้เมื่อมีการสังเกตรายการข้อมูลแบบสุ่มอย่างสม่ำเสมอ และเมทริกซ์เป็นไปตามเงื่อนไขความไม่สอดคล้องกัน (incoherence condition)

แนวคิดเบื้องหลังวิธีการ

ลองจินตนาการถึงสเปรดชีตที่กรอกข้อมูลคะแนนภาพยนตร์ของผู้ใช้บางส่วนซึ่งเซลล์ส่วนใหญ่ว่างเปล่า หากข้อมูลพื้นฐานมีโครงสร้างที่เรียบง่าย เช่น รสนิยมถูกอธิบายด้วยปัจจัยแฝงเพียงไม่กี่อย่าง เช่น ความชอบประเภทและยุคสมัย การทราบคะแนนเพียงเล็กน้อยก็เพียงพอที่จะเติมเต็มส่วนที่เหลือได้อย่างมั่นใจ การเติมเต็มเมทริกซ์ใช้ประโยชน์จากโครงสร้างมิติที่ซ่อนอยู่ซึ่งมีมิติต่ำนี้ คล้ายกับการต่อจิ๊กซอว์ให้สมบูรณ์เมื่อคุณรู้ว่าภาพมีรูปร่างที่แตกต่างกันเพียงไม่กี่แบบ

ประวัติศาสตร์

การเติมเต็มเมทริกซ์เกิดขึ้นจากวรรณกรรมด้านการรับรู้แบบบีบอัด (compressed sensing) Candès และ Recht (2009) ได้สร้างทฤษฎีการกู้คืนที่แม่นยำครั้งแรกผ่านการลดนอร์มนิวเคลียร์ ตามมาด้วยงานของ Candès และ Tao เกี่ยวกับพลังของความไม่สอดคล้องกัน วิธีการนี้ได้รับความสนใจอย่างกว้างขวางจากสาธารณชนผ่านการแข่งขัน Netflix Prize ซึ่งวิธีการกรองร่วมอันดับต่ำ (low-rank collaborative filtering) ได้รับความแม่นยำในการแนะนำที่ล้ำสมัย งานต่อมาโดย Recht, Fazel และ Parrilo ได้เชื่อมโยงการลดนอร์มนิวเคลียร์กับการทำให้เป็นมาตรฐานนอร์มร่องรอย (trace norm regularization) ในการเรียนรู้ของเครื่อง

ควรใช้เมื่อใด

ใช้การเติมเต็มเมทริกซ์เมื่อข้อมูลสามารถจัดระเบียบเป็นเมทริกซ์ที่มีรายการที่ขาดหายไปอย่างเป็นระบบ และมีเหตุผลที่เชื่อได้ว่าสัญญาณจริงมีอันดับต่ำ เช่น ในระบบแนะนำ (recommender systems) จีโนมิกส์ (genomics) การวิเคราะห์เครือข่ายสังคม (social network analysis) และการกู้คืนภาพ (image recovery) ข้อสมมติฐานหลักคือรายการข้อมูลขาดหายไปแบบสุ่มและเมทริกซ์เป็นไปตามเงื่อนไขความไม่สอดคล้องกัน เทคนิคนี้ไม่เหมาะสมสำหรับเมทริกซ์ที่มีการขาดหายไปแบบมีโครงสร้างหรือไม่สุ่ม โครงสร้างอันดับสูงมาก หรือเมื่อข้อสมมติฐานอันดับต่ำไม่สมเหตุสมผล ทางเลือกอื่น ๆ ได้แก่ การประมาณค่า MICE สำหรับข้อมูลที่ขาดหายไปทั่วไป และ NMF เมื่อต้องการค่าที่ไม่เป็นลบ

ข้อจำกัดและข้อควรพิจารณา

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

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • การกู้คืนที่แม่นยำอย่างพิสูจน์ได้ภายใต้เงื่อนไขที่ไม่รุนแรงด้วยโปรแกรมคอนเวกซ์แบบพหุนาม
  • จัดการกับอัตราการขาดหายไปที่สูงมากเมื่อเมทริกซ์มีอันดับต่ำจริง ๆ
  • ไม่จำเป็นต้องมีความรู้ล่วงหน้าเกี่ยวกับอันดับ การลดนอร์มนิวเคลียร์จะค้นหาอันดับโดยปริยาย
  • การรับประกันทางทฤษฎีที่แข็งแกร่งซึ่งมีรากฐานมาจากทฤษฎีเมทริกซ์สุ่มและการวิเคราะห์คอนเวกซ์

การประยุกต์ใช้

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

วิธีการทำงาน

วิธีการทำงาน

1

อัลกอริทึมเริ่มต้นด้วยเมทริกซ์ M ซึ่งรายการข้อมูลถูกสังเกตเฉพาะในชุดดัชนี Omega ค่าที่สังเกตได้เหล่านี้เป็นข้อจำกัดสำหรับปัญหาการกู้คืน รูปแบบความเบาบาง (sparsity pattern) ถูกสมมติว่าสุ่มตัวอย่างอย่างสม่ำเสมอ ซึ่งเป็นการตั้งค่าทางทฤษฎีที่ใช้ในการสร้างการรับประกันการกู้คืนที่แม่นยำ

สูตร
\text{Given } M \in \mathbb{R}^{n_1 \times n_2},\; \text{observe entries } \{M_{ij}\}_{(i,j)\in\Omega}
2

เนื่องจากการลดอันดับของเมทริกซ์โดยตรงเป็นปัญหา NP-hard Candès และ Recht จึงเสนอการลดนอร์มนิวเคลียร์ ซึ่งเป็นผลรวมของค่าเอกฐาน (singular values) เป็นการผ่อนคลายแบบคอนเวกซ์ (convex relaxation) นอร์มนิวเคลียร์มีบทบาทเดียวกันสำหรับเมทริกซ์กับที่ L1 นอร์มมีสำหรับเวกเตอร์ในการรับรู้แบบบีบอัด (compressed sensing): มันส่งเสริมโซลูชันอันดับต่ำในขณะที่ทำให้ปัญหาสามารถจัดการได้ผ่านการเขียนโปรแกรมเชิงกึ่งบวก (semidefinite programming)

สูตร
\min_{X} \|X\|_* \quad \text{subject to} \quad X_{ij} = M_{ij},\; \forall (i,j)\in\Omega
3

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

สูตร
\max_{i} \|U^\top e_i\|^2 \leq \frac{\mu r}{n_1},\quad \max_{j} \|V^\top e_j\|^2 \leq \frac{\mu r}{n_2}
4

เมื่อจำนวนรายการที่สังเกตได้เกินเกณฑ์ที่สัดส่วนกับ mu คูณอันดับ r คูณ n log n ตัวลดขนาดของปัญหานอร์มนิวเคลียร์จะกู้คืนเมทริกซ์จริงได้อย่างแม่นยำด้วยความน่าจะเป็นสูง ผลลัพธ์นี้แสดงให้เห็นว่าขนาดตัวอย่างที่ต้องการมีขนาดใหญ่กว่าระดับความเป็นอิสระภายในของเมทริกซ์อันดับ r เพียงเล็กน้อยในเชิงพหุคูณลอการิทึม ทำให้แนวทางนี้ใกล้เคียงกับค่าที่เหมาะสมที่สุดในเชิงทฤษฎีข้อมูล

สูตร
\text{If } |\Omega| \geq C \cdot \mu r n \log n,\; \text{then } \hat{X} = M \text{ with high probability}

ข้อผิดพลาดที่พบบ่อย

  • การสมมติว่าการขาดหายไปแบบสุ่มอย่างสม่ำเสมอในขณะที่การสังเกตจริงถูกเลือกโดยผู้ใช้หรือมีอคติ (เช่น มีการให้คะแนนเฉพาะรายการที่ได้รับคะแนนสูงเท่านั้น) ซึ่งละเมิดแบบจำลองการสุ่มตัวอย่างทางทฤษฎี
  • การละเลยที่จะตรวจสอบเงื่อนไขความไม่สอดคล้องกัน ซึ่งนำไปสู่การกู้คืนที่ไม่ดีแม้จะมีการสังเกตเพียงพอ
  • การใช้การลดนอร์มนิวเคลียร์โดยไม่มีการปรับขนาดหรือการทำให้เป็นมาตรฐานในสภาพแวดล้อมที่มีสัญญาณรบกวน ซึ่งสูตรการกู้คืนที่แม่นยำไม่เหมาะสม
  • การรวมการเติมเต็มเมทริกซ์เข้ากับฮิวริสติกการแยกตัวประกอบเมทริกซ์: กำลังสองน้อยที่สุดแบบสลับ (alternating least squares) อาจบรรจบกันที่ค่าต่ำสุดเฉพาะที่และขาดการรับประกันการกู้คืนของการลดนอร์มนิวเคลียร์

คำถามที่พบบ่อย

การลดนอร์มนิวเคลียร์เป็นวิธีเดียวในการแก้ปัญหาการเติมเต็มเมทริกซ์หรือไม่?

ไม่ การกำลังสองน้อยที่สุดแบบสลับ (ALS) และการไล่ระดับสีบนรูปแบบที่แยกตัวประกอบ (เช่น SGD บน U และ V โดยที่ M ≈ UV^T) ถูกนำมาใช้กันอย่างแพร่หลายในทางปฏิบัติเพื่อความสามารถในการปรับขนาด อย่างไรก็ตาม แนวทางที่ไม่ใช่คอนเวกซ์เหล่านี้ขาดการรับประกันการกู้คืนที่แม่นยำของการลดนอร์มนิวเคลียร์และอาจบรรจบกันที่ค่าต่ำสุดเฉพาะที่โดยไม่มีการเริ่มต้นที่ระมัดระวัง

ต้องใช้ข้อมูลเท่าใดสำหรับการกู้คืนที่แม่นยำ?

Candès และ Recht แสดงให้เห็นว่ารายการที่สังเกตได้ประมาณ C·mu·r·n·log(n) ก็เพียงพอสำหรับเมทริกซ์อันดับ r ขนาด n×n ที่มีพารามิเตอร์ความไม่สอดคล้องกัน mu ในทางปฏิบัติหมายความว่าเมทริกซ์อันดับต่ำมักจะสามารถกู้คืนได้จากตัวอย่างที่มีขนาดเพียงไม่กี่เท่าของระดับความเป็นอิสระภายใน ซึ่งเท่ากับ r(2n−r) สำหรับเมทริกซ์ขนาด n×n

เงื่อนไขความไม่สอดคล้องกันคืออะไรและทำไมจึงสำคัญ?

ความไม่สอดคล้องกันวัดว่าเวกเตอร์เอกฐานกระจายตัวไปทั่วฐานพิกัดมากน้อยเพียงใด เมทริกซ์ที่มีเวกเตอร์เอกฐานที่รวมศูนย์ เช่น เมทริกซ์อันดับ 1 ที่ไม่เป็นศูนย์เฉพาะในแถวเดียว จะเก็บข้อมูลส่วนใหญ่ไว้ในชุดรายการเล็ก ๆ หากรายการเหล่านั้นไม่ได้ถูกสังเกต การกู้คืนก็เป็นไปไม่ได้ไม่ว่าจะทราบรายการอื่น ๆ มากน้อยเพียงใด

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Candès, E. J., & Recht, B. (2009). Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6), 717–772.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว