Построение оптимальных оценок с помощью метода адаптивных весов в задачах обучения с размеченными и неразмеченными данными тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Пучкин Никита Андреевич

• Пучкин Никита Андреевич
• кандидат наук
• 2023

Оглавление диссертации кандидат наук Пучкин Никита Андреевич

Table of Contents

Introduction

Chapter 1. Multiclass classification

1.1. Problem statement

1.2. Multiclass classification approaches

1.3. Nonparametric multiclass classification and literature review

1.4. Contribution

1.5. Notation and model assumptions

1.6. An adaptive weights method for multiclass classification

1.7. Numerical experiments

1.8. Theoretical properties of the MSSA procedure

1.9. Proof of Theorem

1.10. Auxiliary results

1.11. Additional proofs

Chapter 2. Manifold learning

2.1. Literature review

2.2. Manifold learning and structural adaptation

2.3. Contribution

2.4. Model assumptions

2.5. An adaptive weights method for manifold denoising

2.6. Numerical experiments

2.7. Theoretical properties of SAME

2.8. Proofs of the main results

2.9. Proofs of auxiliary results

Conclusion

References

Введение диссертации (часть автореферата) на тему «Построение оптимальных оценок с помощью метода адаптивных весов в задачах обучения с размеченными и неразмеченными данными»

Introduction

The problem of pattern recognition in large datasets have recently attracted huge attention. The problem of statistical learning finds more and more applications in the era of big data. The diversity of areas of utilization is also impressive: from bioinformatics (e.g., protein fold prediction [1]) and finance (credit rating [2] and bankruptcy [3] prediction) to speech recognition [4] and image analysis [5, 6] and restoration [7, 8]. Such an interest caused a substantial progress in theoretical investigation of the existing methods of machine learning and motivated researches develop new, more efficient ones. Analysis of learning algorithms usually relies on the tools from probability theory and mathematical statistics. That is, a learner assumes that the data he possesses is generated from a statistical model, and he must perform an inference based on this model.

Speaking of statistical learning problems, one can distinguish between three major groups: supervised, semi-supervised, and unsupervised learning. In supervised learning problems, each instance of a given sample has a label, also referred to as a response or a target variable (usually, it is a real number). The goal of the learner is to predict a label of a newly arrived instance, which is not presented in the training sample. The most popular examples of supervised learning problems are classification and regression. In opposite, in an unsupervised learning problem, the learner has to recognize patterns in unlabelled data. The most common examples of unsupervised learning problems include clustering and manifold learning. Finally, in the semi-supervised setup the learner has to perform an inference based on a small portion of labelled instances and a large number of unlabelled ones.

The present thesis pursues methological and theoretical purposes. It aims at developing new adaptive algorithms for supervised and unsupervised learning problems with strong theoretical guarantees on their performance. Chapter 1 is devoted multiclass classification. We suggest an adaptive multiclass nearest neighbor classifier, Algorithm 1. Though the statisticians are familiar with k-nearest neighbor rules for a long time, their nonasymptotic analysis was performed quite recently. In [9], the author proved a minimax optimal upper bound on the excess risk of a weighted nearest neighbor classifier. Unfortunately, the approach of [9] requires quite restrictive assumptions. For instance, the author assumed that the distribution of feature vectors satisfies the so-called strong density assumption. This issue was partially addressed in [10] and [11], where the authors introduced a novel variant of smoothness of the target function, connecting the distribution of feature vectors and labels. Major steps towards understanding the limitations of k-nearest neighbor rules were made in [12] and [13]. In particular, in [12] the authors showed that a universal choice of k in the nearest neighbor classifier leads to strictly suboptimal performance under quite realistic assumptions. In [13], the authors suggested to use auxiliary unlabelled data for the point-dependent choice of k. However, this approach is not always applicable, since the unlabelled data may be unavailable to the statistician. In the present thesis, we develop the ideas of spatial stagewise aggregation [3] and suggest an adaptive weights method based on combination of nearest neighbor estimates. Though the extension of the algorithm in [3] to the multiclass

case is rather straightforward, its theoretical analysis is much more involved. In contrast to [3], we impose much weaker assumptions and show that, under the same conditions as in [12], our procedure attains minimax optimal rates of convergence up to a logarithmic factor (see Theorem 1). Unlike [13], our procedure does not involve any auxiliary data. To our knowledge, this is the first such estimator in the literature.

Chapter 2 is devoted to a manifold learning problem, that is, estimation of a smooth low-dimensional submanifold in Rd from noisy observations. This problem was extensively studied in the literature. Unfortunately, the existing methods of manifold estimation either require the noise magnitude be extremely small (e.g., [8, 14-16]) or assume the noise distribution is known (e.g. [17, 18]). In the present thesis, we focus on a setup, which was not previously considered in the literature. Namely, in contrast to [17, 18], we impose mild assumptions on the noise distribution and we allow the noise magnitude be much larger than in [8, 14-16, 19]. Though our assumptions are quite realistic, they significantly differ from the usual ones. Hence, it is not surprising that the existing algorithms either have no theoretical guarantees in our setup or show suboptimal performance. We faced a challenging problem of suggesting an optimal manifold estimate under mild conditions on the noise distribution. In the present thesis, we extend the idea of structural adaptation [20, 21] and suggest a novel algorithm (Algorithm 2) for manifold denoising. The algorithm allows us to construct a manifold estimate with strong theoretical guarantees (see Theorem

4). We also prove a new minimax lower bound on the accuracy of manifold estimation (Theorem

5), which yields the optimality of our method.

The problems considered in Chapters 1 and 2 are very different, but the methods we proposed for these problems, Algorithm 1 and Algorithm 2, share similar ideas. The core of the algorithms is the so called adaptive weights approach, properly tailored to the problems of multiclass classification and manifold denoising. The fact that the suggested procedures are adaptive (that is, they implicitly perform a partial parameter tuning, simplifying the model selection) increase their practical value. We also would like to note that one may combine Algorithm 1 and Algorithm 2 and apply them to semi-supervised learning problems.

The contribution of the present thesis is as follows.

1. We propose an algorithm for multiclass classification, Algorithm 1, which is based on aggregation of nearest neighbor estimates. The procedure automatically chooses an almost optimal number of neighbors for each test point and each class. Besides, it adapts to the smoothness of the target function.

2. We prove a large deviation bound on the excess risk of the estimate, returned by Algorithm 1, under mild assumptions. The obtained theoretical results are new in the literature and claim optimal accuracy of classification with only a logarithmic payment for adaptation.

3. We suggest a novel algorithm for manifold denoising, Algorithm 2, based on the idea of structural adaptation.

4. Based on Algorithm 2, we construct a new manifold estimate and prove a new upper bound on the accuracy of manifold estimation.

5. We provide a new minimax lower bound on the accuracy of manifold estimation, claiming the optimality of our procedure.

Main results of the thesis were presented at the following conferences, workshops, schools, and seminars.

1. Workshop "New frontiers in high-dimensional probability and statistics", Moscow, February 23-24, 2018. Talk: "Pointwise adaptation via stagewise aggregation of local estimates for multiclass classification".

2. 12th International Vilnius Conference on Probability Theory and Mathematical Statistics and 2018 IMS Annual Meeting on Probability and Statistics, Vilnius, Lithuania, July 2-6, 2018. Poster: "Pointwise adaptation via stagewise aggregation of local estimates for multi-class classification"

3. Research seminar "Structural Learning", Moscow, October 11, 2018. Talk: "Manifold Learning".

4. Winter school "New frontiers in high-dimensional probability and statistics 2", Moscow, February 22-23, 2019. Talk: "Manifold estimation from noisy observations".

5. 49th Saint-Flour Summer School, Saint-Flour, France, July 7-19, 2019. Talk: "Manifold estimation from noisy observations".

6. Conference "Structural Inference in High-Dimensional Models 2", Pushkin, Saint-Petersburg, August 26-30, 2019. Poster: "Structure-adaptive manifold estimation".

7. HSE-Yandex Autumn School on Generative Models, Moscow, November 26-29, 2019. Talk: "Structure-adaptive manifold estimation".

8. Research seminar "Structural Learning", Moscow, December 3, 2019. Talk: "Sample complexity of learning a manifold with an unknown dimension".

9. Conference "Mathematical Methods of Statistics", Luminy, France, December 16-20, 2019. Talk: "Structure-adaptive manifold estimation".

10. HSE Faculty of Computer Science conference on Machine Learning, Fundamental Research track, Moscow, November 18-20, 2020. Talk: "Structure-adaptive manifold estimation".

Main results of the thesis were published in two papers in peer-reviewed journals [22, 23].

The thesis contents and the presented main results reflect the author's personal contribution. The author prepared the results for publication in collaboration with the scientific advisor. The author's contribution is primary. All the presented results were obtained personally by the author.

The thesis consists of introduction, 2 chapters, conclusion, and bibliography. Each chapter starts with the literature review on the relevant topic. The thesis is 100 pages long, including 95 pages of the text, 5 tables, and 5 figures. The bibliography is 5 pages long and it includes 83 items.

Заключение диссертации по теме «Другие cпециальности», Пучкин Никита Андреевич

Conclusion

1. We proposed an adaptive algorithm for multiclass classification, which is based on aggregation of nearest neighbor estimates. The procedure automatically chooses an almost optimal number of neighbors for each test point and each class and adapts to the smoothness of the underlying target function.

2. We proved an upper bound on the excess risk of the classifier, returned by the proposed algorithm, under mild assumptions. This is the first theoretical result matching the minimax lower bound up to a logarithmic factor under these assumptions.

3. We developed a new structure-adaptive manifold estimation procedure for manifold denois-ing. The procedure turns out to be more robust to orthogonal noise, than the existing methods.

4. We carried out theoretical analysis of the proposed procedure. We proved new upper and lower bounds on the accuracy of manifold estimation. The bounds coincide up to a muti-plicative constant, claiming optimality of the proposed algorithm in the minimax sense.

Список литературы диссертационного исследования кандидат наук Пучкин Никита Андреевич, 2023 год

References

1. C. H.Q. Ding and I. Dubchak. Multi-class protein fold recognition using support vector machines and neural networks. Bioinformatics, 17(4):349-58, 2001.

2. H. Ahn and K.-J. Kim. Corporate credit rating using multiclass classification models with order information. World Academy of Science, Engineering and Technology, 60:95-100, 12 2011.

3. D. Belomestny and V. Spokoiny. Spatial aggregation of local likelihood estimates with applications to classification. The Annals of Statistics, 35(5):2287-2311, 2007.

4. A. Ganapathiraju, J.E. Hamaker, and J. Picone. Applications of support vector machines to speech recognition. IEEE Transactions on Signal Processing, 52(8):2348-2355, 2004.

5. J. Kittler, R. Ghaderi, T. Windeatt, and J. Matas. Face verification via error correcting output codes. Image and Vision Computing, 21:1163-1169, 12 2003.

6. D. Li and D. B. Dunson. Classification via local manifold approximation. Biometrika, 107(4):1013-1020, 2020.

7. G. Peyre. Manifold models for signals and images. Computer Vision and Image Understanding, 113(2):249-260, 2009.

8. S. Osher, Z. Shi, and W. Zhu. Low dimensional manifold model for image processing. SIAM Journal on Imaging Sciences, 10(4):1669-1690, 2017.

9. R. J. Samworth. Optimal weighted nearest neighbour classifiers. The Annals of Statistics, 40(5):2733-2763, 2012.

10. K. Chaudhuri and S. Dasgupta. Rates of convergence for nearest neighbor classification. In Proceedings of the 27th International Conference on Neural Information Processing Systems -Volume 2, NIPS'14, pages 3437-3445. MIT Press, 2014.

11. M. Doring, L. Gyorfi, and H. Walk. Rate of convergence of fc-nearest-neighbor classification rule. Journal of Machine Learning Research, 18(227):1-16, 2018.

12. S. Gadat, T. Klein, and C. Marteau. Classification in general finite dimensional spaces with the fc-nearest neighbor rule. The Annals of Statistics, 44(3):982-1009, 2016.

13. T. I. Cannings, T. B. Berrett, and R. J. Samworth. Local nearest neighbour classification with applications to semi-supervised learning. The Annals of Statistics, 48(3):1789-1814, 2020.

14. M. Hein and M. Maier. Manifold denoising. In Advances in Neural Information Processing Systems, volume 19. MIT Press, 2006.

15. M. Maggioni, S. Minsker, and N. Strawn. Multiscale dictionary learning: non-asymptotic bounds and robustness. Journal of Machine Learning Research, 17(2):1-51, 2016.

16. E. Aamari and C. Levrard. Nonasymptotic rates for manifold, tangent space and curvature estimation. The Annals of Statistics, 47(1):177-204, 2019.

17. C. R. Genovese, M. Perone-Pacifico, I. Verdinelli, and L. Wasserman. Minimax manifold estimation. Journal of Machine Learning Research, 13(43):1263-1291, 2012.

18. C. R. Genovese, M. Perone-Pacifico, I. Verdinelli, and L. Wasserman. Manifold estimation and

singular deconvolution under Hausdorff loss. The Annals of Statistics, 40(2):941-963, 2012.

19. E. Aamari and C. Levrard. Stability and minimax optimality of tangential Delaunay complexes for manifold reconstruction. Discrete & Computational Geometry, 59(4):923-971, 2018.

20. M. Hristache, A. Juditsky, and V. Spokoiny. Direct estimation of the index coefficient in a single-index model. The Annals of Statistics, 29(3):595-623, 2001.

21. M. Hristache, A. Juditsky, J. Polzehl, and V. Spokoiny. Structure adaptive approach for dimension reduction. The Annals of Statistics, 29(6):1537-1566, 2001.

22. N. Puchkin and V. Spokoiny. An adaptive multiclass nearest neighbor classifier. ESAIM: Probability and Statistics, 24:69-99, 2020.

23. N. Puchkin and V. Spokoiny. Structure-adaptive manifold estimation. Journal of Machine Learning Research, 23(40):1-62, 2022.

24. R. Tibshirani, T. Hastie, B. Narasimhan, and G. Chu. Class prediction by nearest shrunken centroids, with applications to DNA microarrays. Statistical Science, 18(1):104-117, 2003.

25. T. G. Dietterich and G. Bakiri. Solving multiclass learning problems via error-correcting output codes. Journal of Artificial Intelligence Research, 2(1):263-286, 1995.

26. E. L. Allwein, R. E. Schapire, and Y. Singer. Reducing multiclass to binary: a unifying approach for margin classifiers. Journal of Machine Learning Research, 1(2):113-141, 2001.

27. K. Crammer and Y. Singer. On the algorithmic implementation of multiclass kernel-based vector machines. Journal of Machine Learning Research, 2:265-292, 2002.

28. B. I. Rubinstein, P. L. Bartlett, and J. H. Rubinstein. Shifting, one-inclusion mistake bounds and tight multiclass expected risk bounds. In Advances in Neural Information Processing Systems 19, pages 1193-1200. MIT Press, 2007.

29. A. Daniely, S. Sabato, and S. Shalev-Shwartz. Multiclass learning approaches: A theoretical comparison with implications. In Advances in Neural Information Processing Systems 25, pages 485-493. Curran Associates, Inc., 2012.

30. R. Rifkin and A. Klautau. In defense of one-vs-all classification. Journal of Machine Learning Research, 5:101-141, 2004.

31. A. B. Tsybakov. Optimal rates of aggregation. In Learning Theory and Kernel Machines, pages 303-313. Springer Berlin Heidelberg, 2003.

32. G. Lecue. Optimal rates of aggregation in classification under low noise assumption. Bernoulli, 13(4):1000-1022, 2007.

33. P. Rigollet and A. B. Tsybakov. Sparse estimation by exponential weighting. Statistical Science. A Review Journal of the Institute of Mathematical Statistics, 27(4):558-575, 2012.

34. A. B. Yuditskii, A. V. Nazin, A. B. Tsybakov, and N. Vayatis. Recursive aggregation of estimators by the mirror descent method with averaging. Problemy Peredachi Informatsii, 41(4):78-96, 2005.

35. A. Juditsky, P. Rigollet, and A. B. Tsybakov. Learning by mirror averaging. The Annals of Statistics, 36(5):2183-2206, 2008.

36. G. Lecue. Empirical risk minimization is optimal for the convex aggregation problem.

Bernoulli, 19(5B):2153-2166, 2013.

37. D. Dai, P. Rigollet, and T. Zhang. Deviation optimal learning using greedy Q-aggregation. The Annals of Statistics, 40(3):1878-1905, 2012.

38. G. Lecue and P. Rigollet. Optimal learning with Q-aggregation. The Annals of Statistics, 42(1):211-224, 2014.

39. C. Butucea, J.-F. Delmas, A. Dutfoy, and R. Fischer. Optimal exponential bounds for aggregation of estimators for the Kullback-Leibler loss. Electronic Journal of Statistics, 11(1):2258-2294, 2017.

40. P. Rigollet. Kullback-Leibler aggregation and misspecified generalized linear models. The Annals of Statistics, 40(2):639-665, 2012.

41. J.-Y. Audibert and A. B. Tsybakov. Fast learning rates for plug-in classifiers. The Annals of Statistics, 35(2):608-633, 2007.

42. V. Dinh, L. S. T. Ho, N. V. Cuong, D. Nguyen, and B. T. Nguyen. Learning from non-iid data: fast rates for the one-vs-all multiclass plug-in classifiers. In Theory and applications of models of computation, volume 9076 of Lecture Notes in Comput. Sci., pages 375-387. Springer, Cham, 2015.

43. E. Mammen and A. B. Tsybakov. Smooth discrimination analysis. The Annals of Statistics, 27(6):1808-1829, 1999.

44. A. Agarwal. Selective sampling algorithms for cost-sensitive multiclass prediction. In Proceedings of the 30th International Conference on Machine Learning, volume 28 (3), pages 1220-1228. PMLR, 2013.

45. V. Perchet and P. Rigollet. The multi-armed bandit problem with covariates. The Annals of Statistics, 41(2):693-721, 2013.

46. V. Spokoiny and C. Vial. Parameter tuning in pointwise adaptation using a propagation approach. The Annals of Statistics, 37(5B):2783-2807, 2009.

47. D. Dheeru and E. Karra Taniskidou. UCI machine learning repository, 2017.

48. J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319-2323, 2000.

49. S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323-2326, 2000.

50. Z. Zhang and J. Wang. MLLE: Modified locally linear embedding using multiple weights. In Advances in Neural Information Processing Systems, volume 19. MIT Press, 2006.

51. M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6):1373-1396, 2003.

52. L. van der Maaten and G. Hinton. Visualizing data using t-SNE. Journal of Machine Learning Research, 9(86):2579-2605, 2008.

53. Z. Shi and J. Sun. Convergence of the point integral method for Laplace-Beltrami equation on point cloud. Research in the Mathematical Sciences, 4(1):22, 2017.

54. W. Wang and M. A. Carreira-Perpinan. Manifold blurring mean shift algorithms for manifold

denoising. In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 1759-1766, 2010.

55. D. Gong, F. Sha, and G. Medioni. Locally linear denoising on image manifolds. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pages 265-272. PMLR, 2010.

56. K. Fukunaga and L. Hostetler. The estimation of the gradient of a density function, with applications in pattern recognition. IEEE Transactions on Information Theory, 21(1):32-40, 1975.

57. Y. Cheng. Mean shift, mode seeking, and clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17(8):790-799, 1995.

58. U. Ozertem and D. Erdogmus. Locally defined principal curves and surfaces. Journal of Machine Learning Research, 12(34):1249-1286, 2011.

59. C. R. Genovese, M. Perone-Pacifico, I. Verdinelli, and L. Wasserman. Nonparametric ridge estimation. The Annals of Statistics, 42(4):1511-1545, 2014.

60. M. A. Carreira-Perpinan. Gaussian mean-shift is an em algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(5):767-776, 2007.

61. D. Comaniciu and P. Meer. Mean shift: a robust approach toward feature space analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(5):603-619, 2002.

62. J. Li, S. Ray, and B. G. Lindsay. A nonparametric statistical approach to clustering via mode identification. Journal of Machine Learning Research, 8(59):1687-1723, 2007.

63. E. Arias-Castro, D. Mason, and B. Pelletier. On the estimation of the gradient lines of a density and the consistency of the mean-shift algorithm. Journal of Machine Learning Research, 17(43):1-28, 2016.

64. M. A. Carreira-Perpinan. A review of mean-shift algorithms for clustering. ArXiv, abs/1503.00687, 2015.

65. D. Eberly, R. Gardner, B. Morse, S. Pizer, and C. Scharlach. Ridges for image analysis. Journal of Mathematical Imaging and Vision, 4(4):353-373, 1994.

66. Y. Xia, H. Tong, W. K. Li, and L.-X. Zhu. An adaptive estimation of dimension reduction space. Journal of the Royal Statistical Society. Series B (Statistical Methodology), 64(3):363-410, 2002.

67. A. K. H. Kim and H. H. Zhou. Tight minimax rates for manifold estimation under Hausdorff loss. Electronic Journal of Statistics, 9(1):1562-1582, 2015.

68. N. G. Trillos, D. Sanz-Alonso, and R. Yang. Local regularization of noisy point clouds: Improved global geometric estimates and data analysis. Journal of Machine Learning Research, 20(136):1-37, 2019.

69. C. Fefferman, S. Ivanov, Y. Kurylev, M. Lassas, and H. Narayanan. Fitting a putative manifold to noisy data. In Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 688-720. PMLR, 2018.

70. O. Chapelle, B. Scholkopf, and A. Zien. Semi-Supervised Learning. The MIT Press, 1st

edition, 2010.

71. M.-Y. Cheng and H.-T. Wu. Local linear regression on manifolds and its geometric interpretation. Journal of the American Statistical Association, 108(504):1421-1434, 2013.

72. H. Federer. Curvature measures. Transactions of the American Mathematical Society, 93(3):418-491, 1959.

73. A. B. Tsybakov. Introduction to nonparametric estimation. Springer Series in Statistics. Springer, New York, 2009.

74. E. Gine and V. Koltchinskii. Empirical graph Laplacian approximation of Laplace-Beltrami operators: large sample results. IMS Lecture Notes - Monograph Series, 51:238-259, 2006.

75. A. W. van der Vaart and J. A. Wellner. Weak convergence and empirical processes. Springer Series in Statistics. Springer-Verlag, New York, 1996.

76. B. Recht, W. Xu, and B. Hassibi. Null space conditions and thresholds for rank minimization. Mathematical Programming, 127(1, Ser. B):175-202, 2011.

77. S. J. Szarek. Metric entropy of homogeneous spaces. Banach Center Publications, 43(1):395-410, 1998.

78. E. Gine and A. Guillou. Rates of strong uniform consistency for multivariate kernel density estimators. Annales de l'Institut Henri Poincaré. Probabilités et Statistiques, 38(6):907-921, 2002.

79. M. Talagrand. New concentration inequalities in product spaces. Inventiones Mathematicae, 126(3):505-563, 1996.

80. O. Bousquet. A Bennett concentration inequality and its application to suprema of empirical processes. Comptes Rendus Mathématique. Académie des Sciences. Paris, 334(6):495-500, 2002.

81. C. Davis and W. Kahan. The rotation of eigenvectors by a perturbation. III. SIAM Journal on Numerical Analysis, 7(1):1-46, 1970.

82. J.-D. Boissonnat, A. Lieutier, and M. Wintraecken. The reach, metric distortion, geodesic convexity and the variation of tangent spaces. Journal of Applied and Computational Topology, 3(1):29-58, 2019.

83. G. H. Golub and C. F. Van Loan. Matrix computations. Johns Hopkins University Press, 4th edition, 2013.