การตรวจจับเอกสารซ้ำแบบคล้ายกันด้วย Jaccard similarity และ MinHash

 (blog.nelhage.com)
1 คะแนน โดย GN⁺ 2024-07-06 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • ในคอลเลกชันเอกสารขนาดใหญ่ ระหว่างการครอลเว็บอาจดึงหน้าเดิมมาหลายครั้ง หรือมีเวอร์ชันที่แก้ไขเล็กน้อยปะปนอยู่ ทำให้ Jaccard similarity และ MinHash กลายเป็นวิธีปฏิบัติที่ใช้ได้จริงในการค้นหาเอกสารที่ “เกือบเหมือนกัน”
  • Jaccard similarity แปลงเอกสารเป็นเซตของคุณลักษณะ แล้วคำนวณ ขนาดอินเตอร์เซกชัน / ขนาดยูเนียน โดยมองว่าคู่ที่มีค่ามากกว่าหรือเท่ากับ threshold เป็นเอกสารซ้ำแบบคล้ายกัน แต่โดยทั่วไปความสัมพันธ์นี้ไม่เป็นแบบถ่ายทอด
  • หากเปรียบเทียบเอกสารทุกคู่ ค่าใช้จ่ายจะเป็น O(n²) ตามขนาดของ corpus ดังนั้น MinHash จึงสรุปเอกสารแต่ละฉบับเป็น signature ขนาดคงที่ เพื่อประมาณค่าความคล้ายแบบเชิงความน่าจะเป็น
  • เมื่อใช้ฟังก์ชันแฮช k ตัว สามารถประมาณค่าความคล้ายได้จากสัดส่วนของค่าที่ตำแหน่งเดียวกันใน signature ของเอกสารสองฉบับที่ตรงกัน และเงื่อนไขอย่าง min-wise independence มีความสำคัญต่อการเลือกฟังก์ชันแฮช
  • การใช้ signature ทั้งหมดหรือบางส่วนของ signature เป็นคีย์สำหรับจัดกลุ่ม ช่วยปรับความน่าจะเป็นที่เอกสารคล้ายกันจะตกใน bucket เดียวกันได้ โดยวิธีทำ n-gram และ tokenization เป็นตัวกำหนดความไวในการตรวจจับและต้นทุน

ความยากของการตรวจจับเอกสารซ้ำแบบคล้ายกัน

  • เป้าหมายคือการหา เอกสารที่ไม่ได้เหมือนกันทุกประการ แต่เกือบเหมือนกัน จากชุดเอกสารขนาดใหญ่
    • หากครอลเว็บเป็นระยะเวลาหนึ่ง อาจดึงหน้าเดิมมาหลายครั้ง แต่ metadata อาจแตกต่างกันเล็กน้อย
    • อาจมีเวอร์ชันที่แก้ไขเล็กน้อยของหน้าเดียวกันอยู่หลายชุดด้วย
  • แนวทางพื้นฐานคือกำหนดฟังก์ชันความคล้าย S(A, B) ระหว่างเอกสารสองฉบับ และถือว่าคู่ที่มีค่ามากกว่าหรือเท่ากับ threshold Scrit เป็นเอกสารซ้ำแบบคล้ายกัน
  • “เกือบเหมือนกัน” โดยทั่วไป ไม่ใช่ความสัมพันธ์แบบถ่ายทอด
    • A กับ B และ B กับ C อาจคล้ายกันเกิน threshold
    • ในขณะเดียวกัน A กับ C อาจต่ำกว่า threshold
    • ด้วยเหตุนี้ การตรวจจับเอกสารซ้ำแบบคล้ายกันในสเกลใหญ่จึงจัดการได้ยากกว่าการตรวจจับเอกสารซ้ำแบบตรงตัว

นิยามของ Jaccard similarity

  • Jaccard index แสดงความคล้ายของเซตจำกัดสองเซตเป็น ขนาดอินเตอร์เซกชัน / ขนาดยูเนียน

    [ J(A, B) = \frac{|A \cap B|}{|A \cup B|} ]

  • หากสองเซตคล้ายกัน ทั้งคู่จะมีสมาชิกส่วนใหญ่เหมือนกัน ทำให้ยูเนียนใหญ่ขึ้นเพียงเล็กน้อย และอินเตอร์เซกชันเล็กลงเพียงเล็กน้อย

  • หากสองเซตแยกจากกันโดยสิ้นเชิง ขนาดอินเตอร์เซกชันจะเป็น 0 ดังนั้น Jaccard similarity จึงเป็น 0

  • หากสองเซตเหมือนกัน อินเตอร์เซกชันและยูเนียนจะเป็นเซตเดียวกันทั้งคู่ ดังนั้น Jaccard similarity จึงเป็น 1

  • เอกสารจริงอยู่ในรูปแบบอย่างสตริง Unicode ดังนั้นต้องแปลงเอกสารเป็น เซตของคุณลักษณะ ก่อน

ปัญหาการขยายขนาดของการเปรียบเทียบทุกคู่

  • เมื่อแปลงเอกสารเป็นเซตของคุณลักษณะแล้ว นิยามการหาคู่ที่มี Jaccard similarity สูงนั้นเรียบง่ายในตัวเอง
  • แต่หากเปรียบเทียบเอกสารทุกคู่ ค่าใช้จ่ายจะเพิ่มขึ้นเป็น O(n²) ตามขนาดของ corpus
  • ในการตรวจจับเอกสารซ้ำแบบตรงตัว จะหลีกเลี่ยงค่าใช้จ่ายนี้ด้วยการแฮชเอกสารแล้วจัดเอกสารที่มีแฮชเดียวกันไว้ใน bucket เดียวกัน
  • การตรวจจับเอกสารซ้ำแบบคล้ายกันก็ต้องมีทางอ้อมลักษณะคล้ายกัน และในสาขานี้เรียกว่า locality-sensitive hash
  • สำหรับ Jaccard similarity มีเทคนิคที่เหมาะกับวัตถุประสงค์นี้ และแกนหลักของมันคือ MinHash

การประมาณ Jaccard similarity ด้วย MinHash

  • MinHash ประมาณ Jaccard similarity ได้โดยไม่ต้องเปรียบเทียบทั้งเซตทุกครั้ง ใช้เพียง signature ขนาดเล็กที่คำนวณไว้ล่วงหน้าสำหรับเอกสารแต่ละฉบับ

  • แนวคิดพื้นฐานคือการสุ่มเลือกสมาชิกอย่างสม่ำเสมอจากยูเนียน แล้วดูว่าสมาชิกนั้นอยู่ในอินเตอร์เซกชันด้วยหรือไม่

  • ในทางปฏิบัติ แทนที่จะใช้ permutation แบบสุ่ม จะใช้ฟังก์ชันแฮชที่ดี H(x) และบันทึกคุณลักษณะที่มีค่าแฮชน้อยที่สุดในแต่ละเซต

    [ a_{min} \leftarrow \min_{x \in A} H(x) ]

    [ b_{min} \leftarrow \min_{x \in B} H(x) ]

  • การดำเนินการ min มีสมบัติการจัดหมู่ จึงสามารถ preprocess ค่าแฮชน้อยที่สุดของเอกสารแต่ละฉบับได้อย่างอิสระ

  • ความน่าจะเป็นที่ค่าแฮชน้อยที่สุดของสองเซตจะเท่ากัน เท่ากับ Jaccard similarity ของสองเซตนั้น

ฟังก์ชันแฮชหลายตัวและเวกเตอร์ signature

  • หากใช้ฟังก์ชันแฮชเพียงตัวเดียว จะได้เพียงการประมาณแบบบูลีนว่า “เหมือน/ต่าง” สำหรับเอกสารสองฉบับ

  • หากใช้ฟังก์ชันแฮชต่างกัน k ตัว จะสรุปเอกสารแต่ละฉบับเป็นเวกเตอร์ที่ประกอบด้วยค่า MinHash k ค่าได้

    [ A_{sig} = (\min_{x \in A} H_1(x), \min_{x \in A} H_2(x), \dots, \min_{x \in A} H_k(x)) ]

  • ประมาณ Jaccard similarity จากสัดส่วนของค่าที่ตำแหน่งเดียวกันใน signature สองชุดที่ตรงกัน

    [ J(A, B) \approx \frac{1}{k} \sum_{i=1}^{k} (A_{sig}[i] = B_{sig}[i]) ]

  • การเลือกตระกูลฟังก์ชันแฮชเป็นเรื่องละเอียดอ่อน

    • เป้าหมายคือการประมาณ permutation แบบสุ่มของพื้นที่คุณลักษณะทั้งหมด
    • ตระกูลฟังก์ชันแฮชจริงแสดงได้เพียงส่วนน้อยมากของ permutation ที่เป็นไปได้ทั้งหมด
    • ต้องหลีกเลี่ยง correlation ที่ไม่เหมาะสม และสมบัติที่เกี่ยวข้องเรียกว่า min-wise independence
    • ปัญหานี้ได้รับการศึกษาค่อนข้างดี และมีวิธีแก้ที่มีประสิทธิภาพในงานวรรณกรรม

การหาคู่ candidate จาก corpus ทั้งหมด

  • เมื่อย่อเอกสารแต่ละฉบับเป็น fingerprint ค่าแฮช k ค่าแล้ว ก็สามารถประมาณ Jaccard similarity ได้อย่างมีประสิทธิภาพ
  • ปัญหาที่เหลือคือการหาเอกสารที่มีความคล้ายสูงจากทั้ง corpus โดยไม่ต้องดูเอกสารทุกคู่
  • กลยุทธ์คือจัดกลุ่มเอกสารด้วยคีย์บางอย่าง แล้วเปรียบเทียบเฉพาะภายในกลุ่มเดียวกัน
  • คีย์ของกลุ่มควรถูกสร้างให้เอกสารคล้ายกันถูกจัดเข้าด้วยกันด้วยความน่าจะเป็นสูง และเอกสารที่ไม่คล้ายกันไม่ควรถูกจัดเข้าด้วยกันเท่าที่เป็นไปได้

  • ใช้ signature MinHash ทั้งหมดเป็นคีย์

    • วิธีที่ง่ายที่สุดคือใช้ค่า MinHash ทั้ง k ค่าเป็นคีย์กลุ่มเดียว
    • ถือว่าเอกสารสองฉบับเป็นเอกสารซ้ำแบบคล้ายกันก็ต่อเมื่อค่า MinHash ทั้งหมดตรงกัน
    • บทความ GPT-3 ใช้การลบเอกสารซ้ำแบบคล้ายกันใน pipeline เตรียม dataset และจากถ้อยคำที่อ้างถึง ตีความได้ว่าใช้ implementation MinHashLSH ของ Spark พร้อมแฮช 10 ตัว
    • ข้อดีของวิธีนี้คือ ความเรียบง่ายและประสิทธิภาพ
    • งานจัดกลุ่มด้วยสตริงไบต์ cardinality สูงหนึ่งชุดขยายแนวนอนได้ง่าย
    • เป็น primitive พื้นฐานของเครื่องมือประมวลผลข้อมูล คล้าย “shuffle” ระหว่าง map และ reduce ใน MapReduce
    • หาก Jaccard similarity ของเอกสารสองฉบับคือ J(A, B) และต้องให้ค่าทั้ง k ค่าตรงกันทั้งหมด ความน่าจะเป็นการชนกันของคู่เดียวคือ J(A, B)^k
    • เมื่อ k = 10 เอกสารที่มีความคล้ายประมาณ 0.6 หรือต่ำกว่าแทบจะไม่ชนกัน
    • ความน่าจะเป็นที่จะตรงกันจะสูงขึ้นบริเวณความคล้ายประมาณ 0.95
    • หากเป้าหมายคือหาเอกสารพี่น้องที่ใกล้กันมาก วิธีนี้อาจเพียงพอ
    • การคำนวณ J^k นี้เป็นของ เอกสารคู่เดียว
    • หากมีเอกสารที่คล้ายกันมากจำนวนมาก ความน่าจะเป็นรายคู่จะไม่เป็นอิสระต่อกัน
    • ในทางปฏิบัติ เอกสารที่คล้ายกันมากมักเข้าไปอยู่ใน bucket ไม่เกินสองสาม bucket และสามารถหาเอกสารซ้ำได้เกือบทั้งหมด

การตรวจจับเอกสารซ้ำที่ผ่อนคลายกว่า

  • หากต้องการหาไม่ใช่แค่เอกสารที่มีความคล้ายใกล้ 1 แต่รวมถึงเอกสารที่มีความคล้าย 0.8 หรือ 0.7 ขึ้นไปด้วย การใช้ signature ทั้งหมดเป็นคีย์อาจเข้มงวดเกินไป

  • หากใช้เพียงบางส่วนของ MinHash k ค่าเป็นคีย์กลุ่ม ความเป็นไปได้ที่จะชนกันแม้ความคล้ายต่ำกว่าก็จะสูงขึ้น

    • ตัวอย่างเช่น จัดกลุ่มด้วยค่า MinHash 4 ค่าแรก แล้วภายใน bucket เดียวกันค่อยใช้ค่า MinHash ทั้งหมดเพื่อประมาณความคล้ายจริง

  • การลดจำนวนแฮชมีขีดจำกัด

    • J^r จะน้อยกว่า J เสมอ
    • หาก r เล็กเกินไป อาจเกิดการชนกันที่ผิดพลาดมากเกินไป

  • แทนที่จะทำเช่นนั้น สามารถสร้าง หลายคีย์ ต่อเอกสารหนึ่งฉบับ แล้วใส่ลงในหลาย bucket ได้

    • ตัวอย่างเช่น คำนวณแฮช k = 20 ตัว ใส่ลงใน bucket b = 4 ชุด โดยแต่ละคีย์ประกอบด้วยแฮช r = 5 ตัว

  • ความน่าจะเป็นที่เอกสารสองฉบับจะชนกันใน bucket อย่างน้อยหนึ่งชุดเป็นดังนี้

    [ p = 1 - (1 - J^r)^b ]

  • ในตัวอย่างที่ใช้กลุ่ม 4 ชุดและแฮช 5 ตัวต่อกลุ่ม จุดที่ความน่าจะเป็นการชนกันเป็น 50% จะย้ายไปอยู่บริเวณประมาณ J = 0.7

  • หากทั้ง r และ b มากกว่า 1 เส้นโค้งผลลัพธ์โดยทั่วไปจะเป็นรูปตัว S และให้พื้นที่สำหรับปรับระหว่าง sensitivity, recall และต้นทุนด้านประสิทธิภาพ

ความเกี่ยวข้องกับ HyperLogLog

  • เคล็ดลับหลักของ MinHash มีจุดคล้ายกับอัลกอริทึม sketch อย่าง HyperLogLog
  • HyperLogLog แฮชสมาชิกแต่ละตัวใน stream แล้วบันทึกค่าสูงสุดที่เกิดขึ้นของจำนวน 0 นำหน้าในค่าแฮช
  • ทั้งสองเทคนิคแมปสมาชิกอินพุตไปยังการแจกแจงสม่ำเสมอด้วยฟังก์ชันแฮช แล้วคำนวณค่าสุดขั้วที่เกิดขึ้น เพื่อประมาณสมบัติเชิงการแจกแจงด้วย สรุปขนาดคงที่ เท่านั้น
  • หากคิดด้วยการกลับลำดับบิต HyperLogLog สามารถมองได้ว่าเป็นการคำนวณค่าต่ำสุดที่เกิดขึ้นของ log2(H(x)) ส่วน MinHash ใช้ค่าต่ำสุดของ H(x) เอง
  • โครงสร้างทั้งสองเป็นคู่กันในบางความหมาย
    • เมื่อนำโครงสร้าง HyperLogLog สองชุดมารวมกัน จะประมาณ ขนาดยูเนียน ของสองเซตได้
    • เมื่อเปรียบเทียบโครงสร้าง MinHash สองชุด จะประมาณ ขนาดสัมพัทธ์ของอินเตอร์เซกชัน ของสองเซตได้
  • เมื่อนำสองโครงสร้างมารวมกัน จะสร้าง sketch ที่ตอบคำถามเกี่ยวกับอินเตอร์เซกชันและยูเนียนของเซตใด ๆ ได้

วิธีแทนเอกสารเป็นเซต

  • หากต้องการใช้ Jaccard และ MinHash ต้องแปลงเอกสารสตริงเป็น เซตของคุณลักษณะ ก่อน
  • ไม่ว่าจะใช้วิธีใด ก็สามารถ normalize เอกสารด้วย preprocessing ได้
    • แปลงเป็น Unicode normalization form มาตรฐาน
    • ทำ case folding
    • ยุบช่องว่างต่อเนื่อง
    • การแปลงลักษณะคล้ายกัน

  • n-gram หรือ shingle

    • สามารถแทนเอกสารเป็นเซตของ n-gram ทั้งหมดที่ปรากฏในเอกสารนั้น
    • ในวรรณกรรมการประมวลผลข้อความขนาดใหญ่ยังใช้คำว่า “shingle” ด้วย แต่ในที่นี้มีบทบาทเดียวกับ n-gram
    • การเลือกค่า n มี trade-off
    • ค่าขนาดเล็กทำให้เปรียบเทียบเอกสารแบบหยาบขึ้น
    • ตัวอย่างเช่น ข้อความภาษาอังกฤษส่วนใหญ่อาจดูค่อนข้างคล้ายกันจากมุมมองของ bigram
    • ค่าขนาดใหญ่สร้างคุณลักษณะที่แยกแยะได้มากขึ้นและเซตที่ใหญ่ขึ้น
    • หากใหญ่เกินไป sensitivity อาจลดลง แต่ก่อนถึงจุดนั้นมีแนวโน้มว่าจะพบปัญหาด้านประสิทธิภาพก่อน
    • ตาม Mining of Massive Datasets §3.2.2 ในหลายแอปพลิเคชัน ค่าในช่วง n = 5 ถึง 9 ดูเหมือนเป็นตัวเลือกที่พบบ่อย

  • การแยกคำหรือ token

    • สามารถแบ่งอินพุตเป็น “คำ” หรือ “token” แล้วใช้สิ่งเหล่านั้นเป็นคุณลักษณะได้เช่นกัน
    • ข้อความที่ตัดมาจากบทความ GPT-3 กล่าวถึง tokenizer มาตรฐานของ Spark ซึ่งดูเหมือนหมายถึง pyspark.ml.feature.Tokenizer ที่แปลงอินพุตเป็นตัวพิมพ์เล็กแล้วแบ่งตามช่องว่าง
    • อาจใช้ NLTK tokenizer ที่ซับซ้อนกว่านี้ได้ด้วย
    • วิธีไฮบริดที่ใช้ n-gram ของ token หลังจาก tokenization ก็เป็นไปได้
    • token เดี่ยวมี entropy สูงกว่าไบต์หรืออักขระ ดังนั้นในกรณีนี้จึงใช้ค่า n ที่เล็กกว่า

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-07-06
ความคิดเห็นบน Hacker News

  • หลายคนมักมองข้ามไปว่าเมตริกแบบอิงเซต เช่น Jaccard similarity (ค่าสัมประสิทธิ์ Tanimoto) หรือ F1 score (ค่าสัมประสิทธิ์ Dice) สามารถใช้กับ fuzzy set ได้เช่นกัน
    เพียงแต่ต้องเลือกคู่ T-Norm / T-Conorm ที่เหมาะสมเพื่อแทนแนวคิดของ intersection และ union ของ fuzzy set ซึ่งมีให้เลือกไม่จำกัด
    ในทางกลับกัน การเลือกคู่ที่ตรงกับ semantics ที่ต้องการได้ถือเป็นข้อดีด้วยซ้ำ
    ในการตรวจสอบความถูกต้องของการแบ่งส่วนภาพทางการแพทย์ เคยมีการพูดถึงเรื่องนี้เมื่อผลลัพธ์การแบ่งส่วนและคำตอบเฉลยไม่ใช่ binary mask แต่เป็นแบบ probabilistic/fuzzy: https://link.springer.com/chapter/10.1007/978-3-319-46723-8_..., https://ora.ox.ac.uk/objects/uuid:dc352697-c804-4257-8aec-08...
    โดยทั่วไปมัก threshold ที่ 0.5 เพื่อสร้าง binary set แล้วใช้รูปแบบ binary ของ Jaccard/Dice แต่ดูเหมือนว่าวิธีนี้ทำให้ precision ของตัวดำเนินการตรวจสอบลดลงราวสองหลัก
    เท่ากับว่าประกาศว่าอัลกอริทึมดีกว่าวิธีล้ำสมัยอยู่ 0.001 แต่กลับมองข้ามความจริงที่ว่าขอบเขตความคลาดเคลื่อนของตัวดำเนินการตรวจสอบคือ 0.1

  • เคยมีลูกค้าสร้าง implementation Python ของเทคนิคนี้เองเพื่อทำ deduplication รายการพลเมืองในฐานข้อมูลขนาดใหญ่ของรัฐบาลฝรั่งเศส และมันทำงานได้ดี
    ถ้าเป็นสมัยนี้คงแนะนำให้ใช้ datasketch: https://pypi.org/project/datasketch/
    ลองค้นดูแล้วก็พบว่ายังมีเครื่องมือใหม่ ๆ ในหัวข้อนี้ออกมาเรื่อย ๆ เช่น https://pypi.org/project/rensa/ เป็นเวอร์ชันที่เฉพาะทางและเร็วกว่า MinHash ของ datasketch เขียนด้วย Rust แล้ววาง Python บางส่วนไว้ด้านบน

    • สำหรับการลบรายการบุคคลที่ซ้ำกัน Fellegi-Sunter model ก็เป็นแนวทางที่ทรงพลังเช่นกัน Splink เป็นไลบรารี Python ฟรีที่ implement แนวทางนี้สำหรับชุดข้อมูลขนาดใหญ่ และน่าจะผสมผสานบางส่วนของสองแนวทางเข้าด้วยกันได้
      ขอเปิดเผยว่าผมเป็นผู้เขียนหลัก
      ผมยังได้ทำ interactive tutorial ที่อธิบายวิธีทำงานไว้ด้วย: https://github.com/moj-analytical-services/splink, https://www.robinlinacre.com/intro_to_probabilistic_linkage/
    • มี gaoya ด้วย ผมเป็นคนสร้างเอง เขียนด้วย Rust และมี Python binding ให้ด้วย
      datasketch นั้นยอดเยี่ยม แต่ performance ยังไม่พอสำหรับ use case ของผม ส่วน gaoya ถูกใช้อยู่ในระบบปฏิบัติการ clustering ขนาดใหญ่: https://github.com/serega/gaoya

  • บังเอิญมาก ผมเพิ่ง implement ระบบ MinHash ที่น่าจะมีคนสนใจ
    ปัญหาคือการหา pseudoinverse ของเมทริกซ์ย่อยที่เหมาะสมหลายตัวในเมทริกซ์จัตุรัสขนาดใหญ่
    หากใช้เอกลักษณ์ของเมทริกซ์อย่าง Woodbury, Banachiewicz ก็สามารถอัปเดต inverse ของเมทริกซ์ย่อยที่ “ใกล้เคียง” เพื่อคำนวณ inverse ใหม่ได้อย่างประหยัด
    แค่เก็บ inverse ที่คำนวณไว้แล้วโดยใช้ดัชนีแถว/คอลัมน์เป็น key แล้วสำหรับเมทริกซ์ย่อยใหม่แต่ละตัว ให้หา inverse เดิมที่ใกล้เคียงเพื่อใช้เป็นจุดเริ่มต้นในการอัปเดต
    ผมแก้ปัญหานี้ด้วย MinHash โดยทำ minimum-value hashing กับดัชนี เพื่อให้เมทริกซ์ที่ใกล้เคียงกันมีโอกาสสูงที่จะได้ hash เดียวกัน
    ใน implementation ของผมใช้ multi-resolution hash เพื่อให้ปรับ selectivity ของการค้นหาได้เมื่อจำนวน inverse ที่คำนวณไว้แล้วเพิ่มขึ้น

  • ขอเสริมบริบทที่ขาดไปจากบทความนี้เล็กน้อย ผมเข้าใจว่าเทคนิคนี้ถูกสร้างขึ้นในยุคแรก ๆ ของ Google เพื่อทำ deduplication ของชุดข้อมูลที่ crawl มา
    สิ่งที่น่าสนใจอีกอย่างคือการสร้าง LLM กับการทำดัชนีข้อความเว็บทั่วไปนั้นคล้ายกันอย่างน่าประหลาด
    อ่านรายละเอียดได้ในหนังสือฟรีของ Jeffrey Ullman ชื่อ “Mining Massive Datasets” ซึ่งอธิบายเทคนิคเจ๋ง ๆ และน่าประทับใจมากมายที่ใช้สร้างดัชนีอินเทอร์เน็ตทั้งโลกในตอนนั้น
    หาเอกสารที่เกี่ยวข้องได้ฟรีโดยค้นหา “chapter 3 pdf mmds ullman”
    แก้ไข: ปรากฏว่าผมเข้าใจผิด ตาม Wikipedia ระบุว่า DEC เป็นผู้คิดค้นสำหรับ AltaVista: https://en.wikipedia.org/wiki/MinHash
    อย่างไรก็ตาม หนังสือของ Ullman มีคำอธิบายที่ดี และยังพูดถึงวิธีที่ Google ใช้งานด้วย

  • พยายามทำความเข้าใจ MinHash และรูปแบบต่าง ๆ แล้วรู้สึกไม่ค่อยเข้าหัว เลยกำลังทำ เครื่องมือ visualization ออนไลน์อยู่: https://websla.sh/tools/minhash
    ยังไม่เสร็จสมบูรณ์ และอยากแสดงอย่างการคำนวณ Jaccard similarity ด้วย แต่ตอนนี้ก็สามารถป้อนหลายสตริงแล้วดูได้ด้วยตัวเองว่า “minhash” จริง ๆ คืออะไร

  • การใช้ hashing หรือ neural network ขนาดเล็กร่วมกับ vector search engine และ Tanimoto/Jaccard เป็นกลยุทธ์ที่พบได้บ่อยมากในการ deduplication ชุดข้อมูลขนาดใหญ่
    อาจฉลาดกว่าการใช้ MapReduce job ที่มีความซับซ้อนเชิงเส้น
    มีโปรเจกต์ที่ดีของ Google ซึ่งใช้โมเดล RETSim 500,000 พารามิเตอร์กับเอนจิน USearch: https://github.com/google/unisim

  • ตอนนี้เจอปัญหาคล้าย ๆ กันใน PostgreSQL มี feed_items อยู่ 600000 รายการ และสคีมาคือ (feed_item_id uuid, author varchar, content text, guid varchar, link varchar, title varchar, summary text, feed_id integer)
    โดยเฉพาะคอลัมน์ content กับ summary ของข่าวบางรายการจะคล้ายกันมาก แต่ไม่เหมือนกันเสียทีเดียว
    ถ้ามีข่าวสองรายการแบบนี้ แล้วอยากยุบให้เหลือรายการเดียว มีวิธีดี ๆ ไหม?

    • ผมเคยทำ ระบบที่คล้าย MinHash ใน BigQuery และสามารถคำนวณ cosine similarity ระหว่างรายการ Stack Overflow ทั้งหมดได้ภายในเวลาที่สมเหตุสมผล
      ขั้นตอนคร่าว ๆ เป็นแบบนี้
      1. นำฟิลด์ข้อความทั้งหมดมาต่อกัน แล้วแบ่งเป็นอาร์เรย์ n-gram เช่น หน่วยตัวอักษรขนาด 2 ถึง n
      2. ประกาศอาร์เรย์โกลบอล A และ B ความยาว n แล้วเติมด้วยจำนวนเต็มสุ่มขนาด 32–64 บิต
      3. แฮช n-gram แต่ละตัวเป็นจำนวนเต็ม 32–64 บิต จากนั้นนำค่าแฮชนั้นไปคูณกับค่าสุ่มแต่ละค่าของอาร์เรย์ A แล้วเอาผลลัพธ์ไปหารเอาเศษด้วยค่าสุ่มแต่ละค่าของอาร์เรย์ B จากนั้นเลือกค่าต่ำสุด
        เป้าหมายคือให้แต่ละแถวได้อาร์เรย์จำนวนเต็มที่ “minhashed” แล้ว ซึ่งมีความยาวเท่ากับอาร์เรย์ในขั้นตอนที่ 2 ถ้าประกาศความยาวอาร์เรย์โกลบอลเป็น 64 อาร์เรย์ MinHash ของแต่ละแถวก็จะยาว 64 เช่นกัน
      4. ใช้ window function รวมค่า MinHash ที่ต่อเนื่องกัน N ค่า เพื่อจัดอาร์เรย์แฮชเป็นบักเก็ต เช่น รวมทีละ 4 แถวต่อเนื่องกัน
        ถ้าทำได้ถูกต้อง ให้คลี่อาร์เรย์นี้ออกมาเป็น “แถวต้นทาง” แล้ว join ชุดข้อมูลกับตัวเองด้วยค่า MinHash ที่ถูกจัดบักเก็ตแต่ละค่า ก็จะได้คอลัมน์ “แถวปลายทาง” เพิ่มเข้ามา
        จากนั้น group by คอลัมน์ต้นทาง/ปลายทางและนับจำนวนครั้งที่เกิดขึ้น ก็จะประมาณได้ว่าสองแถวนั้นคล้ายกันแค่ไหน
        โดยแก่นแล้ว ยิ่งสองรายการถูกแฮชไปอยู่ในบักเก็ตที่คล้ายกันมากเท่าไร ก็ยิ่งคล้ายกันมากเท่านั้น ส่วนจะเริ่มคำนวณ Jaccard หรือ cosine similarity แบบ pairwise จริง ๆ ตั้งแต่จุดไหน ก็ต้องกำหนดเอง
    • ในกรณีนี้ วิธีที่ใช้ text embedding กับ cosine similarity อาจมีประโยชน์: https://simonwillison.net/2023/Oct/23/embeddings/
    • การใช้ MinHash ช่วยเลี่ยง เมทริกซ์ระยะทาง O(N^2) แบบเต็มได้ แต่ถ้ามีรายการแค่ 600000 รายการ เพื่อความง่าย การคำนวณเมทริกซ์เต็มแบบ brute force ก็อาจยังพอทำได้
      ประเด็นสำคัญคือมีงบเวลาเท่าไร
    • ถ้ามองว่าสองรายการพูดถึง คีย์เวิร์ด ที่คล้ายกันมาก ระยะทาง Jaccard น่าจะเหมาะ
      ถ้ามองว่าสองรายการมี ข้อความ ที่คล้ายกันมากร่วมกัน ก็น่าลองใช้ระยะทาง Levenshtein
    • ให้ LLM สร้าง inverted index สำหรับรายการต่าง ๆ แต่บังคับให้คง cardinality ไว้ต่ำ
      จากนั้นก็ใช้ Jaccard similarity ได้

  • ชอบบทความนี้ ทีมของเราที่ NVIDIA เพิ่งปล่อยเวอร์ชันเร่งความเร็วด้วย GPU ของ อัลกอริทึม fuzzy deduplication ที่อธิบายไว้เมื่อไม่นานมานี้ และคิดว่าชุมชนนี้ก็น่าจะสนใจ
    รีโพซิทอรีอยู่ที่นี่: https://github.com/NVIDIA/NeMo-Curator/
    เอกสารของสคริปต์ fuzzy deduplication อยู่ที่นี่: https://docs.nvidia.com/nemo-framework/user-guide/latest/dat...
    มีตัวอย่าง Python ด้วย: https://github.com/NVIDIA/NeMo-Curator/blob/main/examples/fu...
    อยากได้ฟังฟีดแบ็ก

  • เทคนิคแบบนี้เป็นประเภทที่อ่านเป็นบทความแล้วไม่ค่อยเข้าใจ แต่พอเอาข้อมูลของตัวเองใส่ในตัวอย่างโค้ดที่รันได้สักสองสามครั้ง แล้วดูขั้นตอนภายใน ก็ซึมซับได้ทันที
    ผมเรียนรู้เทคนิคนี้ครั้งแรกจาก Douglas Eck: https://research.google/people/douglas-eck/
    Google ใช้มันกับการจัดคลัสเตอร์เพลง และจำได้ว่าเขาพูดถึงการแฮชกับเวกเตอร์สุ่ม
    ตอนนั้นผมสับสน เพราะคิดว่าวิธีปรับให้เหมาะสมที่มีความสุ่มน้อยกว่าน่าจะทำงานได้ดีกว่า

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

  • ถ้ามองในฐานะเทคนิคสำหรับ document clustering หรือการลบรายการซ้ำในชุดข้อมูล แนวทางแบบ “โยน machine learning เข้าไปแก้ปัญหา” เมื่อเทียบกับวิธีอัลกอริทึมแบบไม่ต่อเนื่องที่เรียบง่ายกว่านี้ คุณภาพและประสิทธิภาพจะเป็นอย่างไร?
    เช่น สร้าง vector embedding ของเอกสารด้วย LLM encoder ที่ฝึกล่วงหน้า แล้วใส่เวกเตอร์นั้นลงใน vector DB จากนั้นจัดคลัสเตอร์ด้วย k-means

    • LLM เป็นเพียงหนึ่งในหลายวิธีสำหรับสร้าง embedding
      ถ้าจะทำ k-means ก็ยังต้องเลือกฟังก์ชันระยะทางอย่าง Jaccard อยู่ดี และ k-means อาจไม่เหมาะกับ near-duplicate เท่าไร
      อาจใช้ MinHash เป็นการประมวลผลล่วงหน้าก่อน k-means เพื่อเพิ่มความเร็วได้
      ผมไม่คิดว่า vector DB จะช่วยได้มากนัก
      ถ้ามีเอกสารหลายร้อยล้านฉบับ อาจใช้เพื่อทำให้การค้นหา MinHash sketch เร็วขึ้นได้ แต่โดยรวมแล้วน่าจะเป็นทางเลือกที่เกินจำเป็น
    • ผมเคยเห็นวิธีแบบนั้นทำงานได้ดีกว่า LSH
      ทุกครั้งที่ฝังเอกสาร จะค้นหา approximate nearest neighbor ก่อนเพิ่มเข้าไป ดังนั้นจึงเป็น O(N) เหมือน MinHash
      vector index อย่าง HNSW และ PQ มี trade-off ระหว่างประสิทธิภาพ/คุณภาพดีกว่า SimHash LSH ซึ่งเป็นคู่เทียบของ MinHash สำหรับระยะทาง cosine
      คุณภาพขึ้นอยู่กับว่านิยาม near-duplicate อย่างไร และใช้โมเดล embedding ตัวไหน
      โมเดลสมัยใหม่ทำงานได้ดี และถ้ามีข้อมูลที่ติดป้ายกำกับ ก็ปรับให้ดีขึ้นได้ด้วย fine-tuning
      ข้อเสียหลักคือค่าใช้จ่ายเพิ่มเติมในการทำ embedding ให้เอกสารทั้งหมด โดยเฉพาะเอกสารยาว ๆ จะหนักมาก
      แต่ด้วยโมเดลขนาดเล็ก การปรับแต่งที่ดีขึ้น และฮาร์ดแวร์ที่เร็วขึ้น ค่าใช้จ่ายนี้ลดลงอย่างรวดเร็วมาก