A convex formulation for learning shared structures from multiple tasks

ABSTRACT

Multi-task learning (MTL) aims to improve generalization performance by learning multiple related tasks simultaneously. In this paper, we consider the problem of learning shared structures from multiple related tasks. We present an improved formulation (iASO) for multi-task learning based on the non-convex alternating structure optimization (ASO) algorithm, in which all tasks are related by a shared feature representation. We convert iASO, a non-convex formulation, into a relaxed convex one, which is, however, not scalable to large data sets due to its complex constraints. We propose an alternating optimization (cASO) algorithm which solves the convex relaxation efficiently, and further show that cASO converges to a global optimum. In addition, we present a theoretical condition, under which cASO can find a globally optimal solution to iASO. Experiments on several benchmark data sets confirm our theoretical analysis.

REFERENCES

• 1: Yonatan Amit , Michael Fink , Nathan Srebro , Shimon Ullman, Uncovering shared structures in multiclass classification, Proceedings of the 24th international conference on Machine learning, p.17-24, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273499]
• 2: Ando, R. K. (2007). BioCreative II gene mention tagging system at IBM Watson. Proc. of the 2nd. BioCreative Challenge Evaluation Workshop.
• 3: Rie Kubota Ando , Tong Zhang, A Framework for Learning Predictive Structures from Multiple Tasks and Unlabeled Data, The Journal of Machine Learning Research, 6, p.1817-1853, 12/1/2005
• 4: Andreas Argyriou , Theodoros Evgeniou , Massimiliano Pontil, Convex multi-task feature learning, Machine Learning, v.73 n.3, p.243-272, December 2008 [doi>10.1007/s10994-007-5040-8]
• 5: Argyriou, A., Micchelli, C. A., Pontil, M., & Ying, Y. (2007). A spectral regularization framework for multi-task structure learning. Adv. in Neural Info. Proc. Sys..
• 6: Bart Bakker , Tom Heskes, Task clustering and gating for bayesian multitask learning, The Journal of Machine Learning Research, 4, p.83-99, 12/1/2003
• 7: Baxter, J. (2000). A model of inductive bias learning. J. Artif. Intell. Res., 12, 149--198.
• 8: Bertsekas, D. P. (1999). Nonlinear programming. Athena Scientific.
• 9: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 10: Rich Caruana, Multitask Learning, Machine Learning, v.28 n.1, p.41-75, July 1997 [doi>10.1023/A:1007379606734]
• 11: Chang, C.-C., & Lin, C.-J. (2001). LIBSVM: a library for support vector machines. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
• 12: Theodoros Evgeniou , Charles A. Micchelli , Massimiliano Pontil, Learning Multiple Tasks with Kernel Methods, The Journal of Machine Learning Research, 6, p.615-637, 12/1/2005
• 13: Golub, G. H., & Loan, C. F. V. (1996). Matrix computations. Johns Hopkins University Press.
• 14: Heisele, B., Serre, T., Pontil, M., Vetter, T., & Poggio, T. (2001). Categorization by learning and combining object parts. Adv. in Neural Info. Proc. Sys. (pp. 1239--1245).
• 15: Jacob, L., Bach, F., & Vert, J.-P. (2008). Clustered multi-task learning: A convex formulation. Adv. in Neural Info. Proc. Sys. (pp. 745--752).
• 16: Neil D. Lawrence , John C. Platt, Learning to learn with the informative vector machine, Proceedings of the twenty-first international conference on Machine learning, p.65, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015382]
• 17: David D. Lewis , Yiming Yang , Tony G. Rose , Fan Li, RCV1: A New Benchmark Collection for Text Categorization Research, The Journal of Machine Learning Research, 5, p.361-397, 12/1/2004
• 18: Obozinski, G., Taskar, B., & Jordan, M. I. (2006). Multi-task feature selection. Technical report, Dept. of Statistics, UC Berkeley.
• 19: M. L. Overton , R. S. Womersley, Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices, Mathematical Programming: Series A and B, v.62 n.2, p.321-357, Nov. 15, 1993 [doi>10.1007/BF01585173]
• 20: Quattoni, A., Collins, M., & Darrell, T. (2007). Learning visual representations using images with captions. IEEE Conf. on Comp. Vision and Patt. Recog..
• 21: Schwaighofer, A., Tresp, V., & Yu, K. (2004). Learning gaussian process kernels via hierarchical bayes. Adv. in Neural Info. Proc. Sys..
• 22: Ueda, N., & Saito, K. (2002). Parametric mixture models for multi-labeled text. Adv. in Neural Info. Proc. Sys. (pp. 721--728).
• 23: Ya Xue , Xuejun Liao , Lawrence Carin , Balaji Krishnapuram, Multi-Task Learning for Classification with Dirichlet Process Priors, The Journal of Machine Learning Research, 8, p.35-63, 5/1/2007
• 24: Kai Yu , Volker Tresp , Anton Schwaighofer, Learning Gaussian processes from multiple tasks, Proceedings of the 22nd international conference on Machine learning, p.1012-1019, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102479]
• 25: Shipeng Yu , Volker Tresp , Kai Yu, Robust multi-task learning with t-processes, Proceedings of the 24th international conference on Machine learning, p.1103-1110, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273635]
• 26: Zhang, J., Ghahramani, Z., & Yang, Y. (2005). Learning multiple related tasks using latent independent component analysis. Adv. in Neural Info. Proc. Sys..

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Convex programming

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory