This paper proposes a new approach to accelerate spectral norm estimation for a kernel matrix of n data points. Our key intuition is that, by applying the seminal random feature technique, we can well estimate the norm without computing or operating on the n-by-n kernel matrix but only an n-by-q random feature matrix with q ≪ n features, thereby significantly reducing the estimation time from O(n2) to O(nq).Technically, our analysis suggests the spectral norm of a kernel matrix can be approximated by that of its corresponding random feature matrix with an $\tilde O\left( {\ln n/\sqrt q } \right)$ relative norm approximation error. This is comparable to the relative norm estimation error of power iteration (PI), a popular efficient norm estimation method, and suggests our method can be integrated with PI to further accelerate norm estimation without deteriorating the estimation accuracy. Based on these insights, we design a random feature-based power iteration (RFPI) estimator for the kernel matrix spectral norm. Experimental results on two real-world datat sets show RFPI has significantly less estimation time than PI while maintaining competitive estimation accuracy.

This paper presents a new data-dependent random projection method D2RP for least square regressions, which maps data into the row space of a randomly mapped training data matrix. Our theoretical analysis suggests D2RP may not preserve pairwise data distance as well as its data-independent ancestors, but preserves enough information for reconstructing the training data. Our further analysis shows least square regression in the D2RP projected space has an O(e−k/n) empirical excess risk that decays exponentially faster as k increases, partly suggesting its high dimension efficiency. On the practical side, we apply D2RP to speed up least square regression, kernel ridge regression and ensemble regression. Experimental results on real-world data sets show it achieves the best tradeoff between computation efficiency and dimension efficiency compared to multiple baselines methods.

Multimodal fake news detection (MFND) has received widespread attention. As a typical multimodal task, MFND is troubled by modality imbalance, where the dominant modality suppresses other modalities during the optimization process. Meanwhile, the social credibility maintains the amount of fake news less than that of real news, which causes class imbalance. We call MFND with intertwined influence of modality imbalance and class imbalance as dual imbalanced MFND, i.e., DI-MFND, which has not been well studied. In this article, we propose an approach called prototype-based fully balanced learning (PFBL) for DI-MFND. Specifically, our model contains three main parts. 1) The prototype-based modality-balanced learning (PMB) part, which constructs modality prototypes for each modality. It designs the prototype-based unimodal loss to enhance the intraclass compactness of the poorly performing modality and a constrained gradient optimization strategy to suppress the dominant modality for optimization. 2) The prototype-based class-balanced learning (PCB) part constructs class prototypes. A prototype-oriented discriminative enhancement loss is designed to effectively align samples with corresponding prototypes and increase the inter-class distance, thus enhancing the separability of different categories. 3) The multimodal fusion and classification (MFC) part employs a cross-transformer block to perform interaction between modalities and further integrates features of different modalities by attention mechanism. We propose a joint updating strategy for modality prototypes and class prototypes. Extensive experiments on three widely-used news datasets demonstrate that our approach outperforms state-of-the-art approaches.

Labeling sufficient data for supervised learning remains an open challenge in social network analysis. An alternative is to collect self-labeled data, i.e. the data labeled by their owners. Emmery et al show that standard models can be trained and perform well on self-labeled data, suggesting the effectiveness of this approach. In this paper, we argue self-labeled data may not be representative of the population. Taking Twitter demographic prediction as an example, we show the popular FastText model standardly trained on self-labeled data does not generalize well on random testing samples. We then present a new learner DeFastText that aims to correct data bias using the kernel means matching technique. In experiment, we show it achieves lower generalization errors than FastText. This research raises an attention of the data bias problem when learning from self-labeled data in social network analysis.

We propose a model-agnostic randomized learning framework based on Random Hypothesis Subspace Sampling (RHSS). Given any hypothesis class, it randomly samples $k$ hypotheses and learns a near-optimal model from their span by simply solving a linear least square problem in $O(n k^2)$ time, where $n$ is the number of training instances. On the theory side, we derive the performance guarantee of RHSS from a generic subspace approximation perspective, leveraging properties of metric entropy and random matrices. On the practical side, we apply the RHSS framework to learn kernel, network and tree based models. Experimental results show they converge efficiently as $k$ increases and outperform their model-specific counterparts including random Fourier feature, random vector functional link and extra tree on real-world data sets.

Active learning (AL) aims to actively label training data for supervised learners to efficiently improve accuracy of the trained models. However, traditional AL techniques ignore model fairness, which is an important social norm in modern machine learning applications. In this paper, we propose the first fairness-aware active learning technique for decoupled model called D-FA2L. It labels data that receive disagreed predictions from the decoupled models, and we hypothesize it can simultaneously improve model fairness and model accuracy. We present theoretical justification of D-FA2L, proving it can reduce model unfairness under proper conditions. In experiments, we show D-FA2L can reduce model unfairness effectively, and the reduction is more efficient than both classic and state-of-the-art AL techniques on three data sets. In the meantime, D-FA2L is able to maintain similar improvement rate on model accuracy.

Existing studies on individual fairness focus on the passive setting and typically require $O(\frac{1}{\varepsilon^2})$ labeled instances to achieve an $\varepsilon$ bias budget. In this paper, we build on the elegant Approximately Metric-Fair (AMF) learning framework and propose an active AMF learner that can provably achieve the same budget with only $O(\log \frac{1}{\varepsilon})$ labeled instances. To our knowledge, this is a first and substantial improvement of the existing sample complexity for achieving individual fairness. Through experiments on three data sets, we show the proposed active AMF learner improves fairness on linear and non-linear models more efficiently than its passive counterpart as well as state-of-the-art active learners, while maintaining a comparable accuracy. To facilitate algorithm design and analysis, we also design a provably equivalent form of the approximate metric fairness based on uniform continuity instead of the existing almost Lipschitz continuity.

In the evasion attacks against deep neural networks (DNN), the attacker generates adversarial instances that are visually indistinguishable from benign samples and sends them to the target DNN to trigger misclassifications. In this paper, we propose a novel multi-view adversarial image detector, namely Argos, based on a novel observation. That is, there exist two “souls” in an adversarial instance, i.e., the visually unchanged content, which corresponds to the true label, and the added invisible perturbation, which corresponds to the misclassified label. Such inconsistencies could be further amplified through an autoregressive generative approach that generates images with seed pixels selected from the original image, a selected label, and pixel distributions learned from the training data. The generated images (i.e., the “views”) will deviate significantly from the original one if the label is adversarial, demonstrating inconsistencies that Argos expects to detect. To this end, Argos first amplifies the discrepancies between the visual content of an image and its misclassified label induced by the attack using a set of regeneration mechanisms and then identifies an image as adversarial if the reproduced views deviate to a preset degree. Our experimental results show that Argos significantly outperforms two representative adversarial detectors in both detection accuracy and robustness against six well-known adversarial attacks. Code is available at: https://github.com/sohaib730/Argos-Adversarial_Detection

Learning a fair prediction model is an important research problem with profound societal impacts. Most approaches assume free access to the sensitive demographic data, whereas these data are becoming restricted to use by privacy regulations. Existing solutions are broadly based on multi-party computation or demographic proxy, but each direction has its own limits in certain scenarios.

Traditional anomaly detectors examine a single view of instances and cannot discover multi-view anomalies, i.e., instances that exhibit inconsistent behaviors across different views. To tackle the problem, several multi-view anomaly detectors have been developed recently, but they are all transductive and unsupervised thus may suffer some challenges. In this paper, we propose a novel inductive semi-supervised Bayesian multi-view anomaly detector. Specifically, we first present a generative model for normal data. Then, we build a hierarchical Bayesian model, by first assigning priors to all parameters and latent variables, and then assigning priors over the priors. Finally, we employ variational inference to approximate the posterior of the model and evaluate anomalous scores of multi-view instances. In the experiment, we show the proposed Bayesian detector consistently outperforms state-of-the-art counterparts across several public data sets and three well-known types of multi-view anomalies. In theory, we prove the inferred Bayesian estimator is consistent and derive a proximate sample complexity for the proposed anomaly detector.

In cheminformatics, compound-target binding profiles has been a main source of data for research. For data repositories that only provide positive profiles, a popular assumption is that unreported profiles are all negative. In this paper, we caution the audience not to take this assumption for granted, and present empirical evidence of its ineffectiveness from a machine learning perspective. Our examination is based on a setting where binding profiles are used as features to train predictive models; we show (1) prediction performance degrades when the assumption fails and (2) explicit recovery of unreported profiles improves prediction performance. In particular, we propose a framework that jointly recovers profiles and learns predictive model, and show it achieves further performance improvement. The presented study not only suggests applying matrix recovery methods to recover unreported profiles, but also initiates a new missing feature problem which we called Learning with Positive and Unknown Features.

Fair machine learning has become a significant research topic with broad societal impact. However, most fair learning methods require direct access to personal demographic data, which is increasingly restricted to use for protecting user privacy (e.g. by the EU General Data Protection Regulation). In this paper, we propose a distributed fair learning framework for protecting the privacy of demographic data. We assume this data is privately held by a third party, which can communicate with the data center (responsible for model development) without revealing the demographic information. We propose a principled approach to design fair learning methods under this framework, exemplify four methods and show they consistently outperform their existing counterparts in both fairness and accuracy across two real-world data sets. We theoretically analyze the framework, and prove it can learn models with high fairness or high accuracy, with their trade-offs balanced by a threshold variable.

Fair machine learning is a topical problem. It studies how to mitigate unethical bias against minority people in model prediction. A promising solution is ensemble learning - Nina et al [1] first argue that one can obtain a fair model by bagging a set of standard models. However, they do not present any empirical evidence or discuss effective ensemble strategy for fair learning. In this paper, we propose a new ensemble strategy for fair learning. It adopts the AdaBoost framework, but unlike AdaBoost that upweights mispredicted instances, it upweights unfairly predicted instances which we identify using a variant of Luong's k-NN based situation testing method [2]. Through experiments on two real-world data sets, we show our proposed strategy achieves higher fairness than the bagging strategy discussed by Nina et al and several baseline methods. Our results also suggest standard ensemble strategies may not be sufficient for improving fairness.

In recent years, there have been significant efforts on mitigating unethical demographic biases in machine learning methods. However, very little work is done for kernel methods. In this paper, we propose a novel fair kernel regression method via fair feature embedding (FKR-F2E) in kernel space. Motivated by prior works feature processing for fair learning and feature selection for kernel methods, we propose to learn fair feature embeddings in kernel space, where the demographic discrepancy of feature distributions is minimized. Through experiments on three public real-world data sets, we show the proposed FKR-F^2E achieves significantly lower prediction disparity compared with the state-of-the-art fair kernel regression method and several other baseline methods.

In music classification tasks, Convolutional Recurrent Neural Network (CRNN) has achieved state-of-the-art performance on several data sets. However, the current CRNN technique only uses RNN to extract spatial dependency of music signal in its time dimension but not its frequency dimension. We hypothesize the latter can be additionally exploited to improve classification performance. In this paper, we propose an improved technique called CRNN in Time and Frequency dimensions (CRNN-TF), which captures spatial dependencies of music signal in both time and frequency dimensions in multiple directions. Experimental studies on three real-world music data sets show that CRNN-TF consistently outperforms CRNN and several other state-of-the-art deep learning-based music classifiers. Our results also suggest CRNN-TF is transferable on small music data sets via the fine-tuning technique.

Semi-supervised multi-view feature learning (SMFL) is a feasible solution for webpage classification. However, how to fully extract the complementarity and correlation information effectively under semi-supervised setting has not been well studied. In this paper, we propose a semi-supervised multi-view individual and sharable feature learning (SMISFL) approach, which jointly learns multiple view-individual transformations and one sharable transformation to explore the view-specific property for each view and the common property across views. We design a semi-supervised multi-view similarity preserving term, which fully utilizes the label information of labeled samples and similarity information of unlabeled samples from both intra-view and inter-view aspects. To promote learning of diversity, we impose a constraint on view-individual transformation to make the learned view-specific features to be statistically uncorrelated. Furthermore, we train a linear classifier, such that view-specific and shared features can be effectively combined for classification. Experiments on widely used webpage datasets demonstrate that SMISFL can significantly outperform state-of-the-art SMFL and webpage classification methods.

To evaluate prediction qualities of machine learning models, it is typically assumed testing samples are labeled. However, testing labels are not always available in practice. A traditional solution is to approximate prediction qualities on testing samples by the qualities on labeled training samples. But this may be limited in that it completely ignores testing samples. In this paper, we present a new approach to estimate prediction qualities on unlabeled testing sample, based on the reverse testing framework [1]. We evaluate the approach with various quality metrics in classification and anomaly detection tasks, and over numerous real-world data sets. Experimental results show the proposed approach gives a more accurate estimate of prediction qualities on testing sample than those on training samples.

Automatic social circle detection in ego-networks is a fundamentally important task for social network analysis. So far, most studies focused on how to detect overlapping circles or how to detect based on both network structure and node profiles. This paper asks an orthogonal research question: how to detect circles by leveraging multiple views of the network structure? As a first step, we crawl ego networks from Twitter and model them by six views, including user relationships, user interactions, and user content. We then apply both standard and our modified multi-view spectral clustering techniques to detect circles on these ego-networks. By extensive automatic and manual evaluations, we deliver two major findings: first, multi-view clustering techniques detect better circles than single-view clustering methods; second, our modified clustering technique which presumes sparse networks are incomplete detects better circles than the standard clustering technique which ignores such potential incompleteness. In particular, the second finding makes us conjecture a direct application of standard clustering on potentially incomplete networks may yield biased results. We lightly investigate this issue by deriving a bias upper bound that integrates theories of spectral clustering and matrix perturbation, and discussing how the bound may be affected by several network characteristics.

The study of compound-target binding profiles has been a central theme in cheminformatics. For data repositories that only provide positive binding profiles, a popular assumption is all unreported profiles are negative. In this paper, we caution audience not to take such assumption for granted. Under a problem setting where binding profiles are used as features to train predictive models, we present empirical evidence that (1) predictive performance degrades when the assumption fails and (2) specific recovery of unreported profiles improves predictive performance. In particular, we propose a joint framework of profile recovery and supervised learning, which shows further performance improvement. The presented study not only calls for more careful treatment of unreported profiles in cheminformatics, but also initiates a new machine learning problem as we called “Learning with Positive and Unknown Features”.

Drug-Target interaction prediction has significantly sped up the process of drug discovery. However, existing studies focused on a centralized analytic framework, which may have many limitations when applying on the modern distributed data environments. In this paper, we present a distributed and privatized framework for drug-target interaction prediction, which assumes distributed repositories are stored on and analyzed by local computers which could exchange privatized information for improving their own prediction performance. Under this framework, we propose a `conquer-and-divide' style prediction approach based on the recently introduced matrix factorization technique, and demonstrated its effectiveness on real-world cheminformatics data sets.

Collective Matrix Factorization (CMF) is a popular model for the joint matrix completion task, but limited by its strong assumption that all matrices share the same low rank structure. Recently, a promising alternative model was proposed with a relaxed assumption that matrix structures are partially shared. We refer it as Partially Collective Matrix Factorization (P-CMF). This paper presents a first PAC generalization error bound for joint matrix completion based on the P-CMF model. Our contributions are tri-facet. First, we derive a new PAC bound for single matrix completion based on the factorization model, which fundamentally improves the existing PAC bound in multiple aspects. Based on it, we then derive the first PAC bound for joint matrix completion based on the P-CMF model. This not only justifies the theoretical soundness of P-CMF, but also reveals its several insights. Based on it, we finally present a model construction criterion for designing P-CMF based methods, which specifies the degrees of shared and non-shared matrix structures. We demonstrate the effectiveness of this criterion in simulation.

Many classification problems involve instances that are unlabeled, multi-view and multi-class. However, few technique has been benchmarked for this complex scenario, with a notable exception that combines co-trained naive bayes (CoT-NB) with BCH coding. In this paper, we benchmark the performance of co-regularized least square regression (CoR-LS) for semi-supervised multi-view multi-class classification. We find it performed consistently and significantly better than CoT-NB over eight data sets at different scales. We also find for CoR-LS identity coding is optimal on large data sets and BCH coding is optimal on small data sets. Optimal scoring, a data-dependent coding scheme, often provides near-optimal performance.

Active matrix completion (AMC) is an effective approach to improve the performance of matrix completion. It actively acquires certain missing entries of a target matrix, with the aim of quickly improving the completion accuracy of the rest. Although this topic is attracting an increasing attention, all existing solutions are heuristic. In this paper, we propose a new active matrix completion approach called Factor-Disagreed AMC (FDAMC), with provably performance guarantee. It is an extension of the popular disagreement-based active statistical learning to the matrix completion task, at both methodological and theoretical levels. Specifically, FDAMC learns two factorization models to complete the matrix, and acquires those missing entries disagreed by the two models in the completion. By employing and modifying the PAC theory, we prove the sample complexity of this approach. A FDAMC algorithm is also presented, with some heuristics included. Finally, we present proof-of-concept experiments and demonstrate the effectiveness of FDAMC on both synthetic and real-world data sets.

In semi-supervised multi-view learning, unlabeled sample complexity (u.s.c.) specifies the size of unlabeled training sample that guarantees a desired learning error. In this paper, we improve the state-of-art u.s.c. from O(1/ε) to O(log 1/ε) for small error ε, under mild conditions. To obtain the improved result, as a primary step we prove a connection between the generalization error of a classifier and its incompatibility, which measures the fitness between the classifier and the sample distribution. We then prove that with a sufficiently large unlabeled sample, one is able to find classifiers with low incompatibility. Combining the two observations, we manage to prove a probably approximately correct (PAC) style learning bound for semi-supervised multi-view learning. We empirically verified our theory by designing two proof-of-concept multi-view learning algorithms, one based on active view sensing and the other based on online co-regularization, with real-world data sets.

With the development of information technology, online social networks grow dramatically. They now play a significant role in people's social life, especially for the younger generation. While huge amount of information is available in online social networks, privacy concerns arise. Among various privacy protection proposals, the notions of privacy as control and information boundary have been introduced. Commercial social networking sites have adopted the concept to implement mechanisms such as Google circles and Facebook custom lists. However, the functions are not widely accepted by the users, partly because it is tedious and labor-intensive to manually assign friends into circles.

Manifold learning is an effective feature extraction technique, which seeks a low-dimensional space where the manifold structure, in terms of local neighborhood, of the data set can be well preserved. A typical manifold learning method constructs a local neighborhood centered at individual samples. In this paper, we propose to construct local neighborhoods that centered at subclass centers, and seek an embedded space where such neighborhood is well preserved. We show from a probability perspective that, neighbors of a subclass center would contain more intra-class data than inter-class data, which may be desirable for discrimination. Meanwhile, we simultaneously enhance the discriminative power of extracted features by maximizing the Fisher ratio of embedded data based on subclass centers. Experimental results on CAS-PEAL and FERET face databases demonstrate that our proposed approach is more effective than most typical manifold learning methods and their supervised extensions in classification performance.

Sparse representation technique has been successfully employed to solve face recognition task. Though current sparse representation based classifier proves to achieve high classification accuracy, it implicitly assumes that the losses of all misclassifications are the same. However, in many real-world applications, different misclassifications could lead to different losses. Driven by this concern, we propose in this paper a sparse cost-sensitive classifier for face recognition. Our approach uses probabilistic model of sparse representation to estimate the posterior probabilities of a testing sample, calculates all the misclassification losses via the posterior probabilities and then predicts the class label by minimizing the losses. Experimental results on the public AR and FRGC face databases validate the efficacy of the proposed approach.

The key of color face recognition technique is how to effectively utilize the complementary information between color components and remove their redundancy. Present color face recognition methods generally reduce the correlations between color components in the image pixel level, and then extract the discriminant features from the uncorrelated color face images. In this paper, we propose a novel color face recognition approach based on the holistic orthogonal analysis (HOA) of discriminant transforms of color images. HOA can reduce the correlation of color information in the feature level. It in turn achieves the discriminant transforms of red, green and blue color images by using the Fisher criterion, and simultaneously makes the achieved transforms mutually orthogonal. Experimental results on the AR and FRGC-2 public color face image databases demonstrate that the proposed approach acquires better recognition performance than several representative color face recognition methods.