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: Grafikler, Tümevarımsal öğrenme, Veri madenciliği, Verimlilik, Graphics, Inductive learning, Data mining, Productivity
- 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ı: Belirtilmemiş.
Ö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
- Improving efficiency, productivity, and scalability in FFF 3D printing systems by using deep reinforcement learning
Derin pekiştirmeli öğrenme ile FFF 3D yazıcı sistemlerinde verimlilik, üretkenlik ve ölçeklenebilirliğin iyileştirilmesi
AHMED MERZE
Doktora
İngilizce
2026
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAnkara Yıldırım Beyazıt ÜniversitesiBilgisayar Ana Bilim Dalı
PROF. DR. FATİH VEHBİ ÇELEBİ
- Novel methods for fast and accurate solutions of electromagnetic integral equations
Elektromanyetik integral denklemlerin hızlı ve doğru çözümleri için yeni yöntemler
ENES KOÇ
Yüksek Lisans
İngilizce
2025
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik ve Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. VAKUR BEHÇET ERTÜRK
DR. MERT KALFA
- Privacy and security enhancements of federated learning
Federe öğrenme uygulamalarında mahremiyet ve güvenlik geliştirmeleri
ŞÜKRÜ ERDAL
Yüksek Lisans
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilişim Uygulamaları Ana Bilim Dalı
PROF. DR. ENVER ÖZDEMİR
DR. FERHAT KARAKOÇ
- Design and implementation of UW-based collision avoidance system for underground mines
Yeraltı maden ocakları için UWB tabanlı çarpışma önleme sistemi tasarımı ve uygulanması
MURAT İSMAİL KÜÇÜKYILMAZ
Yüksek Lisans
İngilizce
2024
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. ECE OLCAY GÜNEŞ
- High-temperature pyrolysis of sewage sludge: Synergistic effects of co-pyrolysis with rice straw and composite plastic wastes
Atık su arıtma çamurunun yüksek sıcaklık pirolizi: Çeltik sapı ve kompozit plastik atıklar ile birlikte pirolizin sinerjik etkileri
ELİF BABAYİĞİT
Doktora
İngilizce
2025
Kimya Mühendisliğiİstanbul Teknik ÜniversitesiÇevre Mühendisliği Ana Bilim Dalı
PROF. DR. EMİNE ÇOKGÖR
PROF. DR. ALPER SARIOĞLAN