การรวบรวมผลรวมของ einstein อย่างเหมาะสมที่สุด

Aug 18 2020

Einstein summation เป็นวิธีที่สะดวกในการแสดงการทำงานของเทนเซอร์ซึ่งพบในไลบรารีเทนเซอร์เช่น numpy, torch, tensorflow เป็นต้น

ความยืดหยุ่นช่วยให้เราแสดงผลคูณของเมทริกซ์สามตัว $X$, $Y$, $Z$ ของขนาด $(a,b)$, $(b,c)$, $(c,d)$ เช่น

X.Y.Z = einsum('ab,bc,cd->ad',X,Y,Z)

อย่างไรก็ตามข้างต้นรวบรวมสิ่งที่ต้องการ

for a_ in range(a):
  for d_ in range(d):
     res[a_,d_] = 0
     for b_ in range(b):
        for c_ in range(c):
           res[a_,d_] += X[a_,b_] * Y[b_,c_] * Z[c_, d_]

เนทีฟนี้เป็นกำลังสองในขนาดของเมทริกซ์เมื่อเพียงแค่ทำ

einsum('ac,cd->ad',einsum('ab,bc'->'ac', X, Y), Z)

จะเป็นเพียงลูกบาศก์

มีประมาณสามระดับของการเพิ่มประสิทธิภาพที่เราสามารถจินตนาการการใช้งานอย่างชาญฉลาดของeinsumการดำเนินการ

  1. ย่อยสลาย einsum ของเทนเซอร์ $(x_1, \ldots, x_n)$ เป็น einsum คู่ของเทนเซอร์ $x_1, x_2$, $e(x_1, x_2), x_3$ฯลฯ เพื่อเพิ่มประสิทธิภาพเวลาในการคำนวณ

  2. อาศัยการเชื่อมโยง (ถ้ามี) เพื่อเลือกคู่เหล่านั้นอย่างรอบคอบ (นี่เป็นปัญหาการเขียนโปรแกรมไดนามิกแบบคลาสสิก) และสร้างเทนเซอร์ตัวกลางที่เหมาะสม

  3. ค้นพบสูตรที่คล้าย Strassen สำหรับการคำนวณเทนเซอร์เฉพาะ

ในขณะที่ 3 ดูเหมือนไม่สามารถเข้าถึงได้อย่างชัดเจน แต่ 1 และ 2 ดูเหมือนว่าพวกเขาสามารถทำได้ด้วยอัลกอริทึมที่ตรงไปตรงมา อัลกอริทึมดังกล่าวเป็นที่รู้จักสำหรับการสรุปผลแบบไอน์สไตน์ทั่วไปหรือไม่? พวกเขาได้รับการศึกษา?

คำตอบ

2 smapers Aug 19 2020 at 16:33

ดูเหมือนว่าปัญหาทั่วไปในการค้นหาลำดับการหดตัวที่เหมาะสมที่สุดคือ NP-hard [1] เอกสารล่าสุดเกี่ยวกับการเพิ่มประสิทธิภาพลำดับการหดตัวและมีการอ้างอิงที่เกี่ยวข้องคือ [2]

[1] Chi-Chung, Lam, P. Sadayappan และ Rephael Wenger "เกี่ยวกับการเพิ่มประสิทธิภาพคลาสของลูปหลายมิติด้วยการลดลงสำหรับการดำเนินการแบบขนาน" Parallel Processing Letters 7.02 (1997): 157-168.

[2] Schindler, Frank และ Adam Jermyn "อัลกอริทึมสำหรับการสั่งซื้อการหดตัวของเครือข่ายเทนเซอร์" การเรียนรู้ของเครื่อง: วิทยาศาสตร์และเทคโนโลยี (2020).