Binary matrix factorisation via column generation
Identifying discrete patterns in binary data is an important dimensionality reduction tool in machine learning and data mining. In this paper, we consider the problem of low-rank binary matrix factorisation (BMF) under Boolean arithmetic. Due to the hardness of this problem, most previous attempts r...
| 主要な著者: | , , |
|---|---|
| フォーマット: | Conference item |
| 言語: | English |
| 出版事項: |
Association for the Advancement of Artificial Intelligence
2021
|
| _version_ | 1826294069001715712 |
|---|---|
| author | Kovacs, RA Gunluk, O Hauser, R |
| author_facet | Kovacs, RA Gunluk, O Hauser, R |
| author_sort | Kovacs, RA |
| collection | OXFORD |
| description | Identifying discrete patterns in binary data is an important dimensionality reduction tool in machine learning and data mining. In this paper, we consider the problem of low-rank binary matrix factorisation (BMF) under Boolean arithmetic. Due to the hardness of this problem, most previous attempts rely on heuristic techniques. We formulate the problem as a mixed integer linear program and use a large scale optimisation technique of column generation to solve it without the need of heuristic pattern mining. Our approach focuses on accuracy and on the provision of optimality guarantees. Experimental results on real world datasets demonstrate that our proposed method is effective at producing highly accurate factorisations and improves on the previously available best known results for 15 out of 24 problem instances. |
| first_indexed | 2024-03-07T03:39:56Z |
| format | Conference item |
| id | oxford-uuid:bd8c9504-dbcd-41d3-94c6-f2e0b0851ca5 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T03:39:56Z |
| publishDate | 2021 |
| publisher | Association for the Advancement of Artificial Intelligence |
| record_format | dspace |
| spelling | oxford-uuid:bd8c9504-dbcd-41d3-94c6-f2e0b0851ca52022-03-27T05:32:41ZBinary matrix factorisation via column generationConference itemhttp://purl.org/coar/resource_type/c_5794uuid:bd8c9504-dbcd-41d3-94c6-f2e0b0851ca5EnglishSymplectic ElementsAssociation for the Advancement of Artificial Intelligence2021Kovacs, RAGunluk, OHauser, RIdentifying discrete patterns in binary data is an important dimensionality reduction tool in machine learning and data mining. In this paper, we consider the problem of low-rank binary matrix factorisation (BMF) under Boolean arithmetic. Due to the hardness of this problem, most previous attempts rely on heuristic techniques. We formulate the problem as a mixed integer linear program and use a large scale optimisation technique of column generation to solve it without the need of heuristic pattern mining. Our approach focuses on accuracy and on the provision of optimality guarantees. Experimental results on real world datasets demonstrate that our proposed method is effective at producing highly accurate factorisations and improves on the previously available best known results for 15 out of 24 problem instances. |
| spellingShingle | Kovacs, RA Gunluk, O Hauser, R Binary matrix factorisation via column generation |
| title | Binary matrix factorisation via column generation |
| title_full | Binary matrix factorisation via column generation |
| title_fullStr | Binary matrix factorisation via column generation |
| title_full_unstemmed | Binary matrix factorisation via column generation |
| title_short | Binary matrix factorisation via column generation |
| title_sort | binary matrix factorisation via column generation |
| work_keys_str_mv | AT kovacsra binarymatrixfactorisationviacolumngeneration AT gunluko binarymatrixfactorisationviacolumngeneration AT hauserr binarymatrixfactorisationviacolumngeneration |