Publications

Large-scale Multi-label Learning with Missing Labels

Yu, H.-F.; Jain, P.; Kar, P. & Dhillon, I. S.

(2013) [pdf]

The multi-label classification problem has generated significant interest in
cent years. However, existing approaches do not adequately address two key
allenges: (a) the ability to tackle problems with a large number (say
llions) of labels, and (b) the ability to handle data with missing labels. In
is paper, we directly address both these problems by studying the multi-label
oblem in a generic empirical risk minimization (ERM) framework. Our
amework, despite being simple, is surprisingly able to encompass several
cent label-compression based methods which can be derived as special cases of
r method. To optimize the ERM problem, we develop techniques that exploit the
ructure of specific loss functions - such as the squared loss function - to
fer efficient algorithms. We further show that our learning framework admits
rmal excess risk bounds even in the presence of missing labels. Our risk
unds are tight and demonstrate better generalization performance for low-rank
omoting trace-norm regularization when compared to (rank insensitive)
obenius norm regularization. Finally, we present extensive empirical results
a variety of benchmark datasets and show that our methods perform
gnificantly better than existing label compression based methods and can
ale up to very large datasets such as the Wikipedia dataset.

The phylogenetic distribution of resupinate forms across the major clades of mushroom-forming fungi (Homobasidiomycetes)

Binder, M.; Hibbett, D. S.; Larsson, K. H.; Larsson, E.; Langer, E. & Langer, G.

Systematics and Biodiversity, 3(2) 113-157 (2005) [pdf]

Phylogenetic relationships of resupinate Homobasidiomycetes (Corticiaceae s. lat. and others) were studied using ribosomal DNA (rDNA) sequences from a broad sample of resupinate and nonresupinate taxa. Two datasets were analysed using parsimony, a'core'dataset of 142 species, each of which is represented by four rDNA regions (mitochondrial and nuclear large and small subunits), and a 'full' clataset of 656 species, most of which were represented only by nuclear large subunit rDNA sequences. Both datasets were analysed using traditional heuristic methods with bootstrapping, and the full clataset was also analysed with the Parsimony Ratchet, using equal character weights and six-parameter weighted parsimony. Analyses of both datasets supported monophyly of the eight major clades of Homobasicliomycetes recognised by Hibbett and Thorn, as well as independent lineages corresponding to the Gloeophyllum clade, corticioid clade and jaapia argillacea. Analyses of the full clataset resolved two additional groups, the athelioid clade and trechisporoid clade (the latter may be nested in the polyporoid clade). Thus, there are at least 12 independent clades of Homobasicliomycetes. Higher-level relationships among the major clades are not resolved with confidence. Nevertheless, the euagarics clade, bolete clade, athelioid clade and jaapia argillacea are consistently resolved as a monophyletic group, whereas the cantharelloid clade, gomphoid-phalloid clade and hymenochaetoid clade are placed at the base of the Homobasidiomycetes, which is consistent with the preponderance of imperforate parenthesomes in those groups. Resupinate forms occur in each of the major clades of Homobasidiomycetes, some of which are composed mostly or exclusively of resupinate forms (athelioid clade, corticioid clade, trechisporoid clade,jaapia). The largest concentrations of resupinate forms occur in the polyporoid clade, russuloid clade and hymenochaetoid clade. The cantharelloid clade also includes many resupinate forms, including some that have traditionally been regarded as heterobasidiomycetes (Sebacinaceae, Tulasnellates, Ceratobasidiales). The euagarics clade, which is by far the largest clade in the Homobasidiomycetes, has the smallest fraction of resupinate species. Results of the present study are compared with recent phylogenetic analyses, and a table summarising the phylogenetic distribution of resupinate taxa is presented, as well as notes on the ecology of resupinate forms and related Homobasidiomycetes.

Finding community structure in very large networks

Clauset, A.; Newman, M. E. J. & Moore, C.

Physical Review E, 70() 066111 (2004) [pdf]

Finding community structure in very large networks

Clauset, A.; Newman, M. & Moore, C.

Physical Review E, 70() 066111 (2004) [pdf]

Finding community structure in very large networks

Clauset, A.; Newman, M. E. J. & Moore, C.

(2004) [pdf]

The discovery and analysis of community structure in networks is a topic of
nsiderable recent interest within the physics community, but most methods
oposed so far are unsuitable for very large networks because of their
mputational cost. Here we present a hierarchical agglomeration algorithm for
tecting community structure which is faster than many competing algorithms:
s running time on a network with n vertices and m edges is O(m d log n) where
is the depth of the dendrogram describing the community structure. Many
al-world networks are sparse and hierarchical, with m ~ n and d ~ log n, in
ich case our algorithm runs in essentially linear time, O(n log^2 n). As an
ample of the application of this algorithm we use it to analyze a network of
ems for sale on the web-site of a large online retailer, items in the network
ing linked if they are frequently purchased by the same buyer. The network
s more than 400,000 vertices and 2 million edges. We show that our algorithm
n extract meaningful communities from this network, revealing large-scale
tterns present in the purchasing habits of customers.

Tractable Group Detection on Large Link Data Sets

Kubica, J.; Moore, A. & Schneider, J.

Wu, X.; Tuzhilin, A. & Shavlik, J., ed., 'The Third IEEE International Conference on Data Mining', IEEE Computer Society, 573-576 (2003)

K-groups: Tractable Group Detection on Large Link Data Sets

Kubica, J. M.; Moore, A. & Schneider, J.

2003, Technical report, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA [pdf]

Discovering underlying structure from co-occurrence data is an important task in many fields, including: insurance, intelligence, criminal investigation, epidemiology, human resources, and marketing. For example a store may wish to identify underlying sets of items purchased together or a human resources department may wish to identify groups of employees that collaborate with each other.
Previously Kubica et. al. presented the group detection algorithm (GDA) - an algorithm for finding underlying groupings of entities from co-occurrence data. This algorithm is based on a probabilistic generative model and produces coherent groups that are consistent with prior knowledge. Unfortunately, the optimization used in GDA is slow, making it potentially infeasible for many real world data sets.
To this end, we present k-groups - an algorithm that uses an approach similar to that of k-means (hard clustering and localized updates) to significantly accelerate the discovery of the underlying groups while retaining GDA's probabilistic model. In addition, we show that k-groups is guaranteed to converge to a local minimum. We also compare the performance of GDA and k-groups on several real world and artificial data sets, showing that k-groups' sacrifice in solution quality is significantly offset by its increase in speed. This trade-off makes group detection tractable on significantly larger data sets.

Lanczos algorithms for large symmetric eigenvalue computations: Theory

Cullum, J. & Willoughby, R.

2002, Society for Industrial Mathematics [pdf]