Loading...

Parallel Implementation of Peter-Clark (PC)Algorithm for Causal Structure Learning

Zarebavani, Behrooz | 2019

2921 Viewed
  1. Type of Document: M.Sc. Thesis
  2. Language: Farsi
  3. Document No: 52404 (05)
  4. University: Sharif University of Technology
  5. Department: Electrical Engineering
  6. Advisor(s): Hashemi, Matin; Salehkaleybar, Saber
  7. Abstract:
  8. The main goal in many fields in the empirical sciences is to discover causal relationships among a set of variables from observational data. PC algorithm is one of the promising solutions to learn underlying causal structure by performing a number of conditional independence tests. In this paper, we propose a novel GPU-based parallel algorithm, called cuPC, to execute an order-independent version of PC. The proposed solution has two variants, cuPC-E and cuPC-S, which parallelize PC in two different ways for multivariate normal distribution. Experimental results show the scalability of the proposed algorithms with respect to the number of variables, the number of samples, and different graph densities. For instance, in one of the most challenging datasets, the runtime is reduced from more than 11 hours to about 4 seconds. On average, cuPC-E and cuPC-S achieve 500 X and 1300 X speedup, respectively, compared to serial implementation on CPU. The source code of cuPC is available online [1]
  9. Keywords:
  10. Peter-Clark Algorithm ; Hardware Implementation ; Bayesian Learning ; Causal Structure ; Computed Unified Device Architecture (CUDA)Framework ; Graphics Procssing Unit (GPU) ; Machine Learning ; Parallel Processing

 Digital Object List

 Bookmark

  • فهرست اختصارات
  • مقدمه
    • نیاز به CausalStruct
    • الگوریتم‌های یادگیری CausalStruct
    • کار‌های مشابه
    • نوآوری‌های پایان‌نامه
    • ساختار پایان‌نامه
  • شبکه های بیزین
    • مقدمه
    • شبکه بیز
    • یک دید اولیه
    • تصویر استقلال
      • ارتباط بین تصویر استقلال و تبدیل توزیع به ضرب توزیع‌ها
      • بدست آوردن استقلال از گراف شبکه بیزین
    • کلاس هم‌ارزی Markov
    • نتیجه‌گیری
  • الگوریتم GES
    • مقدمه
    • الگوریتم GES
    • نحوه‌ی امتیاز‌دهی بیزین
    • ترتیب کلی فاز‌ها
    • فاز رو به جلو
    • فاز رو به عقب
    • ‌افزایش سرعت و موازی‌ سازی GES
  • الگوریتم PC
    • مقدمه
    • SGS
    • PC
    • PC-stable
    • نتیجه‌گیری
  • cuPC
    • مقدمه
    • چارچوب CUDA
    • سطح صفر
    • سطوح یک به بعد: الگوریتم cuPC-E
    • سطوح یک به بعد: الگوریتم cuPC-S
    • جزئیات بیشتر
      • حذف ریسه‌ها‌ی غیر ضروری
      • محاسبه ترکیب‌های ممکن به صورت موازی
      • تست استقلال
      • PInverse
  • آزمایشات و تجزیه و تحلیل داده‌ها
    • کد پیاده‌سازی الگوریتم‌ها
    • محیط آزمایش
    • مقایسه توانایی الگوریتم‌ها
    • تنظیم پارامتر‌ها
    • اشتراک محلی نسبت به اشتراک کلی
    • توانایی مقیاس پذیری
  • نتیجه‌گیری و پیشنهادات
  • واژه نامه انگلیسی به فارسی
  • واژه نامه فارسی به انگلیسی
...see more