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ı
- Tez No: 338355
- Danışmanlar: DOÇ. DR. PINAR KARAGÖZ
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2013
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- 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
- 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
2024
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ÖZGÜR KABAK
DR. ÖĞR. ÜYESİ İNCİ ÇAĞLAYAN
- Micro-architectural support for improving synchronization and efficiency of SIMD execution on GPUs
Başlık çevirisi yok
AYŞE YILMAZER
Doktora
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolNortheastern UniversityPROF. DAVID KAELI
- 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
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolHacettepe ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. AYÇA KOLUKISA
DR. ÖĞR. ÜYESİ OUMOUT CHOUSEIN OGLOU
- 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
2024
Tekstil ve Tekstil Mühendisliğiİstanbul Teknik ÜniversitesiTekstil Mühendisliği Ana Bilim Dalı
PROF. DR. ALİ DEMİR
- Techniques for efficient execution of large-scale scientific workflows in distributed environments
Başlık çevirisi yok
SELİM KALAYCI
Doktora
İngilizce
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolFlorida International UniversityBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
PROF. S. MASOUD SADJADI