Options
Prof. Dr.
Wrobel, Stefan
Now showing
1  10 of 11

PublicationLearning Weakly Convex Sets in Metric Spaces( 20210910)
;StadtlÃ¤nder, EikeWe introduce the notion of weak convexity in metric spaces, a generalization of ordinary convexity commonly used in machine learning. It is shown that weakly convex sets can be characterized by a closure operator and have a unique decomposition into a set of pairwise disjoint connected blocks. We give two generic efficient algorithms, an extensional and an intensional one for learning weakly convex concepts and study their formal properties. Our experimental results concerning vertex classification clearly demonstrate the excellent predictive performance of the extensional algorithm. Two nontrivial applications of the intensional algorithm to polynomial PAClearnability are presented. The first one deals with learning kconvex Boolean functions, which are already known to be efficiently PAClearnable. It is shown how to derive this positive result in a fairly easy way by the generic intensional algorithm. The second one is concerned with the Euclidean space equipped with the Manhattan distance. For this metric space, weakly convex sets form a union of pairwise disjoint axisaligned hyperrectangles. We show that a weakly convex set that is consistent with a set of examples and contains a minimum number of hyperrectangles can be found in polynomial time. In contrast, this problem is known to be NPcomplete if the hyperrectangles may be overlapping. 
PublicationMaximum Margin Separations in Finite Closure Systems( 2021)
;Seiffahrt, FlorianMonotone linkage functions provide a measure for proximities between elements and subsets of a ground set. Combining this notion with Vapniks idea of support vector machines, we extend the concepts of maximal closed set and halfspace separation in finite closure systems to those with maximum margin. In particular, we define the notion of margin for finite closure systems by means of monotone linkage functions and give a greedy algorithm computing a maximum margin closed set separation for two sets efficiently. The output closed sets are maximum margin halfspaces, i.e., form a partitioning of the ground set if the closure system is Kakutani. We have empirically evaluated our approach on different synthetic datasets. In addition to binary classification of finite subsets of the Euclidean space, we considered also the problem of vertex classification in graphs. Our experimental results provide clear evidence that maximal closed set separation with maximum margin results in a much better predictive performance than that with arbitrary maximal closed sets. 
PublicationMaximal Closed Set and HalfSpace Separations in Finite Closure Systems( 2020)
;Seiffarth, FlorianMotivated by various binary classification problems in structured data (e.g., graphs or other relational and algebraic structures), we investigate some algorithmic properties of closed set and halfspace separation in abstract closure systems. Assuming that the underlying closure system is finite and given by the corresponding closure operator, we formulate some negative and positive complexity results for these two separation problems. In particular, we prove that deciding halfspace separability in abstract closure systems is NPcomplete in general. On the other hand, for the relaxed problem of maximal closed set separation we propose a simple greedy algorithm and show that it is efficient and has the best possible lower bound on the number of closure operator calls. As a second direction to overcome the negative result above, we consider Kakutani closure systems and show first that our greedy algorithm provides an algorithmic characterization of this kind of set systems. As one of the major potential application fields, we then focus on Kakutani closure systems over graphs and generalize a fundamental characterization result based on the Pasch axiom to graph structure partitioning of finite sets. Though the primary focus of this work is on the generality of the results obtained, we experimentally demonstrate the practical usefulness of our approach on vertex classification in different graph datasets. 
PublicationSupport Estimation in Frequent Itemset Mining by Locality Sensitive Hashing( 2019)The main computational effort in generating all frequent itemsets in a transactional database is in the step of deciding whether an itemset is frequent, or not. We present a method for estimating itemset supports with twosided error. In a preprocessing step our algorithm first partitions the database into groups of similar transactions by using locality sensitive hashing and calculates a summary for each of these groups. The support of a query itemset is then estimated by means of these summaries. Our preliminary empirical results indicate that the proposed method results in a speedup of up to a factor of 50 on large datasets. The Fmeasure of the output patterns varies between 0.83 and 0.99.

PublicationMining Tree Patterns with Partially Injective Homomorphisms( 2019)
;Schulz, Till Hendrik ;Welke, PascalOne of the main differences between inductive logic programming (ILP) and graph mining lies in the pattern matching operator applied: While it is mainly defined by relational homomorphism (i.e., subsumption) in ILP, subgraph isomorphism is the most common pattern matching operator in graph mining. Using the fact that subgraph isomorphisms are injective homomorphisms, we bridge the gap between ILP and graph mining by considering a natural transition from homomorphisms to subgraph isomorphisms that is defined by partially injective homomorphisms, i.e., which require injectivity only for subsets of the vertex pairs in the pattern. Utilizing positive complexity results on deciding homomorphisms from bounded treewidth graphs, we present an algorithm mining frequent trees from arbitrary graphs w.r.t. partially injective homomorphisms. Our experimental results show that the predictive performance of the patterns obtained is comparable to that of ordinary frequent subgraphs. Thus, by preserving much from the advantageous properties of homomorphisms and subgraph isomorphisms, our approach provides a tradeoff between efficiency and predictive power. 
PublicationA logicbased approach to relation extraction from texts( 2010)
;PaaÃŸ, Gerhard ;Reichartz, F.In recent years, text mining has moved far beyond the classical problem of text classification with an increased interest in more sophisticated processing of large text corpora, such as, for example, evaluations of complex queries. This and several other tasks are based on the essential step of relation extraction. This problem becomes a typical application of learning logic programs by considering the dependency trees of sentences as relational structures and examples of the target relation as ground atoms of a target predicate. In this way, each example is represented by a definite firstorder Hornclause. We show that an adaptation of Plotkin's least general generalization (LGG) operator can effectively be applied to such clauses and propose a simple and effective divideandconquer algorithm for listing a certain set of LGGs. We use these LGGs to generate binary features and compute the hypothesis by applying SVM to the feature vectors obtained. Empirical results on the ACE2003 benchmark dataset indicate that the performance of our approach is comparable to stateoftheart kernel methods. 

PublicationEfficient closed pattern mining in strongly accessible set systems( 2007)
;PoignÃ©, Axel 

PublicationA refinement operator for outerplanar graphs( 2006)
;Akutsu, T.Outerplanar graphs form a practically relevant class of graphs which appear efficiently computable bottomup refinement operator for tenuous outerplanar graphs defined by combining techniques from firstorder learning, algebraic graph theory, and combinatorial pattern matching. Since the coverage test for outerplanar graphs is decidable in polynomial time, our results can be used to develop practical algorithms for bottomup induction of tenuous outerplanar graph patterns.