nips nips2012 nips2012-128 nips2012-128-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Chunxiao Zhou, Jiseong Park, Yun Fu
Abstract: In this paper, a novel and computationally fast algorithm for computing weighted v-statistics in resampling both univariate and multivariate data is proposed. To avoid any real resampling, we have linked this problem with finite group action and converted it into a problem of orbit enumeration. For further computational cost reduction, an efficient method is developed to list all orbits by their symmetry orders and calculate all index function orbit sums and data function orbit sums recursively. The computational complexity analysis shows reduction in the computational cost from n! or nn level to low-order polynomial level. 1
[01] Babai, L., Kantor, W.M. , and Luks, E.M. (1983), Computational complexity and the classification of finite simple groups, Proc. 24th FOCS, pp. 162-171.
[02] Minaei-Bidgoli, B., Topchy, A., and Punch, W. (2004), A comparison of resampling methods for clustering ensembles, In Proc. International Conference on Artificial Intelligence, Vol. 2, pp. 939-945.
[03] Estabrooks, A., Jo, T., and Japkowicz, N. (2004), A Multiple Resampling Method for Learning from Imbalanced Data Sets, Comp. Intel. 20 (1) pp. 18-36.
[04] Francois, D., Rossib, F., Wertza, V., and Verleysen, M. (2007), Resampling methods for parameter-free and robust feature selection with mutual information, Neurocomputing 70(7-9):1276-1288.
[05] Good, P. (2005), Permutation, Parametric and Bootstrap Tests of Hypotheses, Springer, New York.
[06] Gretton, A., Borgwardt, K., Rasch, M., Scholkopf, B., and Smola, A. (2007), A kernel method for the two-sample- problem, In Advances in Neural Information Processing Systems (NIPS).
[07] Guo, S. (2011), Bayesian Recommender Systems: Models and Algorithms, Ph.D. thesis.
[08] Hopcroft, J., and Tarjan, R. (1973), Efficient algorithms for graph manipulation, Communications of the ACM 16: 372-378.
[09] Huang, J., Guestrin, C., and Guibas, L. (2007), Efficient Inference for Distributions on Permutations, In Advances in Neural Information Processing Systems (NIPS).
[10] Kerber, A. (1999), Applied Finite Group Actions, Springer-Verlag, Berlin.
[11] Kondor, R., Howard, A., and Jebara, T. (2007), Multi-Object Tracking with Representations of the Symmetric Group, Artificial Intelligence and Statistics (AISTATS).
[12] Kuwadekar, A. and Neville, J. (2011), Relational Active Learning for Joint Collective Classification Models, In International Conference on Machine Learning (ICML), P. 385-392.
[13] Liu, H., Palatucci, M., and Zhang, J.(2009), Blockwise coordinate descent procedures for the multi-task lasso, with applications to neural semantic basis discovery, In International Conference on Machine Learning (ICML).
[14] Matthew Higgs and John Shawe-Taylor. (2010), A PAC-Bayes bound for tailored density estimation, In Proceedings of the International Conference on Algorithmic Learning Theory (ALT).
[15] McKay, B. D. (1981), Practical graph isomorphism, Congressus Numerantium 30: 45-87, 10th. Manitoba Conf. on Numerical Math. and Computing.
[16] Mielke, P. W., and K. J. Berry (2007), Permutation Methods: A Distance Function Approach, Springer, New York.
[17] Nicholson, W. K. (2006), Introduction to Abstract Algebra, 3rd ed., Wiley, New York.
[18] Serfling, R. J. (1980), Approximation Theorems of Mathematical Statistics, Wiley, New York.
[19] Song, L. (2008), Learning via Hilbert Space Embedding of Distributions, Ph.D. thesis.
[20] Sutton, R. and Barto, A. (1998), Reinforcement Learning, MIT Press.
[21] Zhou, C., Wang, H., and Wang, Y. M. (2009), Efficient moments-based permutation tests, In Advances in Neural Information Processing Systems (NIPS), p. 2277-2285. 9