Crowdsourcing is a promising human-in-the-loop paradigm for processing computer hard tasks by harnessing crowd intelligence. However, canonical crowdsourcing systems mostly need to aggregate/transmit worker data and may lead to privacy-leakage. To tackle this problem, we propose a novel approach, called FedCS (Federated CrowdSourcing), to achieve privacy protection while ensuring quality. FedCS aggregates model parameters from clients to build a shared server model while keeping the training data locally on worker devices to protect data privacy. To mitigate the staleness of stragglers and boost efficiency, we introduce a semi-asynchronous federated crowdsourcing mechanism, where the parameter server performs global aggregation periodically. Moreover, due to the different frequencies of workers participating in asynchronous update, FedCS uses a staleness-aware grouping and weighted aggregation heuristic to balance the training process. To speed up the convergence rate and improve the training accuracy, FedCS deploys adaptive learning step size for worker devices by their participation frequency. We further present a task assignment algorithm to help workers choose worthy and suitable tasks for annotations and to save the budget. Extensive experiments on benchmark datasets and a real-world crowdsourcing project show that FedCS can complete secure crowdsourcing projects with high quality and low budget.

A recent trend of fair machine learning is to build a decision model subjected to causality-based fairness requirements, which concern with the causality between sensitive attributes and decisions. Almost all (if not all) solutions focus on a single fair decision model and assume no hidden confounder to model causal effects in a too simplified way. However, multiple interdependent decision models are actually used and discrimination may transmit among them. The hidden confounder is another inescapable fact and causal effects cannot be computed from observational data in the unidentifiable situation. To address these problems, we propose a method called CMFL (Causality-based Multiple Fairness Learning). CMFL parameterizes the causal model by response-function variables, whose distributions capture the randomness of causal models. CMFL treats each classifier as a soft intervention to infer the post-intervention distribution, and combines the fairness constraints with the classification loss to train multiple decision classifiers. In this way, all classifiers can make approximately fair decisions. Experiments on synthetic and benchmark datasets confirm its effectiveness, the response-function variables can deal with the unidentifiable issue and hidden confounders.

Learning the directed acyclic graph (DAG) among causal variables is a fundamental pre-task in causal discovery. Available DAG learning solutions canonically focus on homogeneous nodes with multiple variables and assume i.i.d. samples, how to learn DAG on typical attributed heterogeneous network (AHN) composed with different types of inter-dependent nodes and diverse attributes is a practical but more difficult task. In this paper, we propose HetDAG to identify DAG among nodes from heterogeneous network. HetDAG first embeds different types of node attributes and aggregates these embeddings as the node's raw representation. Then it uses contrastive learning with prior network structure to explore latent relationships between nodes and update the representation. Next, HetDAG introduces an attention-based DAG learning module that takes node representations as input to search DAG and orient edges between nodes. To the best of our knowledge, HetDAG is the first study to learn DAG on heterogeneous networks. Extensive experiments on both semi-synthetic and real data show that HetDAG can learn DAG in an efficacy way and outperforms the state-of-the-art approaches. The results on real biological networks confirm that HetDAG can find out the causal relations between lncRNAs and miRNAs.

Multiple clusterings can explore the same set of data from different perspectives by discovering different and meaningful clusterings. However, most, if not all, of the existing approaches overwhelmingly focus on the diversity between clustering subspaces, and pay much less attention on the salience of the subspaces. As a consequence, the quality of the produced clusterings is an understudied aspect of the problem. Furthermore, existing methods cannot explain the unique internal subspace structure of each clustering, and cannot incorporate multi-facet knowledge to generate different clusterings. In this paper, we propose a solution namediMClusts(interpretableMultipleClusteringsby diversified attention). iMClusts makes use of the expressive representational power of deep autoencoders and multi-head attention to generate multiple salient embedding matrices, and multiple clusterings therein. In addition, it leverages multi-facet knowledge and enhances the diversity between heads to boost the quality and diversity of multiple clusterings. Experimental results on benchmark datasets show that iMClusts can generate multiple clusterings with quality, interpretability, and diversity.

Partial multi-label learning (PML) models the scenario where each training sample is annotated with a set of candidate labels, but only a subset of them corresponds to the ground-truths. The key challenge for PML is how to minimize the negative impact of incorrect labels concealed within the candidate ones. Most existing PML solutions require abundant samples to train a noise-robust multi-label predictor. However, due to privacy, safety or ethic issues, we more often have a handful of training samples for the target task. In this paper, we propose an approach named FsPML-DA (Few-shot Partial Multi-Label Learning with Data Augmentation) to simultaneously estimate label confidence, perform data augmentation and induce multilabel classifier. Specifically, FsPML-DA disambiguates the label confidence vector of each PML sample by jointly modeling the feature and semantic similarity, label credibility of other samples and label co-occurrence. Next, FsPML-DA introduces a synthetic feature network to generate more training samples from pairs of given samples with label confidence values. FsPML-DA then leverages original and generated samples to train a noise-tolerant multi-label classifier. Extensive experiments on benchmark datasets show that FsPML-DA performs better than recent competitive PML baselines and few-shot solutions. FsPML-DA can dislodge noisy labels by mining PML data in a sensible way and the proposed data augmentation strategy effectively combats with the scarcity of few-shot training samples.

Multi-label active learning (MAL) aims to learn an accurate multi-label classifier by selecting which examples (or example-label pairs) will be annotated and reducing query effort. MAL is a more complicated and expensive process than single-label active learning, due to one example can be associated with a set of non-exclusive labels and the annotator has to scrutinize the whole example and label space to provide correct annotations. Instead of scrutinizing the whole example for annotation, we may just examine some of its subexamples with respect to a label for annotation. In this way, we can not only save the annotation cost but also speedup the annotation process. Given this observation, we introduce CMAL, a two-stage Cost-effective MAL strategy (CMAL) by querying subexamples. CMAL first selects the most informative example-label pairs by leveraging uncertainty, label correlation and label space sparsity. Specifically, the uncertainty of a label to an example can be reduced if its correlated labels already annotated to the example, and its uncertainty can be reduced also if more examples annotated to this label. Next, CMAL greedily queries the most probable positive subexample-label pairs of the selected example-label pair. In addition, we propose rCMAL to account for the representative of examples to more reliably select example-label pairs in the first stage. Extensive experiments on multi-label datasets from diverse domains show that our proposed CMAL and rCMAL can better save the query cost than state-of-the-art MAL methods. The contribution of leveraging label correlation, label sparsity, and representative for saving cost is also confirmed.

Communities in social networks evolve over time as people enter and leave the network and their activity behaviors shift. The task of predicting structural changes in communities over time is known as community evolution prediction. Existing work in this area has focused on the development of frameworks for defining events while using traditional classification methods to perform the actual prediction. We present a novel graph neural network for predicting community evolution events from structural and temporal information. The model (GNAN) includes a group-node attention component which enables support for variable-sized inputs and learned representation of groups based on member and neighbor node features. A comparative evaluation with standard baseline methods is performed and we demonstrate that our model outperforms the baselines. Additionally, we show the effects of network trends on model performance.

Crowdsourcing is a popular and relatively economic way to harness human intelligence to process computer-hard tasks. Due to diverse factors (i.e., task difficulty, worker capability, and incentives), the collected answers from various crowd workers are of different quality. Many approaches have been proposed to manage high quality answers and to reduce the budget by modelling tasks, workers, or both. However, most of the existing approaches implicitly assume that the capability of workers is fixed during the crowdsourcing process. But in practice, such capability can be improved by gradually completing easy to hard tasks, alike human beings’ intrinsic self-paced learning ability. In this paper, we investigate crowdsourcing with self-paced workers, whose capability can be gradually boosted as he/she scrutinises and completes easy to hard tasks. Our proposed SPCrowd (Self-Paced Crowd worker) first asks workers to complete a set of golden tasks with known annotations; provides feedback to assist workers with capturing the raw modes of tasks and to spark the self-paced learning, which in turn facilitates the estimation of workers’ quality and tasks’ difficulty. It then introduces a task difficulty model to quantify the difficulty of tasks and rank them from easy to hard, and a benefit maximization criterion for task assignment, which can dynamically monitor the quality of self-paced workers and assign the sorted tasks to capable workers. In this way, a worker can successfully complete hard tasks after he/she completes easier and related tasks. Experimental results on semi-simulated and real crowdsourcing projects show that SPCrowd can better control the quality and save the budget compared to competitive baselines.

The label information of training data is crucial for effective machine learning in many domains, while it is expensive to annotate data at a large-scale by domain experts. The problem was intensified by the multiplicity and incompleteness of multiview multi-label (MVML) objects, which is ignored by almost all existing multi-view multi-label active learning approaches. In this paper, we propose an incomplete multi-view multi-label active learning (iMVMAL) approach to reduce the cost of querying MVML data. iMVMAL firstly extends under-complete Autoencoder to learn the shared/individual representations of samples across/within incomplete views by an indicator matrix to indicate the missing samples of respective view. As such, the optimization of the Autoencoder’s parameters will not be impacted by the missing samples. Next, it uses the extracted shared/individual information to train multiple classifiers and to quantify the informativeness of sample-label pairs from these classifiers, from label-wise and sample-wise information also. After that, it selects the sample-label pairs with the highest informativeness for query. Empirical studies on benchmark datasets show that iMVMAL outperforms competitive baselines at the same query cost in the complete multi-view setting, and maintains its effectiveness in the incomplete multi-view setting as well.

Partial multi-label learning (PML) aims at learning a robust multi-label classifier by training on ambiguous data, where each sample is associated with a set of candidate labels, among which only a subset are valid labels. A basic premise of existing PML solutions is to obtain enough partial multi-label samples for inducing the classification model. However, when dealing with new tasks, we may only have a few PML samples for those tasks. Furthermore, existing few-shot learning approaches assume the support (training) samples are precisely labeled; as such, irrelevant labels in the candidate label set may seriously mislead the meta-learner and thus result in a compromised performance. How to achieve PML with limited few-shot support samples is an important and practical problem, but not yet well studied. In this paper, we propose an approach called FsPML (Few-shot PML) to tackle this problem. Specifically, FsPML first performs adaptive distance metric learning via an embedding network using both sample features and label semantics in the embedding space. Next it rectifies the positive and negative prototypes of each new label of the target task in the embedding space. An unseen example can then be classified via its distances to the positive and to the negative prototypes. Experimental results on widely-used multi-label datasets (MS COCO and NUS-WIDE) demonstrate that our FsPML outperforms competitive baselines across different settings, and it can quickly generalize to new tasks with fewer training samples.

Manifold regularization methods for matrix factorization rely on the cluster assumption, whereby the neighborhood structure of data in the input space is preserved in the factorization space. We argue that using the k-neighborhoods of all data points as regularization constraints can negatively affect the quality of the factorization, and propose an unsupervised and selective regularized matrix factorization algorithm to tackle this problem. Our approach jointly learns a sparse set of representatives and their neighbor affinities, and the data factorization. We further propose a fast approximation of our approach by relaxing the selectivity constraints on the data. Our proposed algorithms are competitive against baselines and state-of-the-art manifold regularization and clustering algorithms.

Multi-view multi-instance multi-label learning (M3L) can model complex objects (bags) that are composed of multiple instances, represented with heterogeneous feature views and annotated with multiple related semantic labels.Although significant progress has been made toward M3L tasks, the current solutions still focus on a single-type of complex objects, and cannot effectively mine the widely-witnessed interconnected objects of multi-types.To bridge this gap, we propose a Deep Multi-type objects Multi-view Multi-instance Multi-label Learning solution (DeepM4L) based on heterogeneous network embedding.DeepM4L first encodes the inter-and intra-relations among multi-type objects using a heterogeneous network, and performs instance neighbor embedding to learn the representation vectors of instances.Next, it obtains the instance-label score tensor for each view and uses a max pooling operation to induce the bag-label score tensor for each bag.After that, it combines bag-label scores by multi-view learning to guarantee the semantic consistency between bags of different views.Our empirical study on benchmark datasets shows that DeepM4L is significantly superior to the recent advanced baselines.

Crowdsourcing is a relatively inexpensive and efficient mechanism to collect annotations of data from the open Internet. Crowdsourcing workers are paid for the provided annotations, but the task requester usually has a limited budget. It is desirable to wisely assign the appropriate task to the right workers, so the overall annotation quality is maximized while the cost is reduced. In this article, we propose a novel task assignment strategy (CrowdWT) to capture the complex interactions between tasks and workers, and properly assign tasks to workers. CrowdWT first develops a Worker Bias Model (WBM) to jointly model the worker’s bias, the ground truths of tasks, and the task features. WBM constructs a mapping between task features and worker annotations to dynamically assign the task to a group of workers, who are more likely to give correct annotations for the task. CrowdWT further introduces a Task Difficulty Model (TDM), which builds a Kernel ridge regressor based on task features to quantify the intrinsic difficulty of tasks and thus to assign the difficult tasks to more reliable workers. Finally, CrowdWT combines WBM and TDM into a unified model to dynamically assign tasks to a group of workers and recall more reliable and even expert workers to annotate the difficult tasks. Our experimental results on two real-world datasets and two semi-synthetic datasets show that CrowdWT achieves high-quality answers within a limited budget, and has the best performance against competitive methods.<?vsp -1.5pt?>

Co-clustering aims at discovering groups of both objects and features from a given data matrix. Co-clustering ensembles can produce robust co-clusters by combining multiple base co-clusterings. However, current co-clustering ensemble solutions either ignore the constraints resulting from feature-to-feature and object-to-object relevance information, or ignore feature-to-object relevance information. In this paper, we advocate that all three information sources contribute to the achievement of good consensus solutions, and propose a co-clustering ensemble (CoCE) approach based on multiple relevance measures. CoCE first evaluates the quality of base co-clusters and consequently measures feature-to-object relevance. The latter, along with feature-to-feature and object-to-object relevance measures, contribute to the definition of a hybrid graph. The consensus process uses the resulting hybrid graph; it's formulated as a trace minimization problem and introduces a block-wise matrix multiplication technique to perform the optimization. Experimental results on various datasets show that CoCE not only frequently outperforms other related co-clustering ensembles, but also has reduced runtime cost and is more robust to poor base co-clusterings.

Bayesian bandits using Thompson Sampling have seen increasing success in recent years. Yet existing value models (of rewards) are misspecified on many real-world problem. We demonstrate this on the User Experience Optimization (UXO) problem, providing a novel formulation as a restless, sleeping bandit with unobserved confounders plus optional stopping. Our case studies show how common misspecifications can lead to sub-optimal rewards, and we provide model extensions to address these, along with a scientific model building process practitioners can adopt or adapt to solve their own unique problems. To our knowledge, this is the first study showing the effects of overdispersion on bandit explore/exploit efficacy, tying the common notions of under- and over-confidence to over- and under-exploration, respectively. We also present the first model to demonstrate that vanishing regret and fast and consistent optional stopping are achievable in restless bandits with cointegration.

Multi-view clustering aims at exploiting information from multiple heterogeneous views to promote clustering. Most previous works search for only one optimal clustering based on the predefined clustering criterion, but devising such a criterion that captures what users need is difficult. Due to the multiplicity of multi-view data, we can have meaningful alternative clusterings. In addition, the incomplete multi-view data problem is ubiquitous in real world but has not been studied for multiple clusterings. To address these issues, we introduce a deep incomplete multi-view multiple clusterings (DiMVMC) framework, which achieves the completion of data view and multiple shared representations simultaneously by optimizing multiple groups of decoder deep networks. In addition, it minimizes a redundancy term to simultaneously control the diversity among these representations and among parameters of different networks. Next, it generates an individual clustering from each of these shared representations. Experiments on benchmark datasets confirm that DiMVMC outperforms the state-of-the-art competitors in generating multiple clusterings with high diversity and quality.

Multi-typed objects Multi-view Multi-instance Multi-label Learning (M4L) deals with interconnected multi-typed objects (or bags) that are made of diverse instances, represented with heterogeneous feature views and annotated with a set of non-exclusive but semantically related labels. M4L is more general and powerful than the typical Multi-view Multi-instance Multi-label Learning (M3L), which only accommodates single-typed bags and lacks the power to jointly model the naturally interconnected multi-typed objects in the physical world. To combat with this novel and challenging learning task, we develop a joint matrix factorization based solution (M4L-JMF). Particularly, M4L-JMF firstly encodes the diverse attributes and multiple inter(intra)-associations among multi-typed bags into respective data matrices, and then jointly factorizes these matrices into low-rank ones to explore the composite latent representation of each bag and its instances (if any). In addition, it incorporates a dispatch and aggregation term to distribute the labels of bags to individual instances and reversely aggregate the labels of instances to their affiliated bags in a coherent manner. Experimental results on benchmark datasets show that M4L-JMF achieves significantly better results than simple adaptions of existing M3L solutions on this novel problem.

Partial multi-label learning (PML) aims at learning a robust multi-label classifier from partial multi-label data, where a sample is annotated with a set of candidate labels, while only a subset of those labels is valid. The existing PML algorithms generally suffer from the high computational cost when learning with large label spaces. In this paper, we introduce a PML approach (PML-LCom) that uses Label Compression to efficiently learn from partial multi-label data. PML-LCom firstly splits the observed label data matrix into a latent relevant label matrix and an irrelevant one, and then factorizes the relevant label matrix into two low-rank matrices, one encodes the compressed labels of samples, and the other explores the underlying label correlations. Next, it optimizes the coefficient matrix of the multi-label predictor with respect to the compressed label matrix. In addition, it regularizes the compressed label matrix with respect to the feature similarity of samples, and optimizes the label matrix and predictor in a coherent manner. Experimental results on both semi-synthetic and real-world PML datasets show that PML-LCom achieves a performance superior to the state-of-the-art solutions on predicting the labels of unlabeled samples with a large label space. The label compression improves both the effectiveness and efficiency, and the coherent optimization mutually benefits the label matrix and predictor.

Crowdsourcing is a relatively economic and efficient solution to collect annotations from the crowd through online platforms. Answers collected from workers with different expertise may be noisy and unreliable, and the quality of annotated data needs to be further maintained. Various solutions have been attempted to obtain high-quality annotations. However, they all assume that workers' label quality is stable over time (always at the same level whenever they conduct the tasks). In practice, workers' attention level changes over time, and the ignorance of which can affect the reliability of the annotations. In this paper, we focus on a novel and realistic crowdsourcing scenario involving attention-aware annotations. We propose a new probabilistic model that takes into account workers' attention to estimate the label quality. Expectation propagation is adopted for efficient Bayesian inference of our model, and a generalized Expectation Maximization algorithm is derived to estimate both the ground truth of all tasks and the label-quality of each individual crowd worker with attention. In addition, the number of tasks best suited for a worker is estimated according to changes in attention. Experiments against related methods on three real-world and one semi-simulated datasets demonstrate that our method quantifies the relationship between workers' attention and label-quality on the given tasks, and improves the aggregated labels.

Hashing has been widely studied for big data retrieval due to its low storage cost and fast query speed. Zero-shot hashing (ZSH) aims to learn a hashing model that is trained using only samples from seen categories, but can generalize well to samples of unseen categories. ZSH generally uses category attributes to seek a semantic embedding space to transfer knowledge from seen categories to unseen ones. As a result, it may perform poorly when labeled data are insufficient. ZSH methods are mainly designed for single-modality data, which prevents their application to the widely spread multi-modal data. On the other hand, existing cross-modal hashing solutions assume that all the modalities share the same category labels, while in practice the labels of different data modalities may be different. To address these issues, we propose a general Cross-modal Zero-shot Hashing (CZHash) solution to effectively leverage unlabeled and labeled multi-modality data with different label spaces. CZHash first quantifies the composite similarity between instances using label and feature information. It then defines an objective function to achieve deep feature learning compatible with the composite similarity preserving, category attribute space learning, and hashing coding function learning. CZHash further introduces an alternative optimization procedure to jointly optimize these learning objectives. Experiments on benchmark multi-modal datasets show that CZHash significantly outperforms related representative hashing approaches both on effectiveness and adaptability.

Multiple clustering approaches aim at exploring alternative ways of organizing a given collection of data into various clusters from different perspectives. Although multiple one-way clusterings have been studied for more than a decade, how to explore alternative two-way clusterings (or co-clusterings) still remains an untouched topic, and an important one from an application standpoint. To solve this interesting but yet unexplored topic, we assume the existence of alternative co-clusterings embedded in different subspaces and simultaneously pursue multiple co-clusterings therein. We initially specify a subspace indicator matrix for each feature subspace, and employ matrix tri-factorization to seek row-wise and column-wise cluster indicator matrices in each subspace. To ensure diversity, we quantify the redundancy between pairwise co-clusterings using the cluster indicator and the subspace indicator matrices. We further introduce a unified objective function to simultaneously account for the two pursues, and an alternating optimization solution to iteratively optimize cluster indicator and feature indicator matrices. Our empirical study shows that the proposed solution can explore multiple meaningful co-clusterings and generally achieves better results than state-of-the-art methods.

Multi-label active learning addresses the scarce labeled example problem by querying the most valuable unlabeled examples, or example-label pairs, to achieve a better performance with limited query cost. Current multi-label active learning methods require the scrutiny of the whole example in order to obtain its annotation. In contrast, one can find positive evidence with respect to a label by examining specific patterns (i.e., subexample), rather than the whole example, thus making the annotation process more efficient. Based on this observation, we propose a novel two-stage cost effective multi-label active learning framework, called CMAL. In the first stage, a novel example-label pair selection strategy is introduced. Our strategy leverages label correlation and label space sparsity of multi-label examples to select the most uncertain example-label pairs. Specifically, the unknown relevant label of an example can be inferred from the correlated labels that are already assigned to the example, thus reducing the uncertainty of the unknown label. In addition, the larger the number of relevant examples of a particular label, the smaller the uncertainty of the label is. In the second stage, CMAL queries the most plausible positive subexample-label pairs of the selected example-label pairs. Comprehensive experiments on multi-label datasets collected from different domains demonstrate the effectiveness of our proposed approach on cost effective queries. We also show that leveraging label correlation and label sparsity contribute to saving costs.

Crowdsourcing is a useful and economic approach to data annotation. To obtain annotation of high quality, various aggregation approaches have been developed, which take into account different factors that impact the quality of aggregated answers. However, existing methods generally focus on single-label (multi-class and binary) tasks, and they ignore the inter-correlation between labels, and thus may have compromised quality. In this paper, we introduce a Multi-Label answer aggregation approach based on Joint Matrix Factorization (ML-JMF). ML-JMF selectively and jointly factorizes the sample-label association matrices collected from different annotators into products of individual and shared low-rank matrices. As such, it takes advantage of the robustness of low-rank matrix approximation to noise, and reduces the impact of unreliable annotators by assigning small (zero) weights to their annotation matrices. In addition, it takes advantage of the correlation among labels by leveraging the shared low-rank matrix, and of the similarity between annotators using the individual low-rank matrices to guide the factorization. ML-JMF pursues the low-rank matrices via a unified objective function, and introduces an iterative technique to optimize it. ML-JMF finally uses the optimized low-rank matrices and weights to infer the ground-truth labels. Our experimental results on multi-label datasets show that ML-JMF outperforms competitive methods in inferring ground truth labels. Our approach can identify unreliable annotators, and is robust against their misleading answers through the assignment of small (zero) weights to their annotation.

The goal of multiple clusterings is to discover multiple independent ways of organizing a dataset into clusters. Current approaches to this problem just focus on one-way clustering. In many real-world applications, though, it's meaningful and desirable to explore alternative two-way clustering (or co-clusterings), where both samples and features are clustered. To tackle this challenge and unexplored problem, in this paper we introduce an approach, called Multiple Co-Clusterings (MultiCC), to discover non-redundant alternative co-clusterings. MultiCC makes use of matrix tri-factorization to optimize the sample-wise and feature-wise co-clustering indicator matrices, and introduces two non-redundancy terms to enforce diversity among co-clusterings. We then combine the objective of matrix tri-factorization and two non-redundancy terms into a unified objective function and introduce an iterative solution to optimize the function. Experimental results show that MultiCC outperforms existing multiple clustering methods, and it can find interesting co-clusters which cannot be discovered by current solutions.

Current efforts on multi-label learning generally assume that the given labels of training instances are noise-free. However, obtaining noise-free labels is quite difficult and often impractical, and the presence of noisy labels may compromise the performance of multi-label learning. Partial multi-label learning (PML) addresses the scenario in which each instance is annotated with a set of candidate labels, of which only a subset corresponds to the ground-truth. The PML problem is more challenging than partial-label learning, since the latter assumes that only one label is valid and may ignore the correlation among candidate labels. To tackle the PML challenge, we introduce a feature induced PML approach called fPML, which simultaneously estimates noisy labels and trains multi-label classifiers. In particular, fPML simultaneously factorizes the observed instance-label association matrix and the instance-feature matrix into low-rank matrices to achieve coherent low-rank matrices from the label and the feature spaces, and a low-rank label correlation matrix as well. The low-rank approximation of the instance-label association matrix is leveraged to estimate the association confidence. To predict the labels of unlabeled instances, fPML learns a matrix that maps the instances to labels based on the estimated association confidence. An empirical study on public multi-label datasets with injected noisy labels, and on archived proteomic datasets, shows that fPML can more accurately identify noisy labels than related solutions, and consequently can achieve better performance on predicting labels of instances than competitive methods.

Weak-label learning is an important branch of multi-label learning; it deals with samples annotated with incomplete (weak) labels. Previous work on weak-label learning mainly considers data represented by a single view. An intuitive way to leverage multiple features obtained from different views is to concatenate the features into a single vector. However, this process is not only prone to over-fitting and often results in very high time-complexity, but also ignores the potentially useful complementary information spread across the different views. In this paper, we propose an approach based on Matrix Completion for multi-view Weak-label Learning (McWL). Matrix completion (MC) has sound theoretical properties and is robust to missing values in both feature and label spaces. Our method enforces the optimization of multiple view integration and of MC-based classification within a unified objective function. Specifically, a kernel target alignment technique and the loss function of an MC-based classifier are used to jointly and iteratively adjust the weights assigned to individual views, and to optimize the classifier. McWL can selectively integrate views and is able to assign small weights to views of low quality. Extensive experiments on a broad range of datasets validate the effectiveness of our approach against competitive algorithms.

Collaborative filtering (CF) based recommender systems identify and recommend interesting items to a given user based on the user's past rating activity. These systems improve their recommendations by identifying user preferences and item related information from external sources, like reviews written by users, or concept tags shared by users about these items. These preferences are often reflected through a multi-criterion rating. In this study, we seek to improve recommender systems by integrating user preferences as side information within standard neighborhood-based and matrix factorization based methods. We assume that a user's choice of tags for an item provides additional information about the user's personal preference and additional features about the item. Since, querying users to provide tags and multi-criteria rating imposes an additional burden on the user base, we propose using collective classification to predict tags for both the users and items. We also investigate the use of active learning approaches integrated within the collective classification framework when tag information (users or items) is limited. Our experimental results on several real world datasets show the advantages of using tag-based information within the recommender systems. We are also able to show the effectiveness of collective classification algorithms in estimating user preferences and item features.

No abstract available.

Known Item Search (KIS) is a specialized task of the general multimedia search problem. It describes the scenario where a user has previously seen a video and wants to find it again in a large collection using a text description. While there exists only one correct answer to a query (or topic), the goal is to return a ranked list of videos most likely to satisfy the request. This search problem includes content from speech, visual, and meta-data, and it is not clear how the individual modalities should be combined in the final result. Reranking models have been shown to be effective in problems such as image search, but the single ground truth video for a topic presents a challenge for building a model. In this paper, we propose a semi-supervised rank learning approach to the multimedia problem. We use a large training set of topics and ground truth videos to learn a pairwise ranking model based on gradient boosted regression trees. We define a learning feature space that consists of features derived from topics, videos, and topic-video dependent results. To overcome the KIS class imbalance problem, a set of pseudo positive training examples are identified from each of the multimedia modalities. This semi-supervised approach uses a ground truth video to select similar videos in each of the individual modalities. We then model the similarities as a graph and use a K-Step Markov approach to estimate the importance of nodes in the graph relative to the truth root node.

The mean shift algorithm is a nonparametric clustering technique that does not make assumptions on the number of clusters and on their shapes. It achieves this goal by performing kernel density estimation, and iteratively locating the local maxima of the kernel mixture. The set of points that converge to the same mode defines a cluster. While appealing, the performance of the mean shift algorithm significantly deteriorates with high dimensional data due to the sparsity of the input space. In addition, noisy features can create challenges for the mean shift procedure. In this paper we extend the mean shift algorithm to overcome these limitations, while maintaining its desirable properties. To achieve this goal, we first estimate the relevant subspace for each data point, and then embed such information within the mean shift algorithm, thus avoiding computing distances in the full dimensional input space. The resulting approach achieves the best-of-two-worlds: effective management of high dimensional data and noisy features, while preserving a nonparametric nature. Our approach can also be combined with random sampling to speedup the clustering process with large scale data, without sacrificing accuracy. Extensive experimental results on both synthetic and real-world data demonstrate the effectiveness of the proposed method.

Ensemble clustering, also known as consensus clustering, aims to generate a stable and robust clustering through the consolidation of multiple base clusterings. In recent years many ensemble clustering methods have been proposed, most of which treat each clustering and each object as equally important. Some approaches make use of weights associated with clusters, or with clusterings, when assembling the different base clusterings. Boosting algorithms developed for classification have also led to the idea of considering weighted objects during the clustering process. However, not much effort has been put towards incorporating weighted objects into the consensus process. To fill this gap, in this paper we propose an approach called Weighted-Object Ensemble Clustering (WOEC). We first estimate how difficult it is to cluster an object by constructing the co-association matrix that summarizes the base clustering results, and we then embed the corresponding information as weights associated to objects. We propose three different consensus techniques to leverage the weighted objects. All three reduce the ensemble clustering problem to a graph partitioning one. We present extensive experimental results which demonstrate that our WOEC approach outperforms state-of-the-art consensus clustering methods and is robust to parameter settings.

Advances in biotechnology have made available multitudes of heterogeneous proteomic and genomic data. Integrating these heterogeneous data sources, to automatically infer the function of proteins, is a fundamental challenge in computational biology. Several approaches represent each data source with a kernel (similarity) function. The resulting kernels are then integrated to determine a composite kernel, which is used for developing a function prediction model. Proteins are also found to have multiple roles and functions. As such, several approaches cast the protein function prediction problem within a multi-label learning framework. In our work we develop an approach that takes advantage of several unlabeled proteins, along with multiple data sources and multiple functions of proteins. We develop a graph-based transductive multi-label classifier (TMC) that is evaluated on a composite kernel, and also propose a method for data integration using the ensemble framework, called transductive multi-label ensemble classifier (TMEC). The TMEC approach trains a graph-based multi-label classifier for each individual kernel, and then combines the predictions of the individual models. Our contribution is the use of a bi-relational directed graph that captures relationships between pairs of proteins, between pairs of functions, and between proteins and functions. We evaluate the ability of TMC and TMEC to predict the functions of proteins by using two yeast datasets. We show that our approach performs better than recently proposed protein function prediction methods on composite and multiple kernels.

A nonparametric Bayesian approach to co-clustering ensembles is presented. Similar to clustering ensembles, co-clustering ensembles combine various base co-clustering results to obtain a more robust consensus co-clustering. To avoid pre-specifying the number of co-clusters, we specify independent Dirichlet process priors for the row and column clusters. Thus, the numbers of row- and column-clusters are unbounded a priori; the actual numbers of clusters can be learned a posteriori from observations. Next, to model non-independence of row- and column-clusters, we employ a Mondrian Process as a prior distribution over partitions of the data matrix. As a result, the co-clusters are not restricted to a regular grid partition, but form nested partitions with varying resolutions. The empirical evaluation demonstrates the effectiveness of nonparametric Bayesian co-clustering ensembles and their advantages over traditional co-clustering methods.

Projective Clustering Ensembles (PCE) are a very recent advance in data clustering research which combines the two powerful tools of clustering ensembles and projective clustering.Specifically, PCE enables clustering ensemble methods to handle ensembles composed by projective clustering solutions. PCE has been formalized as an optimization problem with either a two-objective or a single-objective function. Two-objective PCE has shown to generally produce more accurate clustering results than its single-objective counterpart, although it can handle the object-based and feature-based cluster representations only independently of one other. Moreover, both the early formulations of PCE do not follow any of the standard approaches of clustering ensembles, namely instance-based, cluster-based, and hybrid. In this paper, we propose an alternative formulation to the PCE problem which overcomes the above issues. We investigate the drawbacks of the early formulations of PCE and define a new single-objective formulation of the problem. This formulation is capable of treating the object- and feature-based cluster representations as a whole, essentially tying them in a distance computation between a projective clustering solution and a given ensemble. We propose two cluster-based algorithms for computing approximations to the proposed PCE formulation, which have the common merit of conforming to one of the standard approaches of clustering ensembles. Experiments on benchmark datasets have shown the significance of our PCE formulation, as both the proposed heuristics outperform existing PCE methods.

Projective Clustering Ensembles (PCE) has recently been formulated to solve the problem of deriving a robust projective consensus clustering from an ensemble of projective clustering solutions. PCE is formalized as an optimization problem with either a two-objective or a single-objective function, depending on whether the object-based and the feature-based representations of the clusters in the ensemble are treated separately. A major result in is that single-objective PCE outperforms two-objective PCE in terms of efficiency, at the cost of lower accuracy in consensus clustering. In this paper, we enhance the single-objective PCE formulation, with the ultimate goal of providing more effective formulations capable of reducing the accuracy gap with the two-objective counterpart, while maintaining the efficiency advantages. We provide theoretical insights into the single-objective function, and introduce two heuristics that overcome the major limitations of the previous single-objective PCE formulation. Experimental evidence has demonstrated the significance of our proposed heuristics. In fact, results have not only confirmed a far better efficiency w.r.t. two-objective PCE, but have also shown the claimed improvements in accuracy of the consensus clustering obtained by the new single-objective PCE.

Recent advances in data clustering concern clustering ensembles and projective clustering methods, each addressing different issues in clustering problems. In this paper, we consider for the first time the projective clustering ensemble (PCE) problem, whose main goal is to derive a proper projective consensus partition from an ensemble of projective clustering solutions. We formalize PCE as an optimization problem which does not rely on any particular clustering ensemble algorithm, and which has the ability to handle hard as well as soft data clustering, and different feature weightings. We provide two formulations for PCE, namely a two-objective and a single-objective problem, in which the object-based and feature-based representations of the ensemble solutions are taken into account differently. Experiments have demonstrated that the proposed methods for PCE show clear improvements in terms of accuracy of the output consensus partition.

Cluster ensembles offer a solution to challenges inherent to clustering arising from its ill-posed nature. Cluster ensembles can provide robust and stable solutions by leveraging the consensus across multiple clustering results, while averaging out emergent spurious structures that arise due to the various biases to which each participating algorithm is tuned. In this article, we address the problem of combining multiple weighted clusters that belong to different subspaces of the input space. We leverage the diversity of the input clusterings in order to generate a consensus partition that is superior to the participating ones. Since we are dealing with weighted clusters, our consensus functions make use of the weight vectors associated with the clusters. We demonstrate the effectiveness of our techniques by running experiments with several real datasets, including high-dimensional text data. Furthermore, we investigate in depth the issue of diversity and accuracy for our ensemble methods. Our analysis and experimental results show that the proposed techniques are capable of producing a partition that is as good as or better than the best individual clustering.

This paper presents Online Topic Model (OLDA), a topic model that automatically captures the thematic patterns and identifies emerging topics of text streams and their changes over time. Our approach allows the topic modeling framework, specifically the Latent Dirichlet Allocation (LDA) model, to work in an online fashion such that it incrementally builds an up-to-date model (mixture of topics per document and mixture of words per topic) when a new document (or a set of documents) appears. A solution based on the Empirical Bayes method is proposed. The idea is to incrementally update the current model according to the information inferred from the new stream of data with no need to access previous data. The dynamics of the proposed approach also provide an efficient mean to track the topics over time and detect the emerging topics in real time. Our method is evaluated both qualitatively and quantitatively using benchmark datasets. In our experiments, the OLDA has discovered interesting patterns by just analyzing a fraction of data at a time. Our tests also prove the ability of OLDA to align the topics across the epochs with which the evolution of the topics over time is captured. The OLDA is also comparable to, and sometimes better than, the original LDA in predicting the likelihood of unseen documents.

Traditional approaches to document classification requires labeled data in order to construct reliable and accurate classifiers. Unfortunately, labeled data are seldom available, and often too expensive to obtain. Given a learning task for which training data are not available, abundant labeled data may exist for a different but related domain. One would like to use the related labeled data as auxiliary information to accomplish the classification task in the target domain. Recently, the paradigm of transfer learning has been introduced to enable effective learning strategies when auxiliary data obey a different probability distribution. A co-clustering based classification algorithm has been previously proposed to tackle cross-domain text classification. In this work, we extend the idea underlying this approach by making the latent semantic relationship between the two domains explicit. This goal is achieved with the use of Wikipedia. As a result, the pathway that allows to propagate labels between the two domains not only captures common words, but also semantic concepts based on the content of documents. We empirically demonstrate the efficacy of our semantic-based approach to cross-domain classification using a variety of real data.

Document classification presents difficult challenges due to the sparsity and the high dimensionality of text data, and to the complex semantics of the natural language. The traditional document representation is a word-based vector (Bag of Words, or BOW), where each dimension is associated with a term of the dictionary containing all the words that appear in the corpus. Although simple and commonly used, this representation has several limitations. It is essential to embed semantic information and conceptual patterns in order to enhance the prediction capabilities of classification algorithms. In this paper, we overcome the shortages of the BOW approach by embedding background knowledge derived from Wikipedia into a semantic kernel, which is then used to enrich the representation of documents. Our empirical evaluation with real data sets demonstrates that our approach successfully achieves improved classification accuracy with respect to the BOW technique, and to other recently developed methods.

Clustering, as an unsupervised learning process is a challenging problem, especially in cases of high-dimensional datasets. Clustering result quality can benefit from user constraints and objective validity assessment. In this article, we propose a semisupervised framework for learning the weighted Euclidean subspace, where the best clustering can be achieved. Our approach capitalizes on: (i) user constraints; and (ii) the quality of intermediate clustering results in terms of their structural properties. The proposed framework uses the clustering algorithm and the validity measure as its parameters. We develop and discuss algorithms for learning and tuning the weights of contributing dimensions and defining the “best” clustering obtained by satisfying user constraints. Experimental results on benchmark datasets demonstrate the superiority of the proposed approach in terms of improved clustering accuracy.

Outlier detection can uncover malicious behavior in fields like intrusion detection and fraud analysis. Although there has been a significant amount of work in outlier detection, most of the algorithms proposed in the literature are based on a particular definition of outliers (e.g., density-based), and use ad-hoc thresholds to detect them. In this paper we present a novel technique to detect outliers with respect to an existing clustering model. However, the test can also be successfully utilized to recognize outliers when the clustering information is not available. Our method is based on Transductive Confidence Machines, which have been previously proposed as a mechanism to provide individual confidence measures on classification decisions. The test uses hypothesis testing to prove or disprove whether a point is fit to be in each of the clusters of the model. We experimentally demonstrate that the test is highly robust, and produces very few misdiagnosed points, even when no clustering information is available. Furthermore, our experiments demonstrate the robustness of our method under the circumstances of data contaminated by outliers. We finally show that our technique can be successfully applied to identify outliers in a noisy data set for which no information is available (e.g., ground truth, clustering structure, etc.). As such our proposed methodology is capable of bootstrapping from a noisy data set a clean one that can be used to identify future outliers.

Cluster ensembles offer a solution to challenges inherent to clustering arising from its ill-posed nature. Cluster ensembles can provide robust and stable solutions by leveraging the consensus across multiple clustering results, while averaging out emergent spurious structures that arise due to the various biases to which each participating algorithm is tuned. In this paper, we address the problem of combining multiple weighted clusters which belong to different subspaces of the input space. We leverage the diversity of the input clusterings in order to generate a consensus partition that is superior to the participating ones. Since we are dealing with weighted clusters, our consensus function makes use of the weight vectors associated with the clusters. The experimental results show that our ensemble technique is capable of producing a partition that is as good as or better than the best individual clustering.

In this paper, we propose a semi-supervised framework for learning a weighted Euclidean subspace, where the best clustering can be achieved. Our approach capitalizes on user-constraints and the quality of intermediate clustering results in terms of its structural properties. It uses the clustering algorithm and the validity measure as parameters.

In this paper, we first propose a global unsupervised feature selection approach for text, based on frequent itemset mining. As a result, each document is represented as a set of words that co-occur frequently in the given corpus of documents. We then introduce a locally adaptive clustering algorithm, designed to estimate (local) word relevance and, simultaneously, to group the documents. We present experimental results to demonstrate the feasibility of our approach. Furthermore, the analysis of the weights credited to terms provides evidence that the identified keywords can guide the process of label assignment to clusters. We take into consideration both spam email filtering and general classification datasets. Our analysis of the distribution of weights in the two cases provides insights on how the spam problem distinguishes from the general classification case.

Recent empirical work has shown that combining predictors can lead to significant reduction in generalization error. Unfortunately, many combining methods do not improve nearest neighbor (NN) classifiers at all. This is because NN methods are very robust with respect to variations of a data set. In contrast, they are sensitive to input features. We exploit the instability of NN classifiers with respect to different choices of features to generate an effective and diverse set of NN classifiers. Interestingly, the approach takes advantage of the high dimensionality of the data. We investigate techniques to decorrelate errors while keeping the individual classifiers accurate. We analyze the results both in terms of error rates and error correlations. The experimental results show that our technique can offer significant performance improvements with respect to competitive methods.

Automatic classification of documents is an important area of research with many applications in the fields of document searching, forensics and others. Methods to perform classification of text rely on the existence of a sample of documents whose class labels are known. However, in many situations, obtaining this sample may not be an easy (or even possible) task. Consider for instance, a set of documents that is returned as a result of a query. If we want to separate the documents that are truly relevant to the query from those that are not, it is unlikely that we will have at hand labelled documents to train classification models to perform this task. In this paper we focus on the classification of an unlabelled set of documents into two classes: relevant and irrelevant, given a topic of interest. By dividing the set of documents into buckets (for instance, answers returned by different search engines), and using association rule mining to find common sets of words among the buckets, we can efficiently obtain a sample of documents that has a large percentage of relevant ones. (I.e., a high “purity”.) This sample can be used to train models to classify the entire set of documents. We prove, via experimentation, that our method is capable of filtering relevant documents even in adverse conditions where the percentage of irrelevant documents in the buckets is relatively high.

Clustering suffers from the curse of dimensionality, and similarity functions that use all input features with equal relevance may not be effective. We introduce an algorithm that discovers clusters in subspaces spanned by different combinations of dimensions via local weightings of features. This approach avoids the risk of loss of information encountered in global dimensionality reduction techniques, and does not assume any data distribution model. Our method associates to each cluster a weight vector, whose values capture the relevance of features within the corresponding cluster. We experimentally demonstrate the gain in perfomance our method achieves, using both synthetic and real data sets. In particular, our results show the feasibility of the proposed technique to perform simultaneous clustering of genes and conditions in microarray data.

Automatic classification of documents is an important area of research with many applications in the fields of document searching, forensics and others. Methods to perform classification of text rely on the existence of a sample of documents whose class labels are known. However, in many situations, obtaining this sample may not be an easy (or even possible) task. We focus on the classification of unlabelled documents into two classes: relevant and irrelevant, given a topic of interest. By dividing the set of documents into buckets (for instance, answers returned by different search engines), and using association rule mining to find common sets of words among the buckets, we can efficiently obtain a sample of documents that has a large percentage of relevant ones. This sample can be used to train models to classify the entire set of documents. We prove, via experimentation, that our method is capable of filtering relevant documents even in adverse conditions where the percentage of irrelevant documents in the buckets is relatively high.

We study the use of kernel subspace methods for learning low-dimensional representations for classification. We propose a kernel pooled local discriminant subspace method and compare it against several competing techniques: generalized Fisher discriminant analysis (GDA) and kernel principal components analysis (KPCA) in classification problems. We evaluate the classification performance of the nearest-neighbor rule with each subspace representation. The experimental results demonstrate the efficacy of the kernel pooled local subspace method and the potential for substantial improvements over competing methods such as KPCA in some classification problems.

In this paper we address the issue of using local embeddings for data visualization in two and three dimensions, and for classification. We advocate their use on the basis that they provide an efficient mapping procedure from the original dimension of the data, to a lower intrinsic dimension. We depict how they can accurately capture the user's perception of similarity in high-dimensional data for visualization purposes. Moreover, we exploit the low-dimensional mapping provided by these embeddings, to develop new classification techniques, and we show experimentally that the classification accuracy is comparable (albeit using fewer dimensions) to a number of other classification procedures.

The nearest neighbor technique is a simple and appealing method to address classification problems. It relies on the assumption of locally constant class conditional probabilities. This assumption becomes invalid in high dimensions with a finite number of examples due to the curse of dimensionality. Severe bias can be introduced under these conditions when using the nearest neighbor rule. The employment of a local adaptive metric becomes crucial in order to keep class conditional probabilities close to uniform, and therefore to minimize the bias of estimates. We propose a technique that computes a locally flexible metric by means of Support Vector Machines (SVMs). The maximum margin boundary found by the SVM is used to determine the most discriminant direction over the query's neighborhood. Such direction provides a local weighting scheme for input features. We present experimental evidence, together with a formal justification, of classification performance improvement over the SVM algorithm alone and over a variety of adaptive learning schemes, by using both simulated and real data sets. Moreover, the proposed method has the important advantage of superior efficiency over the most competitive technique used in our experiments.

SVMs (support vector machines) suffer from the problem of large memory requirement and CPU time when trained in batch mode on large data sets. We overcome these limitations, and at the same time make SVMs suitable for learning with data streams, by constructing incremental learning algorithms. We first introduce and compare different incremental learning techniques, and show that they are capable of producing performance results similar to the batch algorithm, and in some cases superior condensation properties. We then consider the problem of training SVMs using stream data. Our objective is to maintain an updated representation of recent batches of data. We apply incremental schemes to the problem and show that their accuracy is comparable to the batch algorithm.