Count sketch เป็นวิธี การลดมิติประเภทหนึ่งที่มีประสิทธิภาพเป็นพิเศษในสถิติ การเรียนรู้ ของเครื่องและอัลกอริธึม [ ^{1 ] [ 2 ] คิดค้น} โดย Moses Charikar, Kevin Chen และ Martin Farach-Colton ^{[ 3 ]}เพื่อเร่งความเร็วAMS Sketchโดย Alon, Matias และ Szegedy สำหรับการประมาณโมเมนต์ความถี่ของสตรีม^{[ 4 ]} (การคำนวณเหล่านี้ต้องนับจำนวนครั้งที่เกิดขึ้นสำหรับองค์ประกอบที่แตกต่างกันของสตรีม)

โครงร่างนี้เกือบจะเหมือนกับ อัลกอริธึมการ แฮชคุณลักษณะของ John Moody ^{[ 5 ]}แต่แตกต่างกันตรงที่ใช้ฟังก์ชันแฮชที่มีการพึ่งพาต่ำ ซึ่งทำให้ใช้งานได้จริงมากขึ้น เพื่อให้ยังคงมีโอกาสประสบความสำเร็จสูง จึงใช้เทคนิค ค่ามัธยฐาน เพื่อรวมโครงร่างการนับหลายรายการ แทนที่จะใช้ค่าเฉลี่ย

คุณสมบัติเหล่านี้อนุญาตให้ใช้วิธีการเคอร์เนล ที่ชัดเจน การรวมแบบไบลิเนียร์ในเครือข่ายประสาทและเป็นรากฐานสำคัญในอัลกอริธึมพีชคณิตเชิงเส้นเชิงตัวเลขจำนวนมาก^{[ 6 ]}

ผู้คิดค้นโครงสร้างข้อมูลนี้เสนอคำอธิบายการทำงานของโครงสร้างข้อมูลนี้แบบวนซ้ำดังต่อไปนี้: ^{[ 3 ]}

• ในระดับที่ง่ายที่สุด ผลลัพธ์ของฟังก์ชันแฮช เดี่ยว sที่แมปองค์ประกอบสตรีมqไปยัง {+1, -1} จะป้อนตัวนับขึ้น/ลงเดี่ยวCหลังจากผ่านข้อมูลหนึ่งรอบ ความถี่ขององค์ประกอบสตรีมqสามารถประมาณได้ แม้ว่าจะแย่มากก็ตาม โดยใช้ค่าที่คาดหวัง${\displaystyle n(q)}$${\displaystyle {\mathbf {E}}[C\cdot s(q)]}$
• วิธีที่ตรงไปตรงมาในการปรับปรุงความแปรปรวนของการประมาณค่าก่อนหน้านี้คือการใช้อาร์เรย์ของฟังก์ชันแฮชที่แตกต่างกันโดยแต่ละฟังก์ชันเชื่อมต่อกับตัวนับของตัวเองสำหรับแต่ละiเงื่อนไขยังคงใช้ได้ ดังนั้นการหาค่าเฉลี่ยใน ช่วง iจะทำให้การประมาณค่าแม่นยำยิ่งขึ้น${\displaystyle s_{i}}$${\displaystyle C_{i}}$${\displaystyle {\mathbf {E}}[C_{i}\cdot s_{i}(q)]=n(q)}$
• โครงสร้างก่อนหน้านี้ยังมีข้อบกพร่องสำคัญอยู่: หากองค์ประกอบเอาต์พุตที่มีความถี่ต่ำแต่ยังคงสำคัญaเกิดการชนกันของแฮชกับองค์ประกอบที่มีความถี่สูง แม้แต่เพียงแฮช เดียว การประมาณค่าก็อาจได้รับผลกระทบอย่างมาก การหลีกเลี่ยงปัญหานี้จำเป็นต้องลดความถี่ของการอัปเดตตัวนับการชนกันระหว่างองค์ประกอบที่แตกต่างกันสองตัวใดๆ ซึ่งทำได้โดยการแทนที่แต่ละตัวในโครงสร้างก่อนหน้านี้ด้วยอาร์เรย์ของ ตัวนับ mตัว (ทำให้ชุดตัวนับเป็นเมทริกซ์สองมิติ) โดยดัชนีjของตัวนับเฉพาะที่จะเพิ่ม/ลดค่าจะถูกเลือกผ่านชุดฟังก์ชันแฮชอีกชุดหนึ่งที่แมปองค์ประกอบqไปยังช่วง {1.. m } เนื่องจาก การหาค่าเฉลี่ยของค่า iทั้งหมดจึงใช้ได้ผล${\displaystyle s_{i}}$${\displaystyle n(a)}$${\displaystyle C_{i}}$${\displaystyle C_{i,j}}$${\displaystyle h_{i}}$${\displaystyle {\mathbf {E}}[C_{i,h_{i}(q)}\cdot s_{i}(q)]=n(q)}$

1. สำหรับค่าคงที่และ(ที่จะกำหนดในภายหลัง) ให้เลือกฟังก์ชันแฮชแบบสุ่ม และอย่างอิสระ โดยที่ และ จำเป็นอย่างยิ่งที่ตระกูลแฮชที่ เลือก และจะต้องเป็นอิสระต่อกันเป็นคู่ๆ ${\displaystyle w}$${\displaystyle t}$${\displaystyle d=2t+1}$${\displaystyle h_{1},\dots ,h_{d}}$${\displaystyle s_{1},\dots ,s_{d}}$${\displaystyle h_{i}:[n]\to [w]}$${\displaystyle s_{i}:[n]\to \{\pm 1\}}$${\displaystyle h_{i}}$${\displaystyle s_{i}}$

2. สำหรับแต่ละรายการในสตรีม ให้เพิ่มลงในบัคเก็ตที่ th ของแฮชที่ th ${\displaystyle q_{i}}$${\displaystyle s_{j}(q_{i})}$${\displaystyle h_{j}(q_{i})}$${\displaystyle j}$

เมื่อสิ้นสุดกระบวนการนี้ จะได้ผลรวมดังนี้ ${\displaystyle wd}$${\displaystyle (C_{ij})}$

${\displaystyle C_{i,j}=\sum _{h_{i}(k)=j}s_{i}(k).}$

ในการประมาณจำนวนของs นั้น จะคำนวณค่าต่อไปนี้: ${\displaystyle q}$

${\displaystyle r_{q}={\text{median}}_{i=1}^{d}\,s_{i}(q)\cdot C_{i,h_{i}(q)}.}$

ค่าเหล่านี้ เป็นค่าประมาณที่ไม่ลำเอียงว่า ปรากฏในสตรีม กี่ครั้ง${\displaystyle s_{i}(q)\cdot C_{i,h_{i}(q)}}$${\displaystyle q}$

การประมาณค่ามีความแปรปรวนโดยที่ คือความยาวของลำธารและคือ^{[ 7 ]}${\displaystyle r_{q}}$${\displaystyle O(\mathrm {min} \{m_{1}^{2}/w^{2},m_{2}^{2}/w\})}$${\displaystyle m_{1}}$${\displaystyle m_{2}^{2}}$${\displaystyle \sum _{q}(\sum _{i}[q_{i}=q])^{2}}$

นอกจากนี้ ยังรับประกันได้ว่าค่าที่ได้จะไม่ คลาดเคลื่อนจากค่าที่แท้จริงเกินกว่า ค่าที่คาดการณ์ไว้ ด้วยความน่าจะ เป็น ${\displaystyle r_{q}}$${\displaystyle 2m_{2}/{\sqrt {w}}}$${\displaystyle 1-e^{-O(t)}}$

อีกทางเลือกหนึ่ง Count-Sketch สามารถมองได้ว่าเป็นแผนที่เชิงเส้นที่มีฟังก์ชันการสร้างใหม่แบบไม่เชิงเส้น ให้เป็นชุดของเมทริกซ์ที่กำหนดโดย ${\displaystyle M^{(i\in [d])}\in \{-1,0,1\}^{w\times n}}$${\displaystyle d=2t+1}$

${\displaystyle M_{h_{i}(j),j}^{(i)}=s_{i}(j)}$

สำหรับและ 0 ในทุกที่อื่น ${\displaystyle j\in [w]}$

จากนั้น จึงวาดเวกเตอร์ โดยใช้ เพื่อสร้างใหม่เราใช้ซึ่งให้การรับประกันเช่นเดียวกับที่กล่าวไว้ข้างต้น หากเราใช้ และ${\displaystyle v\in \mathbb {R} ^{n}}$${\displaystyle C^{(i)}=M^{(i)}v\in \mathbb {R} ^{w}}$${\displaystyle v}$${\displaystyle v_{j}^{*}={\text{median}}_{i}C_{j}^{(i)}s_{i}(j)}$${\displaystyle m_{1}=\|v\|_{1}}$${\displaystyle m_{2}=\|v\|_{2}}$

การฉายภาพสเก็ตช์นับของผลคูณภายนอกของเวกเตอร์สองตัวเทียบเท่ากับการสังเคราะห์ (convolution)ของสเก็ตช์นับส่วนประกอบสองตัว

สเก็ตช์การนับจะคำนวณการสังเคราะห์ เวกเตอร์

${\displaystyle C^{(1)}x\ast C^{(2)}x^{T}}$โดยที่และเป็นเมทริกซ์การนับแบบร่างที่เป็นอิสระต่อกัน ${\displaystyle C^{(1)}}$${\displaystyle C^{(2)}}$

Pham และ Pagh ^{[ 8 ]} แสดงให้เห็นว่าสิ่งนี้เท่ากับ– ภาพสเก็ตช์นับของผลคูณภายนอกของเวกเตอร์ โดยที่แสดงถึง ผล คูณ Kronecker${\displaystyle C(x\otimes x^{T})}$${\displaystyle C}$${\displaystyle \otimes }$

การแปลงฟูริเยร์แบบเร็วสามารถใช้ในการคอนโวลูชันอย่างรวดเร็วของภาพร่างนับ โดยใช้ผลคูณการแบ่งหน้า^{[ 9 ] [ 10 ] [ 11 ]}โครงสร้างดังกล่าวสามารถคำนวณได้เร็วกว่าเมทริกซ์ปกติมาก

• Count–min sketchเป็นเวอร์ชันของอัลกอริธึมที่มีความต้องการหน่วยความจำน้อยกว่า (และมีการรับประกันความคลาดเคลื่อนที่น้อยกว่าเป็นข้อแลกเปลี่ยน)
• สเก็ตช์เทนเซอร์

• Charikar, Moses; Chen, Kevin; Farach-Colton, Martin (2004). "การค้นหารายการที่เกิดขึ้นบ่อยในสตรีมข้อมูล" (PDF) . วิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎี . 312 (1). Elsevier BV: 3– 15. doi : 10.1016/s0304-3975(03)00400-6 . ISSN  0304-3975 .
• Faisal M. Algashaam; Kien Nguyen; Mohamed Alkanhal; Vinod Chandran; Wageeh Boles. "การจำแนกประเภทบริเวณรอบดวงตาแบบหลายสเปกตรัมด้วยการรวมเชิงเส้นหลายรูปแบบขนาดกะทัดรัดแบบหลายโมดอล" [1] . IEEE Access , Vol. 5. 2017.
• Ahle, Thomas; Knudsen, Jakob (2019-09-03). "Almost Optimal Tensor Sketch" . ResearchGate . สืบค้นเมื่อ2020-07-11 .