The Experts below are selected from a list of 6120 Experts worldwide ranked by ideXlab platform
Pauli Miettinen - One of the best experts on this subject based on the ideXlab platform.
-
Recent Developments in Boolean Matrix Factorization
arXiv: Learning, 2020Co-Authors: Pauli Miettinen, Stefan NeumannAbstract:The goal of Boolean Matrix Factorization (BMF) is to approximate a given binary Matrix as the product of two low-rank binary factor matrices, where the product of the factor matrices is computed under the Boolean algebra. While the problem is computationally hard, it is also attractive because the binary nature of the factor matrices makes them highly interpretable. In the last decade, BMF has received a considerable amount of attention in the data mining and formal concept analysis communities and, more recently, the machine learning and the theory communities also started studying BMF. In this survey, we give a concise summary of the efforts of all of these communities and raise some open questions which in our opinion require further investigation.
-
Biclustering and Boolean Matrix Factorization in Data Streams
arXiv: Learning, 2020Co-Authors: Stefan Neumann, Pauli MiettinenAbstract:We study the clustering of bipartite graphs and Boolean Matrix factorization in data streams. We consider a streaming setting in which the vertices from the left side of the graph arrive one by one together with all of their incident edges. We provide an algorithm that, after one pass over the stream, recovers the set of clusters on the right side of the graph using sublinear space; to the best of our knowledge, this is the first algorithm with this property. We also show that after a second pass over the stream, the left clusters of the bipartite graph can be recovered and we show how to extend our algorithm to solve the Boolean Matrix factorization problem (by exploiting the correspondence of Boolean matrices and bipartite graphs). We evaluate an implementation of the algorithm on synthetic data and on real-world data. On real-world datasets the algorithm is orders of magnitudes faster than a static baseline algorithm while providing quality results within a factor 2 of the baseline algorithm. Our algorithm scales linearly in the number of edges in the graph. Finally, we analyze the algorithm theoretically and provide sufficient conditions under which the algorithm recovers a set of planted clusters under a standard random graph model.
-
Boolean Matrix factorization meets consecutive ones property
Proceedings of the 2019 SIAM International Conference on Data Mining, 2019Co-Authors: Nikolaj Tatti, Pauli MiettinenAbstract:Boolean Matrix factorization is a natural and a popular technique for summarizing binary matrices. In this paper, we study a problem of Boolean Matrix factorization where we additionally require that the factor matrices have consecutive ones property (OBMF). A major application of this optimization problem comes from graph visualization: standard techniques for visualizing graphs are circular or linear layout, where nodes are ordered in circle or on a line. A common problem with visualizing graphs is clutter due to too many edges. The standard approach to deal with this is to bundle edges together and represent them as ribbon. We also show that we can use OBMF for edge bundling combined with circular or linear layout techniques. We demonstrate that not only this problem is NP-hard but we cannot have a polynomial-time algorithm that yields a multiplicative approximation guarantee (unless P = NP). On the positive side, we develop a greedy algorithm where at each step we look for the best 1-rank factorization. Since even obtaining 1-rank factorization is NP-hard, we propose an iterative algorithm where we fix one side and and find the other, reverse the roles, and repeat. We show that this step can be done in linear time using pq-trees. We also extend the problem to cyclic ones property and symmetric factorizations. Our experiments show that our algorithms find high-quality factorizations and scale well.
-
mdl4bmf minimum description length for Boolean Matrix factorization
ACM Transactions on Knowledge Discovery From Data, 2014Co-Authors: Pauli Miettinen, Jilles VreekenAbstract:Matrix factorizations—where a given data Matrix is approximated by a product of two or more factor matrices—are powerful data mining tools. Among other tasks, Matrix factorizations are often used to separate global structure from noise. This, however, requires solving the “model order selection problem” of determining the proper rank of the factorization, that is, to answer where fine-grained structure stops, and where noise starts. Boolean Matrix Factorization (BMF)—where data, factors, and Matrix product are Boolean—has in recent years received increased attention from the data mining community. The technique has desirable properties, such as high interpretability and natural sparsity. Yet, so far no method for selecting the correct model order for BMF has been available. In this article, we propose the use of the Minimum Description Length (MDL) principle for this task. Besides solving the problem, this well-founded approach has numerous benefits; for example, it is automatic, does not require a likelihood function, is fast, and, as experiments show, is highly accurate. We formulate the description length function for BMF in general—making it applicable for any BMF algorithm. We discuss how to construct an appropriate encoding: starting from a simple and intuitive approach, we arrive at a highly efficient data-to-model--based encoding for BMF. We extend an existing algorithm for BMF to use MDL to identify the best Boolean Matrix factorization, analyze the complexity of the problem, and perform an extensive experimental evaluation to study its behavior.
-
dynamic Boolean Matrix factorizations
International Conference on Data Mining, 2012Co-Authors: Pauli MiettinenAbstract:Boolean Matrix factorization is a method to decompose a binary Matrix into two binary factor matrices. Akin to other Matrix factorizations, the factor matrices can be used for various data analysis tasks. Many (if not most) real-world data sets are dynamic, though, meaning that new information is recorded over time. Incorporating this new information into the factorization can require a re-computation of the factorization -- something we cannot do if we want to keep our factorization up-to-date after each update. This paper proposes a method to dynamically update the Boolean Matrix factorization when new data is added to the data base. This method is extended with a mechanism to improve the factorization with a trade-off in speed of computation. The method is tested with a number of real-world and synthetic data sets including studying its efficiency against off-line methods. The results show that with good initialization the proposed online and dynamic methods can beat the state-of-the-art offline Boolean Matrix factorization algorithms.
Martin Trnecka - One of the best experts on this subject based on the ideXlab platform.
-
From-below Boolean Matrix factorization algorithm based on MDL
Advances in Data Analysis and Classification, 2020Co-Authors: Tatiana Makhalova, Martin TrneckaAbstract:During the past few years Boolean Matrix factorization (BMF) has become an important direction in data analysis. The minimum description length principle (MDL) was successfully adapted in BMF for the model order selection. Nevertheless, a BMF algorithm performing good results w.r.t. standard measures in BMF is missing. In this paper, we propose a novel from-below Boolean Matrix factorization algorithm based on formal concept analysis. The algorithm utilizes the MDL principle as a criterion for the factor selection. On various experiments we show that the proposed algorithm outperforms—from different standpoints—existing state-of-the-art BMF algorithms.
-
From-Below Boolean Matrix Factorization Algorithm Based on MDL
Advances in Data Analysis and Classification, 2020Co-Authors: Tatiana Makhalova, Martin TrneckaAbstract:During the past few years Boolean Matrix factorization (BMF) has become an important direction in data analysis. The minimum description length principle (MDL) was successfully adapted in BMF for the model order selection. Nevertheless, a BMF algorithm performing good results from the standpoint of standard measures in BMF is missing. In this paper, we propose a novel from-below Boolean Matrix factorization algorithm based on formal concept analysis. The algorithm utilizes the MDL principle as a criterion for the factor selection. On various experiments we show that the proposed algorithm outperforms---from different standpoints---existing state-of-the-art BMF algorithms.
-
A Study of Boolean Matrix Factorization Under Supervised Settings
2019Co-Authors: Tatiana Makhalova, Martin TrneckaAbstract:Boolean Matrix factorization is a generally accepted approach used in data analysis to explain data. It is commonly used under unsu-pervised setting or for data preprocessing under supervised settings. In this paper we study factors under supervised settings. We provide an experimental proof that factors are able to explain not only data as a whole but also classes in the data.
-
ICFCA - A Study of Boolean Matrix Factorization Under Supervised Settings
Formal Concept Analysis, 2019Co-Authors: Tatiana Makhalova, Martin TrneckaAbstract:Boolean Matrix factorization is a generally accepted approach used in data analysis to explain data or for data preprocessing in the supervised settings. In this paper we study factors in the supervised settings. We provide an experimental proof that factors are able to explain not only data as a whole but also classes in the data.
-
Data reduction for Boolean Matrix factorization algorithms based on formal concept analysis
Knowledge Based Systems, 2018Co-Authors: Martin Trnecka, Marketa TrneckovaAbstract:Abstract Data size reduction is an important step in many data mining techniques. We present a novel approach based on formal concept analysis to data reduction tailored for Boolean Matrix factorization methods. A general aim of these methods is to find factors that exactly or approximately explain data. The presented approach is able to significantly reduce the size of data by choosing a representative set of rows, and preserve (with a little loss) factors behind the data, i.e. it only slightly affects a quality of the factors produced by Boolean Matrix factorization algorithms.
Jaideep Vaidya - One of the best experts on this subject based on the ideXlab platform.
-
Boolean Matrix decomposition problem theory variations and applications to data engineering
International Conference on Data Engineering, 2012Co-Authors: Jaideep VaidyaAbstract:With the ubiquitous nature and sheer scale of data collection, the problem of data summarization is most critical for effective data management. Classical Matrix decomposition techniques have often been used for this purpose, and have been the subject of much study. In recent years, several other forms of decomposition, including Boolean Matrix Decomposition have become of significant practical interest. Since much of the data collected is categorical in nature, it can be viewed in terms of a Boolean Matrix. Boolean Matrix decomposition (BMD), wherein a Boolean Matrix is expressed as a product of two Boolean matrices, can be used to provide concise and interpretable representations of Boolean data sets. The decomposed matrices give the set of meaningful concepts and their combination which can be used to reconstruct the original data. Such decompositions are useful in a number of application domains including role engineering, text mining as well as knowledge discovery from databases. In this seminar, we look at the theory underlying the BMD problem, study some of its variants and solutions, and examine different practical applications.
-
ICDE - Boolean Matrix Decomposition Problem: Theory, Variations and Applications to Data Engineering
2012 IEEE 28th International Conference on Data Engineering, 2012Co-Authors: Jaideep VaidyaAbstract:With the ubiquitous nature and sheer scale of data collection, the problem of data summarization is most critical for effective data management. Classical Matrix decomposition techniques have often been used for this purpose, and have been the subject of much study. In recent years, several other forms of decomposition, including Boolean Matrix Decomposition have become of significant practical interest. Since much of the data collected is categorical in nature, it can be viewed in terms of a Boolean Matrix. Boolean Matrix decomposition (BMD), wherein a Boolean Matrix is expressed as a product of two Boolean matrices, can be used to provide concise and interpretable representations of Boolean data sets. The decomposed matrices give the set of meaningful concepts and their combination which can be used to reconstruct the original data. Such decompositions are useful in a number of application domains including role engineering, text mining as well as knowledge discovery from databases. In this seminar, we look at the theory underlying the BMD problem, study some of its variants and solutions, and examine different practical applications.
-
extended Boolean Matrix decomposition
International Conference on Data Mining, 2009Co-Authors: Jaideep Vaidya, Vijayalakshmi Atluri, Yuan HongAbstract:With the vast increase in collection and storage of data, the problem of data summarization is most critical for effective data management. Since much of this data is categorical in nature, it can be viewed in terms of a Boolean Matrix. Boolean Matrix decomposition (BMD) has been used to provide concise and interpretable representations of Boolean data sets. A Boolean Matrix can be expressed as a product of two Boolean matrices, where the first Matrix represents a set of meaningful concepts, and the second describes how the observed data can be expressed as combinations of those concepts. Typically, the combination is only in terms of the set union. In other words, a successful Boolean Matrix decomposition gives a set of concepts and shows how every column of the input data can be expressed as a union of some subset of those concepts. However, this way of modeling only incompletely represents real data semantics. Essentially, it ignores a critical component -- the set difference operation: a column can be expressed as the combination of union of certain concepts as well as the exclusion of other concepts. This has two significant benefits. First, the total number of concepts required to describe the data may itself be reduced. Second, a more succinct summarization may be found for every column. In this paper, we propose the extended Boolean Matrix decomposition (EBMD) problem, which aims to factor Boolean matrices using both the set union and set difference operations. We study several variants of the problem, show that they are NP-hard, and propose efficient heuristics to solve them. Extensive experimental results demonstrate the power of EBMD.
-
ICDM - Extended Boolean Matrix Decomposition
2009 Ninth IEEE International Conference on Data Mining, 2009Co-Authors: Jaideep Vaidya, Vijayalakshmi Atluri, Yuan HongAbstract:With the vast increase in collection and storage of data, the problem of data summarization is most critical for effective data management. Since much of this data is categorical in nature, it can be viewed in terms of a Boolean Matrix. Boolean Matrix decomposition (BMD) has been used to provide concise and interpretable representations of Boolean data sets. A Boolean Matrix can be expressed as a product of two Boolean matrices, where the first Matrix represents a set of meaningful concepts, and the second describes how the observed data can be expressed as combinations of those concepts. Typically, the combination is only in terms of the set union. In other words, a successful Boolean Matrix decomposition gives a set of concepts and shows how every column of the input data can be expressed as a union of some subset of those concepts. However, this way of modeling only incompletely represents real data semantics. Essentially, it ignores a critical component -- the set difference operation: a column can be expressed as the combination of union of certain concepts as well as the exclusion of other concepts. This has two significant benefits. First, the total number of concepts required to describe the data may itself be reduced. Second, a more succinct summarization may be found for every column. In this paper, we propose the extended Boolean Matrix decomposition (EBMD) problem, which aims to factor Boolean matrices using both the set union and set difference operations. We study several variants of the problem, show that they are NP-hard, and propose efficient heuristics to solve them. Extensive experimental results demonstrate the power of EBMD.
Frédéric Magniez - One of the best experts on this subject based on the ideXlab platform.
-
Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision
Algorithmica, 2016Co-Authors: Stacey Jeffery, Robin Kothari, François Le Gall, Frédéric MagniezAbstract:The quantum query complexity of Boolean Matrix multiplication is typically studied as a function of the Matrix dimension, $$n$$ n , as well as the number of $$1$$ 1 s in the output, $$\ell $$ ℓ . We prove an upper bound of $$\widetilde{\hbox {O}}(n\sqrt{\ell +1})$$ O ~ ( n ℓ + 1 ) for all values of $$\ell $$ ℓ . This is an improvement over previous algorithms for all values of $$\ell $$ ℓ . On the other hand, we show that for any $$\varepsilon < 1$$ ε < 1 and any $$\ell \le \varepsilon n^2$$ ℓ ≤ ε n 2 , there is an $$\Omega (n\sqrt{\ell })$$ Ω ( n ℓ ) lower bound for this problem, showing that our algorithm is essentially tight. We first reduce Boolean Matrix multiplication to several instances of graph collision. We then provide an algorithm that takes advantage of the fact that the underlying graph in all of our instances is very dense to find all graph collisions efficiently. Using similar ideas, we also show that the time complexity of Boolean Matrix multiplication is $$\tilde{O}(n\sqrt{\ell +1}+\ell \sqrt{n})$$ O ~ ( n ℓ + 1 + ℓ n ) .
-
improving quantum query complexity of Boolean Matrix multiplication using graph collision
International Colloquium on Automata Languages and Programming, 2012Co-Authors: Stacey Jeffery, Robin Kothari, Frédéric MagniezAbstract:The quantum query complexity of Boolean Matrix multiplication is typically studied as a function of the Matrix dimension, n, as well as the number of 1s in the output, l. We prove an upper bound of $\widetilde{\mathrm{O}}(n\sqrt{\ell})$ for all values of l. This is an improvement over previous algorithms for all values of l. On the other hand, we show that for any e<1 and any l≤en2, there is an $\Omega(n\sqrt{\ell})$ lower bound for this problem, showing that our algorithm is essentially tight. We first reduce Boolean Matrix multiplication to several instances of graph collision. We then provide an algorithm that takes advantage of the fact that the underlying graph in all of our instances is very dense to find all graph collisions efficiently.
-
improving quantum query complexity of Boolean Matrix multiplication using graph collision
arXiv: Quantum Physics, 2011Co-Authors: Stacey Jeffery, Robin Kothari, Frédéric MagniezAbstract:The quantum query complexity of Boolean Matrix multiplication is typically studied as a function of the Matrix dimension, n, as well as the number of 1s in the output, \ell. We prove an upper bound of O (n\sqrt{\ell}) for all values of \ell. This is an improvement over previous algorithms for all values of \ell. On the other hand, we show that for any \eps < 1 and any \ell <= \eps n^2, there is an \Omega(n\sqrt{\ell}) lower bound for this problem, showing that our algorithm is essentially tight. We first reduce Boolean Matrix multiplication to several instances of graph collision. We then provide an algorithm that takes advantage of the fact that the underlying graph in all of our instances is very dense to find all graph collisions efficiently.
Bernhard Pfahringer - One of the best experts on this subject based on the ideXlab platform.
-
xor based Boolean Matrix decomposition
International Conference on Data Mining, 2019Co-Authors: Jorg Wicker, Yan Cathy Hua, Rayner Rebello, Bernhard PfahringerAbstract:Boolean Matrix factorization (BMF) is a data summarizing and dimension-reduction technique. Existing BMF methods build on Matrix properties defined by Boolean algebra, where the addition operator is the logical inclusive OR and the multiplication operator the logical AND. As a consequence, this leads to the lack of an additive inverse in all Boolean Matrix operations, which produces an indelible type of approximation error. Previous research adopted various methods to address such an issue and produced reasonably accurate approximation. However, an exact factorization is rarely found in the literature. In this paper, we introduce a new algorithm named XBMaD (XOR-based Boolean Matrix Decomposition) where the addition operator is defined as the exclusive OR (XOR). This change completely removes the error-mitigation issue of OR-based BMF methods, and allows for an exact error-free factorization. An evaluation comparing XBMaD and classic OR-based methods suggested that XBMAD performed equal or in most cases more accurately and faster.
-
ICDM - XOR-Based Boolean Matrix Decomposition
2019 IEEE International Conference on Data Mining (ICDM), 2019Co-Authors: Jorg Wicker, Yan Cathy Hua, Rayner Rebello, Bernhard PfahringerAbstract:Boolean Matrix factorization (BMF) is a data summarizing and dimension-reduction technique. Existing BMF methods build on Matrix properties defined by Boolean algebra, where the addition operator is the logical inclusive OR and the multiplication operator the logical AND. As a consequence, this leads to the lack of an additive inverse in all Boolean Matrix operations, which produces an indelible type of approximation error. Previous research adopted various methods to address such an issue and produced reasonably accurate approximation. However, an exact factorization is rarely found in the literature. In this paper, we introduce a new algorithm named XBMaD (XOR-based Boolean Matrix Decomposition) where the addition operator is defined as the exclusive OR (XOR). This change completely removes the error-mitigation issue of OR-based BMF methods, and allows for an exact error-free factorization. An evaluation comparing XBMaD and classic OR-based methods suggested that XBMAD performed equal or in most cases more accurately and faster.
-
multi label classification using Boolean Matrix decomposition
ACM Symposium on Applied Computing, 2012Co-Authors: Jorg Wicker, Bernhard Pfahringer, Stefan KramerAbstract:This paper introduces a new multi-label classifier based on Boolean Matrix decomposition. Boolean Matrix decomposition is used to extract, from the full label Matrix, latent labels representing useful Boolean combinations of the original labels. Base level models predict latent labels, which are subsequently transformed into the actual labels by Boolean Matrix multiplication with the second Matrix from the decomposition. The new method is tested on six publicly available datasets with varying numbers of labels. The experimental evaluation shows that the new method works particularly well on datasets with a large number of labels and strong dependencies among them.
-
SAC - Multi-label classification using Boolean Matrix decomposition
Proceedings of the 27th Annual ACM Symposium on Applied Computing - SAC '12, 2012Co-Authors: Jorg Wicker, Bernhard Pfahringer, Stefan KramerAbstract:This paper introduces a new multi-label classifier based on Boolean Matrix decomposition. Boolean Matrix decomposition is used to extract, from the full label Matrix, latent labels representing useful Boolean combinations of the original labels. Base level models predict latent labels, which are subsequently transformed into the actual labels by Boolean Matrix multiplication with the second Matrix from the decomposition. The new method is tested on six publicly available datasets with varying numbers of labels. The experimental evaluation shows that the new method works particularly well on datasets with a large number of labels and strong dependencies among them.