Datum
2019Autor
Hanika, TomSchlagwort
004 Informatik Bipartiter GraphFormale BegriffsanalyseKünstliche IntelligenzWissensextraktionSoziales NetzwerkMaschinelles LernenExplorationMetadata
Zur Langanzeige
Dissertation
Discovering Knowledge in Bipartite Graphs with Formal Concept Analysis
Zusammenfassung
Since the 1970s knowledge based approaches are a crucial part of artificial intelligence (AI) research. In this work we investigate data sets in the form of bipartite graphs, i.e., graphs where a bipartition of the vertex set respecting the edge set can be found, for knowledge. To this end we first relate those bipartite graphs to the structure formal context, as used in formal concept analysis (FCA). This link enables us to employ the whole tool-set of FCA to bipartite graphs and therefore, notably, to bipartite social networks. In particular, notions for formal concepts, orderings of those, and implicational bases. All these then can be considered as aspects of knowledge in bipartite graphs. For the most part of our work we focus
on implicational knowledge and how to compute all valid implications in a bipartite graph, also called theory. The common approach here is to compute a minimal basis of implications due to the possibly exponential size of the theory.
Although our approach is mathematically elegant, it opened an immense number of a computational problems. First of all the size of common data sets is to large for classical algorithms from FCA. We overcome this limitation in our work by employing ideas from probably approximately correct (PAC) learning. This led to the development of PAC implicational bases. Furthermore, we developed a PAC exploration method, based on the attribute exploration algorithm, which is able to compute a basis of implications for implicit data sets in a PAC fashion. In experiments on PAC bases we encountered a dependency on the distribution of data in high dimensional attribute space. In order to express this observation in terms of a measure we developed a novel approach for measuring the intrinsic dimension of a data set. The goal here was to incorporate the particular set of features employed by a machine learning or knowledge procedure, like formal concepts, into the measure.
In the later part of our work we point our attention to the order structures in bipartite social networks. We provide a first notion for individuality in social networks and clones, i.e., exchangeable vertices with respect to the concept structure. Finally, we show how to employ a social network of (local) domain experts to conduct a collaborative attribute exploration, and conclude our work by pointing out different tasks and applications as well as possible next steps.
on implicational knowledge and how to compute all valid implications in a bipartite graph, also called theory. The common approach here is to compute a minimal basis of implications due to the possibly exponential size of the theory.
Although our approach is mathematically elegant, it opened an immense number of a computational problems. First of all the size of common data sets is to large for classical algorithms from FCA. We overcome this limitation in our work by employing ideas from probably approximately correct (PAC) learning. This led to the development of PAC implicational bases. Furthermore, we developed a PAC exploration method, based on the attribute exploration algorithm, which is able to compute a basis of implications for implicit data sets in a PAC fashion. In experiments on PAC bases we encountered a dependency on the distribution of data in high dimensional attribute space. In order to express this observation in terms of a measure we developed a novel approach for measuring the intrinsic dimension of a data set. The goal here was to incorporate the particular set of features employed by a machine learning or knowledge procedure, like formal concepts, into the measure.
In the later part of our work we point our attention to the order structures in bipartite social networks. We provide a first notion for individuality in social networks and clones, i.e., exchangeable vertices with respect to the concept structure. Finally, we show how to employ a social network of (local) domain experts to conduct a collaborative attribute exploration, and conclude our work by pointing out different tasks and applications as well as possible next steps.
Förderhinweis
Supported by BMBF: 16FWN016Zitieren
@phdthesis{doi:10.17170/kobra-20190213189,
author={Hanika, Tom},
title={Discovering Knowledge in Bipartite Graphs with Formal Concept Analysis},
school={Kassel, Universität Kassel, Fachbereich Elektrotechnik / Informatik},
year={2019}
}
0500 Oax 0501 Text $btxt$2rdacontent 0502 Computermedien $bc$2rdacarrier 1100 2019$n2019 1500 1/eng 2050 ##0##http://hdl.handle.net/123456789/11077 3000 Hanika, Tom 4000 Discovering Knowledge in Bipartite Graphs with Formal Concept Analysis / Hanika, Tom 4030 4060 Online-Ressource 4085 ##0##=u http://nbn-resolving.de/http://hdl.handle.net/123456789/11077=x R 4204 \$dDissertation 4170 5550 {{Bipartiter Graph}} 5550 {{Formale Begriffsanalyse}} 5550 {{Künstliche Intelligenz}} 5550 {{Wissensextraktion}} 5550 {{Soziales Netzwerk}} 5550 {{Maschinelles Lernen}} 5550 {{Exploration}} 7136 ##0##http://hdl.handle.net/123456789/11077
2019-02-19T14:19:15Z 2019-02-19T14:19:15Z 2019 doi:10.17170/kobra-20190213189 http://hdl.handle.net/123456789/11077 Supported by BMBF: 16FWN016 eng Namensnennung-NichtKommerziell-KeineBearbeitung 3.0 Deutschland http://creativecommons.org/licenses/by-nc-nd/3.0/de/ Bipartite Graphs Formal Concept Analysis Implications Cliques Conceptual Knowledge Artificial Intelligence Knowledge Discovery Social Network Analysis SNA Conceptual Structures Probably Approximately Correct Machine Learning Exploration 004 Discovering Knowledge in Bipartite Graphs with Formal Concept Analysis Dissertation Since the 1970s knowledge based approaches are a crucial part of artificial intelligence (AI) research. In this work we investigate data sets in the form of bipartite graphs, i.e., graphs where a bipartition of the vertex set respecting the edge set can be found, for knowledge. To this end we first relate those bipartite graphs to the structure formal context, as used in formal concept analysis (FCA). This link enables us to employ the whole tool-set of FCA to bipartite graphs and therefore, notably, to bipartite social networks. In particular, notions for formal concepts, orderings of those, and implicational bases. All these then can be considered as aspects of knowledge in bipartite graphs. For the most part of our work we focus on implicational knowledge and how to compute all valid implications in a bipartite graph, also called theory. The common approach here is to compute a minimal basis of implications due to the possibly exponential size of the theory. Although our approach is mathematically elegant, it opened an immense number of a computational problems. First of all the size of common data sets is to large for classical algorithms from FCA. We overcome this limitation in our work by employing ideas from probably approximately correct (PAC) learning. This led to the development of PAC implicational bases. Furthermore, we developed a PAC exploration method, based on the attribute exploration algorithm, which is able to compute a basis of implications for implicit data sets in a PAC fashion. In experiments on PAC bases we encountered a dependency on the distribution of data in high dimensional attribute space. In order to express this observation in terms of a measure we developed a novel approach for measuring the intrinsic dimension of a data set. The goal here was to incorporate the particular set of features employed by a machine learning or knowledge procedure, like formal concepts, into the measure. In the later part of our work we point our attention to the order structures in bipartite social networks. We provide a first notion for individuality in social networks and clones, i.e., exchangeable vertices with respect to the concept structure. Finally, we show how to employ a social network of (local) domain experts to conduct a collaborative attribute exploration, and conclude our work by pointing out different tasks and applications as well as possible next steps. open access Hanika, Tom 2019-01-31 xii, 219 Seiten Kassel, Universität Kassel, Fachbereich Elektrotechnik / Informatik Stumme, Gerd (Prof. Dr.) Ganter, Bernhard (Prof. Dr.) Bipartiter Graph Formale Begriffsanalyse Künstliche Intelligenz Wissensextraktion Soziales Netzwerk Maschinelles Lernen Exploration publishedVersion
Die folgenden Lizenzbestimmungen sind mit dieser Ressource verbunden: