Geri Dön

Improving scalability and efficiency of ILP-based and graph-based concept discovery systems

Tümevaran mantık programlama tabanlı ve çizge tabanlı kavram keşif sistemlerinin ölçeklendirilebilirlik ve veriminin artırılması

  1. Tez No: 338355
  2. Yazar: ALEV MUTLU
  3. Danışmanlar: DOÇ. DR. PINAR KARAGÖZ
  4. Tez Türü: Doktora
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2013
  8. Dil: İngilizce
  9. Üniversite: Orta Doğu Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 114

Özet

Kavram keşfi, bir ilişki tanımının arkaplan ilişlileri olarak adlındırılan diğeri bazı ilişkiler cinsinden bulunması problemidir. Kavram keşif probleminde Tümevaran Mantık Programlama (TMP) ve çizge tabanlı yöntemler yoğun olarak kullanılmaktadır.TMP tabanlı yaklaşımlar bu problemde uzun süredir hakim bir şekilde kullanılıyor olsa da, bu tür sistemlerin bazı problemlerini çözdüğü için çizge tabanlı yaklaşılar da son zamanlarda bu alanda popülarite kazanmıştır.Birçok alanda uygulaması bulunmakla birlikte, TMP tabanlı sistemlerde verimililik ve ölçeklendirilebilirlik sorunları mevcuttur. Bu sorunlar genellikle TMP tabanlı sistemlerin oluşturduğu büyük arama alanlarından kaynaklanmaktadır. Bu çalışmada, tablolama ve paralleleştirme yöntemleri kullanılarak TMP tabanlı kavram keşif sistemlerinin arama alanı oluşturma ve değerlendirme aşamalarının iyileştirilmesi için yöntemler sunulmaktadır.Bu çalışmada tablolama yöntemlerini kullanan üç yöntem sunulmuştur, Tabular CRIS, Tabular CRIS-wEF ve Selective Tabular CRIS. Bu metotlarda, temel olarak, arama alanı değerlendirme sorguları daha sonra kullanılmak üzere tablolanmaktadır. Her üç metot bazı ortak temel fonksiyonları barındırmakla birlikte, ardıl gelen öncekinin ölçeklendirilebilirliğini iyileştirmek için bazı yeni yaklaşımlar sunmaktadır.Önerilen paralel yöntem, pCRIS, TMP tabanlı sistemlerin arama alanı oluşturma ve değerlendirme aşamalarını veri-paralel yöntemler kullanılarak paralelleştirmektedir. Önerilen yöntem fazladan yapılan işi ve senkronizayon anlarında işlemcilerin bekleme süresini asgari düzeyde tutacak şekilde tasarlanmıştır.Çizge tabanlı sistemler öncelikle TMP tabanlı sistemlerin problemlerinden biri olan yerel plato problemini gidermek için sunulmuştur. Veriyi etkin bir şekilde ifade edebildiği ve TMP tabanlı sistemlerin bazı problemerini ortadan kaldırdıgı için yakın zamanlarda, kavram keşfi probleminde, çizge tabanlı sistemler artan bir popülarite kazanmaktadır. Genel olarak bu tür sistemler ortak bileşen bulma ve yol bulma sistemleri olarak gruplandırılabilir. İlk kümeye düşen yöntemler ortak bileşenleri bulmak pahalı algoritmalar kullanmaktadır. İkinci kümeye düşen yaklaşımlar ise çizge içideki yolları tumak için komplike indeksleme yöntemlerine ihityaç duymaktadır. Bu çalışmada çizge tabanlı kavram keşif sistemleri için pahalı bileşen bulma algoritmalarına ve komplike indeksleme mekanizmalarına ihtiyaç duymayan melez bir yöntem sunulmaktadır. Önerilen yöntemde bezer yapılar gruplanmakta ve kavram tanımlarını oluşturan yollar çizge inşaa edilirken oluşturulmaktadır.

Özet (Çeviri)

Concept discovery is the problem of finding definitions of target relation in terms or other relation given as a background knowledge. Inductive Logic Programming (ILP)-based and graph-based approaches are two competitors in concept discovery problem. Although ILP-based systems have long dominated the area, graph-based systems have recently gained popularity as they overcome certain shortcomings of ILP-based systems.While having applications in numerous domains, ILP-based concept discovery systems still sustain scalability and efficiency issues. These issues generally arose due to the large search spaces such systems build. In this work we propose memoization-based and parallelization-based methods that modify the search space construction step and the evaluation step of ILP-based concept discovery systems to overcome these problem.In this work we propose three memoization-based methods, called Tabular CRIS, Tabular CRIS-wEF, and Selective Tabular CRIS. In these methods, basically, evaluation queries are stored in look-up tables for later uses. While preserving some core functions in common, each proposed method improves efficiency and scalability of its predecessor by introducing constraints on what kind of evaluation queries to store in look-up tables and for how long.The proposed parallelization method, called pCRIS, parallelizes the search space construction and evaluation steps of ILP-based concept discovery systems in a data-parallel manner. The proposed method introduces policies to minimize the redundant work and waiting time among the workers at synchronization points.Graph-based approaches were first introduced to the concept discovery domain to handle the so called local plateau problem. Graph-based approaches have recently gained more popularity in concept discovery system as they provide convenient environment to represent relational data and are able to overcome certain shortcomings of ILP-based concept discovery systems. Graph-based approaches can be classified as structure-based approaches and path-finding approaches. The first class of approaches need to employ expensive algorithms such as graph isomorphism to find frequently appearing substructures. The methods that fall into the second class need to employ sophisticated indexing mechanisms to find out the frequently appearing paths that connect some nodes in interest. In this work, we also propose a hybrid method for graph-based concept discovery which does not require costly substructure matching algorithms and path indexing mechanism. The proposed method builds the graph in such a way that similar facts are grouped together and paths that eventually turn to be concept descriptors are build while the graph is constructed.

Benzer Tezler

  1. Comprehensive risk mapping and fire station optimization for forest fire management: An application in Antalya

    Orman yangını yönetimi için kapsamlı risk haritalama ve yangın istasyonu optimizasyonu: Antalya uygulaması

    ZÜHAL ÖZCAN YAVUZ

    Doktora

    İngilizce

    İngilizce

    2024

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. ÖZGÜR KABAK

    DR. ÖĞR. ÜYESİ İNCİ ÇAĞLAYAN

  2. A decision support system for software architecture decision making

    Yazılım mimarisine karar verme için bir karar destek sistemi

    MERVE ÖZDEŞ DEMİR

    Doktora

    İngilizce

    İngilizce

    2024

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolHacettepe Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. AYÇA KOLUKISA

    DR. ÖĞR. ÜYESİ OUMOUT CHOUSEIN OGLOU

  3. Enerji depolamada yenilikçi karbon yapılı esnek yüzeylerin üretimi ve analizi

    Production and analysis of novel carbon structured flexible surfaces for energy storage applications

    ESRA ŞERİFE KILIÇ

    Doktora

    Türkçe

    Türkçe

    2024

    Tekstil ve Tekstil Mühendisliğiİstanbul Teknik Üniversitesi

    Tekstil Mühendisliği Ana Bilim Dalı

    PROF. DR. ALİ DEMİR

  4. Techniques for efficient execution of large-scale scientific workflows in distributed environments

    Başlık çevirisi yok

    SELİM KALAYCI

    Doktora

    İngilizce

    İngilizce

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolFlorida International University

    Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı

    PROF. S. MASOUD SADJADI