{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T10:52:52Z","timestamp":1761648772287},"reference-count":38,"publisher":"MIT Press - Journals","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Neural Computation"],"published-print":{"date-parts":[[2020,8]]},"abstract":"<jats:p>We propose a new formulation of multiple-instance learning (MIL), in which a unit of data consists of a set of instances called a bag. The goal is to find a good classifier of bags based on the similarity with a \u201cshapelet\u201d (or pattern), where the similarity of a bag with a shapelet is the maximum similarity of instances in the bag. In previous work, some of the training instances have been chosen as shapelets with no theoretical justification. In our formulation, we use all possible, and thus infinitely many, shapelets, resulting in a richer class of classifiers. We show that the formulation is tractable, that is, it can be reduced through linear programming boosting (LPBoost) to difference of convex (DC) programs of finite (actually polynomial) size. Our theoretical result also gives justification to the heuristics of some previous work. The time complexity of the proposed algorithm highly depends on the size of the set of all instances in the training sample. To apply to the data containing a large number of instances, we also propose a heuristic option of the algorithm without the loss of the theoretical guarantee. Our empirical study demonstrates that our algorithm uniformly works for shapelet learning tasks on time-series classification and various MIL tasks with comparable accuracy to the existing methods. Moreover, we show that the proposed heuristics allow us to achieve the result in reasonable computational time.<\/jats:p>","DOI":"10.1162\/neco_a_01297","type":"journal-article","created":{"date-parts":[[2020,6,10]],"date-time":"2020-06-10T22:41:18Z","timestamp":1591828878000},"page":"1580-1613","source":"Crossref","is-referenced-by-count":1,"title":["Theory and Algorithms for Shapelet-Based Multiple-Instance Learning"],"prefix":"10.1162","volume":"32","author":[{"given":"Daiki","family":"Suehiro","sequence":"first","affiliation":[{"name":"Department of Advanced Information Technology, Faculty of Information Science and Electrical Engineering, Kyushu University, and RIKEN Center for Advanced Intelligence Project, Nishi-ku, Fukuoka, 8190395, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kohei","family":"Hatano","sequence":"additional","affiliation":[{"name":"Faculty of Arts and Science, Kyushu University, and RIKEN Center for Advanced Intelligence Project, Nishi-ku, Fukuoka, 8190395, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eiji","family":"Takimoto","sequence":"additional","affiliation":[{"name":"Department of Informatics, Faculty of Information Science and Electrical Engineering, Kyushu University, Nishi-ku, Fukuoka, 8190395, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuji","family":"Yamamoto","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Keio University, and RIKEN Center for Advanced Intelligence Project, Minatokita-ku, Yokohama, 2238522, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kenichi","family":"Bannai","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Keio University, and RIKEN Center for Advanced Intelligence Project, Minatokita-ku, Yokohama, 2238522, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Akiko","family":"Takeda","sequence":"additional","affiliation":[{"name":"Department of Creative Informatics, University of Tokyo, and RIKEN Center for Advanced Intelligence Project, Bunkyo-ku, Tokyo, 1138656, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","reference":[{"key":"B1","first-page":"65","volume-title":"Advances in neural information processing systems","volume":"16","author":"Andrews S.","year":"2004"},{"key":"B2","first-page":"577","volume-title":"Advances in neural information processing systems","volume":"15","author":"Andrews S.","year":"2003"},{"key":"B3","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/978-3-540-30115-8_9","author":"Auer P.","year":"2004","journal-title":"Lecture Notes in Computer Science: Vol. 3201. Proceedings of the European Conference on Machine Learning"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-016-0483-9"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1162\/153244303321897690"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2017.10.009"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2006.248"},{"key":"B8","author":"Chen Y.","year":"2015","journal-title":"The UCR time series classification archive."},{"key":"B9","first-page":"929","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Cuturi M.","year":"2011"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012470815092"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(96)00034-3"},{"key":"B12","unstructured":"Doran, G. (2015).Multiple instance learning from distributions. PhD diss. Case Western Reserve University."},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-013-5429-5"},{"key":"B14","first-page":"179","author":"G\u00e4rtner T.","year":"2002","journal-title":"Proceedings of the International Conference on Machine Learning"},{"key":"B15","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1145\/2623330.2623613","author":"Grabocka J.","year":"2014","journal-title":"Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining"},{"key":"B16","author":"Grabocka J.","year":"2015","journal-title":"CoRR"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-013-0322-1"},{"key":"B18","first-page":"1209","author":"Hou L.","year":"2016","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-016-0473-y"},{"key":"B20","first-page":"668","author":"Keogh E. J.","year":"2013","journal-title":"Proceedings of the International Conference on Data Mining"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1235-y"},{"key":"B22","author":"L\u00f6ning M.","year":"2019","journal-title":"sktime: A unified interface for machine learning with time series"},{"key":"B23","author":"Mohri M.","year":"2012","journal-title":"Foundations of machine learning"},{"key":"B24","first-page":"547","volume-title":"Advances in neural information processing systems","volume":"12","author":"Platt J. C.","year":"2000"},{"key":"B25","first-page":"1","author":"Renard X.","year":"2015","journal-title":"Proceedings of the IEEE International Conference on Data Science and Advanced Analytics"},{"issue":"1","key":"B26","first-page":"2999","volume":"13","author":"Sabato S.","year":"2012","journal-title":"Journal of Machine Learning Research"},{"key":"B27","first-page":"2310","author":"Sangnier M.","year":"2016","journal-title":"Proceedings of the International Conference on Machine Learning"},{"key":"B28","author":"Sch\u00f6kopf B.","year":"2002","journal-title":"Learning with kernels: Support vector machines, regularization, optimization, and beyond"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1080\/02331930902730070"},{"key":"B30","first-page":"921","author":"Shimodaira H.","year":"2001","journal-title":"Proceedings of the International Conference on Neural Information Processing Systems"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-9297-1_18"},{"key":"B33","first-page":"1585","volume-title":"Advances in neural information processing systems","volume":"20","author":"Warmuth M.","year":"2008"},{"key":"B34","author":"Wistuba M.","year":"2015","journal-title":"CoRR"},{"key":"B35","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1145\/1557019.1557122","author":"Ye L.","year":"2009","journal-title":"Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining"},{"key":"B36","first-page":"1169","author":"Yu C.-N. J.","year":"2009","journal-title":"Proceedings of the International Conference on Machine Learning"},{"key":"B37","first-page":"1975","volume-title":"Advances in neural information processing systems","volume":"29","author":"Yu F. X. X.","year":"2016"},{"key":"B38","first-page":"1417","volume-title":"Advances in neural information processing systems","volume":"18","author":"Zhang C.","year":"2006"},{"key":"B39","first-page":"82","author":"Zhang D.","year":"2013","journal-title":"Proceedings of the International Conference on Machine Learning"}],"container-title":["Neural Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/neco_a_01297","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T20:34:58Z","timestamp":1616186098000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/neco\/article\/32\/8\/1580-1613\/95628"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8]]},"references-count":38,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["10.1162\/neco_a_01297"],"URL":"https:\/\/doi.org\/10.1162\/neco_a_01297","relation":{},"ISSN":["0899-7667","1530-888X"],"issn-type":[{"value":"0899-7667","type":"print"},{"value":"1530-888X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8]]}}}