In this paper, we present a novel stability analysis of adversarial training and prove generalization upper bounds in terms of an expansiveness property of adversarial perturbations used during training and used for evaluation. These expansiveness parameters appear not only govern the vanishing rate of the generalization error but also govern its scaling constant. Our proof techniques do not rely on artificial assumptions of the adversarial loss, as are typically used in previous works. Our bound attributes the robust overfitting in PGD-based adversarial training to the sign function used in the PGD attack, resulting in a bad expansiveness parameter. The peculiar choice of sign function in the PGD attack appears to impact adversarial training both in terms of (inner) optimization and in terms of generalization, as shown in this work. This aspect has been largely overlooked to date. Going beyond the sign-function based PGD attacks, we further show that poor expansiveness properties exist in a wide family of PGD-like iterative attack algorithms, which may highlight an intrinsic difficulty in adversarial training.

Federated learning (FL) is a widely adopted privacy-preserving distributed learning framework, yet its generalization performance remains less explored compared to centralized learning. In FL, the generalization error consists of two components: the out-of-sample gap, which measures the gap between the empirical and true risk for participating clients, and the participation gap, which quantifies the risk difference between participating and non-participating clients. In this work, we apply an information-theoretic analysis via the conditional mutual information (CMI) framework to study FL’s two-level generalization. Beyond the traditional supersample-based CMI framework, we introduce a superclient construction to accommodate the two-level generalization setting in FL. We derive multiple CMI-based bounds, including hypothesis-based CMI bounds, illustrating how privacy constraints in FL can imply generalization guarantees. Furthermore, we propose fast-rate evaluated CMI bounds that recover the best-known convergence rate for two-level FL generalization in the small empirical risk regime. For specific FL model aggregation strategies and structured loss functions, we refine our bounds to achieve improved convergence rates with respect to the number of participating clients. Empirical evaluations confirm that our evaluated CMI bounds are non-vacuous and accurately capture the generalization behavior of FL algorithms.

Watermarking has emerged as a crucial method to distinguish AI-generated text from human-created text. Current watermarking approaches often lack formal optimality guarantees or address the scheme and detector design separately. In this paper, we introduce a novel, unified theoretical framework for watermarking Large Language Models (LLMs) that jointly optimizes both the watermarking scheme and detector. Our approach aims to maximize detection performance while maintaining control over the worst-case false positive rate (FPR) and distortion on text quality. We derive closed-form optimal solutions for this joint design and characterize the fundamental trade-off between watermark detectability and distortion. Notably, we reveal that the optimal watermarking schemes should be adaptive to the LLM’s generative distribution. Building on our theoretical insights, we propose a distortion-free, distribution-adaptive watermarking algorithm (DAWA) that leverages a surrogate model for model-agnosticism and efficiency. Experiments on Llama2-13B and Mistral-8$\times$7B models confirm the effectiveness of our approach, particularly at ultra-low FPRs. Our code is available at \url{https://github.com/yepengliu/DAWA}.

The interactions between the update of model parameters and the update of perturbation operators complicate the dynamics of adversarial training (AT). This paper reveals a surprising behavior in AT, namely that the distribution induced by adversarial perturbations during AT becomes progressively more difficult to learn. We derived a generalization bound to theoretically attribute this behavior to the increasing of a quantity associated with the perturbation operator, namely, its local dispersion. We corroborate this explanation with concrete experimental validations and show that this deteriorating behavior of the induced distributions is correlated with robust overfitting of AT.

To date, a backbone of methods for unsupervised domain adaptation (UDA) involves learning label-discriminative features via a label classifier and domain-invariant features through a domain discriminator in an adversarial scheme. However, these methods lack explicit control for aligning the source data and target data within the same label class, degrading the classifier's performance in the target domain. In this paper, we propose PL-Mix, a pseudo label guided Mixup method based on adversarial prompt tuning. Specifically, our PL-Mix facilitates class-dependent alignment and can alleviate the impact of noisy pseudo-labels. We then theoretically justify that PL-Mix can improve the generalization for UDA. Extensive experiments of the comparison with existing models also demonstrate the effectiveness of PL-Mix.

Sentence Representation Learning (SRL) is a fundamental task in Natural Language Processing (NLP), with the Contrastive Learning of Sentence Embeddings (CSE) being the mainstream technique due to its superior performance. An intriguing phenomenon in CSE is the significant performance gap between supervised and unsupervised methods, with their only difference lying in the training data. Previous works attribute this performance gap to differences in two representation properties (alignment and uniformity). However, since alignment and uniformity only measure the results, they fail to answer "What aspects of the training data contribute to the performance gap?" and "How can the performance gap be narrowed?", In this paper, we conduct empirical experiments to answer these "What" and "How" questions. We first answer the "What" question by thoroughly comparing the behavior of supervised and unsupervised CSE during their respective training processes. From the comparison, we identify the similarity pattern as a key factor to the performance gap, and introduce a metric, called Relative Fitting Difficulty (RFD), to measure the complexity of the similarity pattern. Then, based on the insights gained from the "What" question, we tackle the "How" question by increasing the pattern complexity of the training data. We achieve this by leveraging the In-Context Learning (ICL) capability of the Large Language Model (LLM) to generate data that simulates complex patterns. By utilizing the hierarchical patterns in the LLM-generated data, we effectively narrow the gap between supervised and unsupervised CSE. We release our codes and appendix at https://github.com/BDBC-KG-NLP/NGCSE.

Unsupervised domain adaptation (UDA) plays a crucial role in addressing distribution shifts in machine learning. In this work, we improve the theoretical foundations of UDA proposed in Acuna et al. (2021) by refining their $f$-divergence-based discrepancy and additionally introducing a new measure, $f$-domain discrepancy ($f$-DD). By removing the absolute value function and incorporating a scaling parameter, $f$-DD obtains novel target error and sample complexity bounds, allowing us to recover previous KL-based results and bridging the gap between algorithms and theory presented in Acuna et al. (2021). Using a localization technique, we also develop a fast-rate generalization bound. Empirical results demonstrate the superior performance of $f$-DD-based learning algorithms over previous works in popular UDA benchmarks.

In this work, we introduce novel information-theoretic generalization bounds using the conditional $f$-information framework, an extension of the traditional conditional mutual information (MI) framework. We provide a generic approach to derive generalization bounds via $f$-information in the supersample setting, applicable to both bounded and unbounded loss functions. Unlike previous MI-based bounds, our proof strategy does not rely on upper bounding the cumulant-generating function (CGF) in the variational formula of MI. Instead, we set the CGF or its upper bound to zero by carefully selecting the measurable function invoked in the variational formula. Although some of our techniques are partially inspired by recent advances in the coin-betting framework (e.g., Jang et al. (2023)), our results are independent of any previous findings from regret guarantees of online gambling algorithms. Additionally, our newly derived MI-based bound recovers many previous results and improves our understanding of their potential limitations. Finally, we empirically compare various $f$-information measures for generalization, demonstrating the improvement of our new bounds over the previous bounds.

Stochastic differential equations (SDEs) have been shown recently to characterize well the dynamics of training machine learning models with SGD. When the generalization error of the SDE approximation closely aligns with that of SGD in expectation, it provides two opportunities for understanding better the generalization behaviour of SGD through its SDE approximation. Firstly, viewing SGD as full-batch gradient descent with Gaussian gradient noise allows us to obtain trajectory-based generalization bound using the information-theoretic bound from Xu and Raginsky [2017]. Secondly, assuming mild conditions, we estimate the steady-state weight distribution of SDE and use information-theoretic bounds from Xu and Raginsky [2017] and Negrea et al. [2019] to establish terminal-state-based generalization bounds. Our proposed bounds have some advantages, notably the trajectory-based bound outperforms results in Wang and Mao [2022], and the terminal-state-based bound exhibits a fast decay rate comparable to stability-based bounds.

Text classification is one vital tool assisting web content mining. Semi-supervised text classification (SSTC) offers an approach to alleviate the burden of annotation costs by training on a few labeled texts alongside many unlabeled texts. Unsolved challenges in SSTC are the overfitting problem caused by the limited labeled data and the mislabeling problem of unlabeled texts. To address these issues, this paper proposes a Self-Paced PairWise representation learning (SPPW) model. Concretely, SPPW alleviates the overfitting problem by replacing the overfitting-prone learning of a parameterized classifier with representation learning in a pair-wise manner. Besides, we propose a novel self-paced text filtering method that effectively integrates both label confidence and text hardness to reduce mislabeled texts synergistically. Extensive experiments on 3 benchmark SSTC datasets show that SPPW outperforms baselines and is effective in mitigating overfitting and mislabeling problems.

Text classification is a fundamental task in web content mining. Although the existing supervised contrastive learning (SCL) approach combined with pre-trained language models (PLMs) has achieved leading performance in text classification, it lacks fundamental principles. Theoretically motivated by a derived lower bound of mutual information maximization, we propose a dual contrastive learning framework DualCL that satisfies three properties, i.e., parameter-free, augmentation-easy and label-aware. DualCL generates classifier parameters from the PLM and simultaneously uses them for classification and as augmented views of the input text for supervised contrastive learning. Extensive experiments conclusively demonstrate that DualCL excels in learning superior text representations and consistently outperforms baseline models.

Multimodal relation extraction is a fundamental task of multimodal information extraction. Recent studies have shown promising results by integrating hierarchical visual features from local regions, like image patches, to the broader global regions that form the entire image. However, research to date has largely ignored the understanding of how hierarchical visual semantics are represented and the characteristics that can benefit relation extraction. To bridge this gap, we propose a novel two-stage hierarchical visual context fusion transformer incorporating the mixture of multimodal experts framework to effectively represent and integrate hierarchical visual features into textual semantic representations. In addition, we introduce the concept of hierarchical tracking maps to facilitate the understanding of the intrinsic mechanisms of image information processing involved in multimodal models. We thoroughly investigate the implications of hierarchical visual contexts through four dimensions: performance evaluation, the nature of auxiliary visual information, the patterns observed in the image encoding hierarchy, and the significance of various visual encoding levels. Empirical studies show that our approach achieves new state-of-the-art performance on the MNRE dataset.

Data augmentation is widely used in text classification, especially in the low-resource regime where a few examples for each class are available during training. Despite the success, generating data augmentations as hard positive examples that may increase their effectiveness is under-explored. This paper proposes an Adversarial Word Dilution (AWD) method that can generate hard positive examples as text data augmentations to train the low-resource text classification model efficiently. Our idea of augmenting the text data is to dilute the embedding of strong positive words by weighted mixing with unknown-word embedding, making the augmented inputs hard to be recognized as positive by the classification model. We adversarially learn the dilution weights through a constrained min-max optimization process with the guidance of the labels. Empirical studies on three benchmark datasets show that AWD can generate more effective data augmentations and outperform the state-of-the-art text data augmentation methods. The additional analysis demonstrates that the data augmentations generated by AWD are interpretable and can flexibly extend to new examples without further training.

We present a simple and yet effective interpolation-based regularization technique, aiming to improve the generalization of Graph Neural Networks (GNNs) on supervised graph classification. We leverage Mixup, an effective regularizer for vision, where random sample pairs and their labels are interpolated to create synthetic images for training. Unlike images with grid-like coordinates, graphs have arbitrary structure and topology, which can be very sensitive to any modification that alters the graph's semantic meanings. This posts two unanswered questions for Mixup-like regularization schemes: Can we directly mix up a pair of graph inputs? If so, how well does such mixing strategy regularize the learning of GNNs? To answer these two questions, we propose ifMixup, which first adds dummy nodes to make two graphs have the same input size and then simultaneously performs linear interpolation between the aligned node feature vectors and the aligned edge representations of the two graphs. We empirically show that such simple mixing schema can effectively regularize the classification learning, resulting in superior predictive accuracy to popular graph augmentation and GNN methods.

Prompt-based Learning has shown significant success in few-shot classification. The mainstream approach is to concatenate a template for the input text to transform the classification task into a cloze-type task where label mapping plays an important role in finding the ground-truth labels. While current label mapping methods only use the contexts in one single input, it could be crucial if wrong information is contained in the text. Specifically, it is proved in recent work that even the large language models like BERT/RoBERTa make classification decisions heavily dependent on a specific keyword regardless of the task or the context. Such a word is referred to as a lexical cue and if a misleading lexical cue is included in the instance it will lead the model to make a wrong prediction. We propose a multi-mask prompt-based approach with Multi-Mask Label Mapping (MMLM) to reduce the impact of misleading lexical cues by allowing the model to exploit multiple lexical cues. To satisfy the conditions of few-shot learning, an instance augmentation approach for the cloze-type model is proposed and the misleading cues are gradually excluded through training. We demonstrate the effectiveness of MMLM by both theoretical analysis and empirical studies, and show that MMLM outperforms other existing label mapping approaches.

Document-level relation extraction (DocRE)involves identifying relations between entities distributed in multiple sentences within a document.Existing methods focus on building a heterogeneous document graph to model the internal structure of an entity and the external interaction between entities.However, there are two drawbacks in existing methods.On one hand, anaphor plays an important role in reasoning to identify relations between entities but is ignored by these methods.On the other hand, these methods achieve crosssentence entity interactions implicitly by utilizing a document or sentences as intermediate nodes.Such an approach has difficulties in learning fine-grained interactions between entities across different sentences, resulting in sub-optimal performance.To address these issues, we propose an Anaphor-Assisted (AA) framework for DocRE tasks.Experimental results on the widely-used datasets demonstrate that our model achieves a new state-of-the-art performance.1

In this work, we present a variety of novel information-theoretic generalization bounds for learning algorithms, from the supersample setting of Steinke & Zakynthinou (2020)—the setting of the “conditional mutual information” framework. Our development exploits projecting the loss pair (obtained from a training instance and a testing instance) down to a single number and correlating loss values with a Rademacher sequence (and its shifted variants). The presented bounds include square-root bounds, fast-rate bounds, including those based on variance and sharpness, and bounds for interpolating algorithms etc. We show theoretically or empirically that these bounds are tighter than all information-theoretic bounds known to date on the same supersample setting.

Semi-supervised text classification (STC) has been extensively researched and reduces human annotation. However, existing research assuming that unlabeled data only contains in-distribution texts is unrealistic. This paper extends STC to a more practical Open-set Semi-supervised Text Classification (OSTC) setting, which assumes that the unlabeled data contains out-of-distribution (OOD) texts. The main challenge in OSTC is the false positive inference problem caused by inadvertently including OOD texts during training. To address the problem, we first develop baseline models using outlier detectors for hard OOD-data filtering in a pipeline procedure. Furthermore, we propose a Latent Outlier Softening (LOS) framework that integrates semi-supervised training and outlier detection within probabilistic latent variable modeling. LOS softens the OOD impacts by the Expectation-Maximization (EM) algorithm and weighted entropy maximization. Experiments on 3 created datasets show that LOS significantly outperforms baselines.

We present new information-theoretic generalization guarantees through the a novel construction of the "neighboring-hypothesis" matrix and a new family of stability notions termed sample-conditioned hypothesis (SCH) stability. Our approach yields sharper bounds that improve upon previous information-theoretic bounds in various learning scenarios. Notably, these bounds address the limitations of existing information-theoretic bounds in the context of stochastic convex optimization (SCO) problems, as explored in the recent work by Haghifam et al. (2023).

Opinion target extraction (OTE) or aspect extraction (AE) is a fundamental task in opinion mining that aims to extract the targets (or aspects) on which opinions have been expressed. Recent work focus on cross-domain OTE, which is typically encountered in real-world scenarios, where the testing and training distributions differ. Most methods use domain adversarial neural networks that aim to reduce the domain gap between the labelled source and unlabelled target domains to improve target domain performance. However, this approach only aligns feature distributions and does not account for class-wise feature alignment, leading to suboptimal results. Semi-supervised learning (SSL) has been explored as a solution, but is limited by the quality of pseudo-labels generated by the model. Inspired by the theoretical foundations in domain adaptation [2], we propose a new SSL approach that opts for selecting target samples whose model output from a domain-specific teacher and student network disagree on the unlabelled target data, in an effort to boost the target domain performance. Extensive experiments on benchmark cross-domain OTE datasets show that this approach is effective and performs consistently well in settings with large domain shifts.

Word Sense Disambiguation (WSD) which aims to identify the correct sense of a target word appearing in a specific context is essential for web text analysis. The use of glosses has been explored as a means for WSD. However, only a few works model the correlation between the target context and gloss. We add to the body of literature by presenting a model that employs a multi-head attention mechanism on deep contextual features of the target word and candidate glosses to refine the target word embedding. Furthermore, to encourage the model to learn the relevant part of target features that align with the correct gloss, we recursively alternate attention on target word features and that of candidate glosses to gradually extract the relevant contextual features of the target word, refining its representation and strengthening the final disambiguation results. Empirical studies on the five most commonly used benchmark datasets show that our proposed model is effective and achieves state-of-the-art results.

We consider the problem of learning a neural network classifier. Under the information bottleneck (IB) principle, we associate with this classification problem a representation learning problem, which we call "IB learning". We show that IB learning is, in fact, equivalent to a special class of the quantization problem. The classical results in rate-distortion theory then suggest that IB learning can benefit from a "vector quantization" approach, namely, simultaneously learning the representations of multiple input objects. Such an approach assisted with some variational techniques, result in a novel learning framework, "Aggregated Learning", for classification with neural network models. In this framework, several objects are jointly classified by a single neural network. The effectiveness of this framework is verified through extensive experiments on standard image recognition and text classification tasks.

Multi-label text classification (MLTC) has a wide range of real-world applications. Neural networks recently promoted the performance of MLTC models. Training these neural-network models relies on sufficient accurately labelled data. However, manually annotating large-scale multi-label text classification datasets is expensive and impractical for many applications. Weak supervision techniques have thus been developed to reduce the cost of annotating text corpus. However, these techniques introduce noisy labels into the training data and may degrade the model performance. This paper aims to deal with such noise-label problems in MLTC in both single-instance and multi-instance settings. We build a novel Neural Expectation-Maximization Framework (nEM) that combines neural networks with probabilistic modelling. The nEM framework produces text representations using neural-network text encoders and is optimized with the Expectation-Maximization algorithm. It naturally considers the noisy labels during learning by iteratively updating the model parameters and estimating the distribution of the ground-truth labels. We evaluate our nEM framework in multi-instance noisy MLTC on a benchmark relation extraction dataset constructed by distant supervision and in single-instance noisy MLTC on synthetic noisy datasets constructed by keywords supervision and label flipping. The experimental results demonstrate that nEM significantly improves upon baseline models in both single-instance and multi-instance noisy MLTC tasks. The experiment analysis suggests that our nEM framework efficiently reduces the noisy labels in MLTC datasets and significantly improves model performance.

Entity alignment is a vital task in knowledge fusion, which aims to align entities from different knowledge graphs and merge them into one single graph. Existing entity alignment models focus on local features and try to minimize the distance between pairs of pre-aligned entities. Despite their success, these models heavily rely on the number of existing pre-aligned entity pairs and the topology information from the rest large set of unaligned entities is still largely unexplored. To overcome the limitation of existing models, we propose a model, termed Global Alignment and Local Information Aggregation, or GALA. GALA constructs global features for the knowledge graphs to be aligned using entity embeddings. It aligns the entities in the graphs by forcing their global features to match with each other and progressively updating the entity embeddings by aggregating local information from the other network. Empirical studies on commonly-used KG alignment data sets confirm the effectiveness of the proposed model.

Information extraction aims at extracting entities, relations, and so on, in text to support information retrieval systems. To extract information, researchers have considered multitask learning (ML) approaches. The conventional ML approach learns shared features across tasks, with the assumption that these features capture sufficient task interactions to learn expressive shared representations for task classification. However, such an assumption is flawed in different perspectives. First, the shared representation may contain noise introduced by another task; tasks coupled for multitask learning may have different complexities but this approach treats all tasks equally; the conventional approach has a flat structure that hinders the learning of explicit interactions. This approach, however, learns implicit interactions across tasks and often has a generalization ability that has benefited the learning of multitasks. In this article, we take advantage of implicit interactions learned by conventional approaches while alleviating the issues mentioned above by developing a Recurrent Interaction Network with an effective Early Prediction Integration (RIN-EPI) for multitask learning. Specifically, RIN-EPI learns implicit and explicit interactions across two different but related tasks. To effectively learn explicit interactions across tasks, we consider the correlations among the outputs of related tasks. It is, however, obvious that task outputs are unobservable during training, so we leverage the predictions at intermediate layers (referred to as early predictions) as proxies as well as shared features across tasks to learn explicit interactions through attention mechanisms and sequence learning models. By recurrently learning explicit interactions, we gradually improve predictions for the individual tasks in the multitask learning. We demonstrate the effectiveness of RIN-EPI on the learning of two mainstream multitasks for information extraction: (1) entity recognition and relation classification and (2) aspect and opinion term co-extraction. Extensive experiments demonstrate the effectiveness of the RIN-EPI architecture, where we achieve state-of-the-art results on several benchmark datasets.

Each link prediction task requires different degrees of answer diversity. While a link prediction task may expect up to a couple of answers, another may expect nearly a hundred answers. Given this fact, the performance of a link prediction model can be estimated more accurately if a flexible number of obtained answers are estimated instead of a predefined number of answers. Inspired by this, in this article, we analyze two evaluation criteria for link prediction tasks, respectively ranking-based protocol and sampling-based protocol. Furthermore, we study two classes of models on link prediction task, direct model and latent-variable model respectively, to demonstrate that latent-variable model performs better under the sampling-based protocol. We then propose a latent-variable model where the framework of Conditional Variational AutoEncoder (CVAE) is applied. Experimental study suggests that the proposed model performs comparably to the current state-of-the-art even under the conventional rank-based protocol. Under the sampling-based protocol, the proposed model is shown to outperform various state-of-the-art models.

Few-shot text classification has recently been promoted by the meta-learning paradigm which aims to identify target classes with knowledge transferred from source classes with sets of small tasks named episodes. Despite their success, existing works building their meta-learner based on Prototypical Networks are unsatisfactory in learning discriminative text representations between similar classes, which may lead to contradictions during label prediction. In addition, the task-level and instance-level overfitting problems in few-shot text classification caused by a few training examples are not sufficiently tackled. In this work, we propose a contrastive learning framework named ContrastNet to tackle both discriminative representation and overfitting problems in few-shot text classification. ContrastNet learns to pull closer text representations belonging to the same class and push away text representations belonging to different classes, while simultaneously introducing unsupervised contrastive regularization at both task-level and instance-level to prevent overfitting. Experiments on 8 few-shot text classification datasets show that ContrastNet outperforms the current state-of-the-art models.

Unsupervised sentence representation learning is a fundamental problem in natural language processing. Recently, contrastive learning has made great success on this task. Existing constrastive learning based models usually apply random sampling to select negative examples for training. Previous work in computer vision has shown that hard negative examples help contrastive learning to achieve faster convergency and better optimization for representation learning. However, the importance of hard negatives in contrastive learning for sentence representation is yet to be explored. In this study, we prove that hard negatives are essential for maintaining strong gradient signals in the training process while random sampling negative examples is ineffective for sentence representation. Accordingly, we present a contrastive model, MixCSE, that extends the current state-of-the-art SimCSE by continually constructing hard negatives via mixing both positive and negative features. The superior performance of the proposed approach is demonstrated via empirical studies on Semantic Textual Similarity datasets and Transfer task datasets.

Weakly supervised phrase grounding aims to learn an alignment between phrases in a caption and objects in a corresponding image using only caption-image annotations, i.e., without phrase-object annotations.Previous methods typically use a caption-image contrastive loss to indirectly supervise the alignment between phrases and objects, which hinders the maximum use of the intrinsic structure of the multimodal data and leads to unsatisfactory performance.In this work, we directly use the phrase-object contrastive loss in the condition that no positive annotation is available in the first place.Specifically, we propose a novel contrastive learning framework based on the expectation-maximization algorithm that adaptively refines the target prediction.Experiments on two widely used benchmarks, Flickr30K Entities and RefCOCO+, demonstrate the effectiveness of our framework.We obtain 63.05% top-1 accuracy on Flickr30K Entities and 59.51%/43.46% on RefCOCO+ TestA/TestB, outperforming the previous methods by a large margin, even surpassing a previous SoTA that uses a pre-trained visionlanguage model.Furthermore, we deliver a theoretical analysis of the effectiveness of our method from the perspective of the maximum likelihood estimate with latent variables.

Overfitting is a common problem when there is insufficient data to train deep neural networks in machine learning tasks.Data augmentation regularization methods such as Dropout, Mixup, and their enhanced variants, are effective and prevalent, and achieve promising performance to overcome overfitting.However, in text learning, most of the existing regularization approaches merely adopt ideas from computer vision without considering the importance of dimensionality in natural language processing.In this paper, we argue that the property is essential to overcome overfitting in text learning.Accordingly, we present a saliency map informed textual data augmentation and regularization framework, which combines Dropout and Mixup, namely DropMix, to mitigate the overfitting problem in text learning.In addition, we design a procedure that drops and patches fine grained shapes of the saliency map under the DropMix framework to enhance regularization.Empirical studies confirm the effectiveness of the proposed approach on 12 text classification tasks.

Text style transfer is an important task in natural language processing with broad applications.Existing models following the masking and filling scheme suffer two challenges: the word masking procedure may mistakenly remove unexpected words and the selected words in the word filling procedure may lack diversity and semantic consistency.To tackle both challenges, in this study, we propose a style transfer model, with an adversarial masking approach and a styled filling technique (AMSF).Specifically, AMSF first trains a mask predictor by adversarial training without manual configuration.Then two additional losses, i.e. an entropy maximization loss and a consistency regularization loss, are introduced in training the word filling module to guarantee the diversity and semantic consistency of the transferred texts.Experimental results and analysis on two benchmark text style transfer data sets demonstrate the effectiveness of the proposed approaches.

This paper considers the domain generalization problem in which the labels of the query batch may be predicted at once and the model is allowed to assign a label to a query example utilizing all information contained in the query batch. In this setting, we identify two problems in the standard adaptive risk minimization (ARM) framework, namely, mismatched context and overfitted context, which are most severely manifested respectively at small and large support batch sizes. The existence of these problems signifies a fundamental tradeoff between within-domain learning and cross-domain generalization. We also propose two context adversarial training approaches to alleviate these problems so as to achieve a better tradeoff. We demonstrate experimentally that the proposed approaches uniformly outperform the standard ARM training for all choices of support batch sizes.

Fine-Grained entity typing is complicated by the fact that type labels form a hierarchical structure, and those training examples usually contain noisy type labels. This paper addresses these two issues by proposing a novel framework that simultaneously models the correlation among hierarchical types and the noise within the training data. Additionally, the framework contains an innovative training approach during which the noise in the training data is progressively removed. Experiments on standard benchmarking datasets validate the proposed framework and establish it as a new state of the art for this problem.

Aspect-level sentiment classification (ALSC); a fine-grained task of sentiment analysis holds the promise of machines communicating knowledge of different aspects of a product/service with humans. Specifically, ALSC aims at inferring the sentiment expressed toward a specific aspect term in a user-generated textual content. It is a long-standing problem in sentiment analysis, and its usefulness cannot be underestimated. Recent studies employ the dependency tree and restructure it to model the syntactic relationship among words in text. However, the restructuring process destructs the structural information of the original dependency tree. As a solution, we first construct a syntax graph that preserves the structural information of the dependency tree. We then propose a reliable syntax-based neural network model that performs a thorough search on the syntax graph to effectively find the relevant contextual information with respect to the aspect term for the sentence encoding. Noting that dependency trees parsed from existing dependency parsers may contain incorrect syntactic dependencies due to grammatical errors in a sentence, we adopt a convolutional layer that takes into account the relations among features of words in a local neighborhood to mitigate the issues brought by incorrect syntactic dependencies. Our results on benchmark datasets demonstrate that our model outperforms the previous methods and achieves state-of-the-art results for the ALSC task.

Multitask learning has shown promising performance in learning multiple related tasks simultaneously, and variants of model architectures have been proposed, especially for supervised classification problems. One goal of multitask learning is to extract a good representation that sufficiently captures the relevant part of the input about the output for each learning task. To achieve this objective, in this paper we design a multitask learning architecture based on the observation that correlations exist between outputs of some related tasks (e.g. entity recognition and relation extraction tasks), and they reflect the relevant features that need to be extracted from the input. As outputs are unobserved, our proposed model exploits task predictions in lower layers of the neural model, also referred to as early predictions in this work. But we control the injection of early predictions to ensure that we extract good task-specific representations for classification. We refer to this model as a Progressive Multitask learning model with Explicit Interactions (PMEI). Extensive experiments on multiple benchmark datasets produce state-of-the-art results on the joint entity and relation extraction task.

Attention with positional encoding has been demonstrated as a powerful component in modern neural network models, such as transformers. However, why positional encoding works well in attention models remains largely unanswered. In this paper, we study the scalar relative positional encoding (SRPE) proposed in the T5 transformer. Such an encoding method has two features. First, it uses a scalar to embed relative positions. Second, the relative positions are bucketized using a fixed heuristic algorithm, and positions in the same bucket share the same embedding. In this work, we show that SRPE in attention has an elegant probabilistic interpretation. More specifically, the positional encoding serves to produce a prior distribution for the attended positions. The resulting attentive distribution can be viewed as a posterior distribution of the attended position given the observed input sequence. Furthermore, we propose a new SRPE (AT5) that adopts a learnable bucketization protocol and automatically adapts to the dependency range specific to the learning task. Empirical studies show that the AT5 achieves superior performance than the T5's SRPE.

Effective regularization techniques are highly desired in deep learning for alleviating overfitting and improving generalization. This work proposes a new regularization scheme, based on the understanding that the flat local minima of the empirical risk cause the model to generalize better. This scheme is referred to as adversarial model perturbation (AMP), where instead of directly minimizing the empirical risk, an alternative "AMP loss" is minimized via SGD. Specifically, the AMP loss is obtained from the empirical risk by applying the "worst" norm-bounded perturbation on each point in the parameter space. Comparing with most existing regularization schemes, AMP has strong theoretical justifications, in that minimizing the AMP loss can be shown theoretically to favour flat local minima of the empirical risk. Extensive experiments on various modern deep architectures establish AMP as a new state of the art among regularization schemes. Our code is available at https://github.com/hiyouga/AMP-Regularizer.

Fine-grained entity typing (FET) aims to annotate the entity mentions in a sentence with fine-grained type labels. It brings plentiful semantic information for many natural language processing tasks. Existing FET approaches apply hard attention to learn on the noisy labels, and ignore that those noises have structured hierarchical dependency. Despite their successes, these FET models are insufficient in modeling type hierarchy dependencies and handling label noises. In this paper, we directly tackle the structured noisy labels by combining a forward tree module and a backward tree module. Specifically, the forward tree formulates the informative walk that hierarchically represents the type distributions. The backward tree models the erroneous walk that learns the noise confusion matrix. Empirical studies on several benchmark data sets confirm the effectiveness of the proposed framework.

In this paper, we unify a diverse set of learning tasks in NLP, semantic retrieval and related areas, under a common umbrella, which we call unsupervised semantic association learning (USAL). Examples of this generic task include word sense disambiguation, answer selection and question retrieval. We then present a novel modeling framework to tackle such tasks. The framework introduces, under the deep learning paradigm, a latent label indexing the true target in the candidate target set. An EM algorithm is then developed for learning the deep model and inferring the latent variables, principled under variational techniques and noise contrastive estimation. We apply the model and algorithm to several semantic retrieval benchmark tasks and the superior performance of the proposed approach is demonstrated via empirical studies.

We consider the problem of learning a neural network classifier. Under the information bottleneck (IB) principle, we associate with this classification problem a representation learning problem, which we call “IB learning”. We show that IB learning is, in fact, equivalent to a special class of the quantization problem. The classical results in rate-distortion theory then suggest that IB learning can benefit from a “vector quantization” approach, namely, simultaneously learning the representations of multiple input objects. Such an approach assisted with some variational techniques, result in a novel learning framework, “Aggregated Learning”, for classification with neural network models. In this framework, several objects are jointly classified by a single neural network. The effectiveness of this framework is verified through extensive experiments on standard image recognition and text classification tasks.

A large majority of approaches have been proposed to leverage the dependency tree in the relation classification task. Recent works have focused on pruning irrelevant information from the dependency tree. The state-of-the-art Attention Guided Graph Convolutional Networks (AGGCNs) transforms the dependency tree into a weighted-graph to distinguish the relevance of nodes and edges for relation classification. However, in their approach, the graph is fully connected, which destroys the structure information of the original dependency tree. How to effectively make use of relevant information while ignoring irrelevant information from the dependency trees remains a challenge in the relation classification task. In this work, we learn to transform the dependency tree into a weighted graph by considering the syntax dependencies of the connected nodes and persisting the structure of the original dependency tree. We refer to this graph as a syntax-transport graph. We further propose a learnable syntax-transport attention graph convolutional network (LST-AGCN) which operates on the syntax-transport graph directly to distill the final representation which is sufficient for classification. Experiments on Semeval-2010 Task 8 and Tacred show our approach outperforms previous methods.

Aspect-level sentiment classification (ALSC) aims at predicting the sentiment polarity of a specific aspect term occurring in a sentence. This task requires learning a representation by aggregating the relevant contextual features concerning the aspect term. Existing methods cannot sufficiently leverage the syntactic structure of the sentence, and hence are difficult to distinguish different sentiments for multiple aspects in a sentence. We perceive the limitations of the previous methods and propose a hypothesis about finding crucial contextual information with the help of syntactic structure. For this purpose, we present a neural network model named RepWalk which performs a replicated random walk on a syntax graph, to effectively focus on the informative contextual words. Empirical studies show that our model outperforms recent models on most of the benchmark datasets for the ALSC task. The results suggest that our method for incorporating syntactic structure enriches the representation for the classification.

The dependencies between system and user utterances in the same turn and across different turns are not fully considered in existing multidomain dialogue state tracking (MDST) models.In this study, we argue that the incorporation of these dependencies is crucial for the design of MDST and propose Parallel Interactive Networks (PIN) to model these dependencies.Specifically, we integrate an interactive encoder to jointly model the in-turn dependencies and cross-turn dependencies.The slot-level context is introduced to extract more expressive features for different slots.And a distributed copy mechanism is utilized to selectively copy words from historical system utterances or historical user utterances.Empirical studies demonstrated the superiority of the proposed PIN model.

The idea of using multi-task learning approaches to address the joint extraction of entity and relation is motivated by the relatedness between the entity recognition task and the relation classification task.Existing methods using multi-task learning techniques to address the problem learn interactions among the two tasks through a shared network, where the shared information is passed into the taskspecific networks for prediction.However, such an approach hinders the model from learning explicit interactions between the two tasks to improve the performance on the individual tasks.As a solution, we design a multitask learning model which we refer to as recurrent interaction network which allows the learning of interactions dynamically, to effectively model task-specific features for classification.Empirical studies on two real-world datasets confirm the superiority of the proposed model.

The introduction of VAE provides an efficient framework for the learning of generative models, including generative topic models.However, when the topic model is a Latent Dirichlet Allocation (LDA) model, a central technique of VAE, the reparameterization trick, fails to be applicable.This is because no reparameterization form of Dirichlet distributions is known to date that allows the use of the reparameterization trick.In this work, we propose a new method, which we call Rounded Reparameterization Trick (RRT), to reparameterize Dirichlet distributions for the learning of VAE-LDA models.This method, when applied to a VAE-LDA model, is shown experimentally to outperform the existing neural topic models on several benchmark datasets and on a synthetic dataset.

Entity linking, which maps named entity mentions in a document into the proper entities in a given knowledge graph, has been shown to be able to significantly benefit from modeling the entity relatedness through Graph Convolutional Networks (GCN). Nevertheless, existing GCN entity linking models fail to take into account the fact that the structured graph for a set of entities not only depends on the contextual information of the given document but also adaptively changes on different aggregation layers of the GCN, resulting in insufficiency in terms of capturing the structural information among entities. In this paper, we propose a dynamic GCN architecture to effectively cope with this challenge. The graph structure in our model is dynamically computed and modified during training. Through aggregating knowledge from dynamically linked nodes, our GCN model can collectively identify the entity mappings between the document and the knowledge graph, and efficiently capture the topical coherence among various entity mentions in the entire document. Empirical studies on benchmark entity linking data sets confirm the superior performance of our proposed strategy and the benefits of the dynamic graph structure.

Supervised learning relies heavily on readily available labelled data to infer an effective classification function. However, proposed methods under the supervised learning paradigm are faced with the scarcity of labelled data within domains, and are not generalized enough to adapt to other tasks. Transfer learning has proved to be a worthy choice to address these issues, by allowing knowledge to be shared across domains and tasks. In this paper, we propose two transfer learning methods Anchored Model Transfer (AMT) and Soft Instance Transfer (SIT), which are both based on multi-task learning, and account for model transfer and instance transfer, and can be combined into a common framework. We demonstrate the effectiveness of AMT and SIT for aspect-level sentiment classification showing the competitive performance against baseline models on benchmark datasets. Interestingly, we show that the integration of both methods AMT+SIT achieves state-of-the-art performance on the same task.

Real-world knowledge bases such as DBPedia, Yago, and Freebase contain sparse linkage connectivity, which poses a severe challenge to link prediction between entities. To cope with such data scarcity issues, recent models have focused on learning interactions between entity pairs by means of relations that exist between them. However promising, some relations are associated with very few tail entities or head entities, resulting in poor estimation of the relation interaction between entities. In this article, we break the sole dependency of modeling relation interactions between entity pairs by associating a triple with pairwise embeddings, i.e., distributed vector representations for pairs of word-based entities and relation of a triple. We capture the interactions that exist between pairwise embeddings by means of a Pairwise Factorization Model that employs a factorization machine with relation attention. This approach allows parameters for related interactions to be estimated efficiently, ensuring that the pairwise embeddings are discriminative, providing strong supervisory signals for the decoding task of link prediction. The Pairwise Factorization Model we propose exploits a neural bag-of-words model as the encoder, which effectively encodes word-based entities into distributed vector representations for the decoder. The proposed model is simple and enjoys efficiency and capability, showing superior link prediction performance over state-of-the-art complex models on benchmark datasets DBPedia50K and FB15K-237.

MixUp (Zhang et al. 2017) is a recently proposed dataaugmentation scheme, which linearly interpolates a random pair of training examples and correspondingly the one-hot representations of their labels. Training deep neural networks with such additional data is shown capable of significantly improving the predictive accuracy of the current art. The power of MixUp, however, is primarily established empirically and its working and effectiveness have not been explained in any depth. In this paper, we develop an understanding for MixUp as a form of “out-of-manifold regularization”, which imposes certain “local linearity” constraints on the model’s input space beyond the data manifold. This analysis enables us to identify a limitation of MixUp, which we call “manifold intrusion”. In a nutshell, manifold intrusion in MixUp is a form of under-fitting resulting from conflicts between the synthetic labels of the mixed-up examples and the labels of original training data. Such a phenomenon usually happens when the parameters controlling the generation of mixing policies are not sufficiently fine-tuned on the training data. To address this issue, we propose a novel adaptive version of MixUp, where the mixing policies are automatically learned from the data using an additional network and objective function designed to avoid manifold intrusion. The proposed regularizer, AdaMixUp, is empirically evaluated on several benchmark datasets. Extensive experiments demonstrate that AdaMixUp improves upon MixUp when applied to the current art of deep classification models.

Embedding based models for knowledge base completion have demonstrated great successes and attracted significant research interest. In this work, we observe that existing embedding models all have their loss functions decomposed into atomic loss functions, each on a triple or an postulated edge in the knowledge graph. Such an approach essentially implies that conditioned on the embeddings of the triple, whether the triple is factual is independent of the structure of the knowledge graph. Although arguably the embeddings of the entities and relation in the triple contain certain structural information of the knowledge base, we believe that the global information contained in the embeddings of the triple can be insufficient and such an assumption is overly optimistic in heterogeneous knowledge bases. Motivated by this understanding, in this work we propose a new embedding model in which we discard the assumption that the embeddings of the entities and relation in a triple is a sufficient statistic for the triple’s factual existence. More specifically, the proposed model assumes that whether a triple is factual depends not only on the embedding of the triple but also on the embeddings of the entities and relations in a larger graph neighbourhood. In this model, attention mechanisms are constructed to select the relevant information in the graph neighbourhood so that irrelevant signals in the neighbourhood are suppressed. Termed locality-expanded neural embedding with attention (LENA), this model is tested on four standard datasets and compared with several stateof-the-art models for knowledge base completion. Extensive experiments suggest that LENA outperforms the existing models in virtually every metric.

Ci is a lyric poetry form that follows highly restrictive metrical structures. This makes it challenging for a computer to compose Ci subject to a specified metrical requirement. In this work, we adapt the CVAE framework to automated Ci generation under metrical constraints. Specifically, we present the first neural model that explicitly encodes the designated metrical structure for Ci generation. The proposed model is shown experimentally to generate Ci with nearly perfect metrical structures.

Junfan Chen, Richong Zhang, Yongyi Mao, Hongyu Guo, Jie Xu. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.

Kai Sun, Richong Zhang, Samuel Mensah, Yongyi Mao, Xudong Liu. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.

Fine-grained entity typing (FET), which annotates the entities in a sentence with a set of finely specified type labels, often serves as the first and critical step towards many natural language processing tasks. Despite great processes have been made, current FET methods have difficulty to cope with the noisy labels which naturally come with the data acquisition processes. Existing FET approaches either pre-process to clean the noise or simply focus on one of the noisy labels, sidestepping the fact that those noises are related and content dependent. In this paper, we directly model the structured, noisy labels with a novel content-sensitive weighting schema. Coupled with a newly devised cost function and a hierarchical type embedding strategy, our method leverages a random walk process to effectively weight out noisy labels during training. Experiments on several benchmark datasets validate the effectiveness of the proposed framework and establish it as a new state of the art strategy for noisy entity typing problem.

Knowledge graphs such as DBPedia and Freebase contain sparse linkage connectivity, which poses severe challenge to link prediction between entities. In addressing this sparsity problem, our studies indicate that one needs to leverage model with low complexity to avoid overfitting the weak structural information in the graphs, requiring the simple models which can efficiently encode the entities and their description information and then effectively decode their relationships. In this paper, we present a simple and efficient model that can attain these two goals. Specifically, we use a bag-of-words model, where relevant words are aggregated using average pooling or a basic Graph Convolutional Network to encode entities into distributed embeddings. A factorization machine is then used to score the relationships between those embeddings to generate linkage predictions. Empirical studies on two real datasets confirms the efficiency of our proposed model and shows superior predictive performance over state-of-the-art approaches.

Question answering over knowledge bases aims to take full advantage of the information in knowledge bases with the ultimate purpose of returning answers to questions. To access the substantial knowledge within the KB, many model architectures are hindered by the bottleneck of accurately predicting relations that connect subject entities in questions to object entities in the knowledge base. To break the bottleneck, this article presents a novel model architecture, APVA, which includes a verification mechanism to check the correctness of predicted relations. Specifically, APVA takes advantage of KB-based information to improve relation prediction but verifies the correctness of the predicted relation by means of simple negative sampling in a logistic regression framework. The APVA architecture offers a natural way to integrate an iterative training procedure, which we call turbo training. Accordingly, we introduce APVA-TURBO to perform question answering over knowledge bases. We demonstrate extensive experiments to show that APVA-TURBO outperforms existing approaches on question answering.

Embedding has emerged as an important approach to prediction, inference, data mining and information retrieval based on knowledge bases and various embedding models have been presented. Most of these models are "typeless," namely, treating a knowledge base solely as a collection of instances without considering the types of the entities therein. In this paper, we investigate the use of entity type information for knowledge base embedding. We present a framework that augments a generic "typeless" embedding model to a typed one. The framework interprets an entity type as a constraint on the set of all entities and let these type constraints induce isomorphically a set of subsets in the embedding space. Additional cost functions are then introduced to model the fitness between these constraints and the embedding of entities and relations. A concrete example scheme of the framework is proposed. We demonstrate experimentally that this framework offers improved embedding performance over the typeless models and other typed models.

In this paper, we study the problem of question answering over knowledge base. We identify that the primary bottleneck in this problem is the difficulty in accurately predicting the relations connecting the subject entity to the object entities. We advocate a new model architecture, APVA, which includes a verification mechanism responsible for checking the correctness of predicted relations. The APVA framework naturally supports a well-principled iterative training procedure, which we call turbo training. We demonstrate via experiments that the APVA-TUBRO approach drastically improves the question answering performance.

We propose a novel strategy to encode the syntax parse tree of sentence into a learnable distributed representation.The proposed syntax encoding scheme is provably informationlossless.In specific, an embedding vector is constructed for each word in the sentence, encoding the path in the syntax tree corresponding to the word.The one-to-one correspondence between these "syntax-embedding" vectors and the words (hence their embedding vectors) in the sentence makes it easy to integrate such a representation with all word-level NLP models.We empirically show the benefits of the syntax embeddings on the Authorship Attribution domain, where our approach improves upon the prior art and achieves new performance records on five benchmarking data sets.

Building knowledge base embedding models for link prediction has achieved great success. We however argue that the conventional top-k criterion used for evaluating the model performance is inappropriate. This paper introduces a new criterion, referred to as max-k. Through theoretical analysis and experimental study, we show that the top-k criterion is fundamentally inferior to max-k. We also introduce two prediction protocols for the max-k criterion. These protocols are strongly justified theoretically. Various insights concerning the max-k criterion and the two protocols are obtained through extensive experiments.

The knowledge base (KB) completion problem is usually formulated as a link prediction problem. Such formulation is incapable of capturing certain application scenarios when the KB contains multi-fold relations. In this paper, we present a new formulation of KB completion, called instance reconstruction. Unlike its link-prediction counterpart, which has linear complexity in the size of the KB, this problem has its complexity behave as a high-degree polynomial. This presents a significant challenge in developing scalable instance reconstruction algorithms. In this paper, we present a novel knowledge embedding model (RAE) and build on it an instance reconstruction algorithm (SIR). The SIR algorithm utilizes schema-based filtering as well as "relatedness" filtering for complexity reduction. Here relatedness refers to the likelihood that two entities co-participate in a common instance, and the relatedness metric is learned from the RAE model. We show experimentally that SIR significantly reduces computation complexity without sacrificing reconstruction performance. The complexity reduction corresponds to reducing the KB size by 100 to 1000 folds.

One of the most important crowdsourcing topics is to study the effective quality control methods so as to reduce the cost and to guarantee the quality of task processing. As an effective approach, iterative improvement workflow is known to choose the best result from multiple workflows. However, for complex crowdsourcing tasks that consists of a certain number of subtasks under some specific constraints, but cannot be split into subtasks to be crowdsourced, the approach merely considers the best workflow without integrating the contributions of all workflows, which potentially results in extra costs for more iterations. In this paper, we propose an assembly model to integrate the best output of subtasks from different workflows. Moreover, we devise an efficient iterative method based on POMDP to improve the quality of assembled output. Empirical studies confirms the superiority of our proposed model.

In this paper, we show analytically that the duality of normal factor graphs (NFG) can facilitate stochastic estimation of partition functions. In particular, our analysis suggests that for the q-ary two-dimensional nearest-neighbor Potts model, sampling from the primal NFG of the model and sampling from its dual exhibit opposite behaviours with respect to the temperature of the model. For high-temperature models, sampling from the primal NFG gives rise to better estimators whereas for low-temperature models, sampling from the dual gives rises to better estimators. This analysis is validated by experiments.

The prediction of trust relationships in social networks plays an important role in the analytics of the networks. Although various link prediction algorithms for general networks may be adapted for this purpose, the recent notion of “trust propagation” has been shown to effectively capture the trust-formation mechanisms and resulted in an effective prediction algorithm. This article builds on the concept of trust propagation and presents a probabilistic trust propagation model. Our model exploits the modern framework of probabilistic graphical models, more specifically, factor graphs. Under this model, the trust prediction problem can be formulated as a statistical inference problem and we derive the belief propagation algorithm as a solver for trust prediction. The model and algorithm are tested using datasets from Epinions and Ciao, by which performance advantages over the previous algorithms are demonstrated.

Exploiting the recent framework of normal factor graphs, this paper presents a transparent exposition of the Krawtchouk transform and its relationship to the Fourier transform and the MacWilliams identities. Such treatment of the subject is believed to be more accessible to wider audience of coding theory.

SUMMARY This paper studies the problem of designing real‐time helpfulness prediction algorithms. Instead of following the conventional route, in which the fraction of positive votes is used as the measure of helpfulness, we give ‘helpfulness’ a naturally sensible and mathematically precise definition, namely, as the probability that a user will vote ‘helpful’ on the user‐generated content. Building on this definition, we introduce a principled methodology to helpfulness prediction, in which the prediction problem is naturally formulated as an optimization problem. Under this proposed methodology, we first develop a batch (off‐line) algorithm. Experiments on data from Amazon.com suggest that our proposed model in fact outperforms the previously reported prediction algorithm, support vector regression. In some circumstances, an online algorithm that can update the model as additional data arrive is required. In light of this, we proposed an online algorithm that incrementally updates the parameters of the model. Finally, an efficient hybrid algorithm is provided to increase the convergence rate and prediction precision. The final two algorithms are tested on real‐life user‐generated contents, and experimental results illustrate that the hybrid approach efficiently processes incoming data and generates reliable helpfulness predictions for users. Copyright © 2011 John Wiley & Sons, Ltd.

Inspired by some new advances on normal factor graphs (NFGs), we introduce NFGs as a simple and intuitive diagrammatic approach towards encoding some concepts from linear algebra. We illustrate with examples the workings of such an approach and settle a conjecture of Peterson on the Pfaffian.

This paper stands at the intersection of two distinct lines of research. One line is “holographic algorithms,” a powerful approach introduced by Valiant for solving various counting problems in computer science; the other is “normal factor graphs,” an elegant framework proposed by Forney for representing codes defined on graphs. We introduce the notion of holographic transformations for normal factor graphs, and establish a very general theorem, called the generalized Holant theorem, which relates a normal factor graph to its holographic transformation. We show that the generalized Holant theorem on the one hand underlies the principle of holographic algorithms, and on the other hand reduces to a general duality theorem for normal factor graphs, a special case of which was first proved by Forney. In the course of our development, we formalize a new semantics for normal factor graphs, which highlights various linear algebraic properties that potentially enable the use of normal factor graphs as a linear algebraic tool.

Under the tuple-level uncertainty paradigm, we introduce a novel graphical model, Generator-Recognizer Network (GRN), as a model for probabilistic databases. The GRN modeling framework extends existing graphical models of probabilistic databases and is capable of representing a much wider range of dependence structures.

In his recent work, Valiant presented a powerful family of new algorithms, which he calls holographic algorithms. The mathematical foundation of holographic algorithms is what is known as Holant Theorem. Synthesizing from Valiant's work, in this paper, we introduce the notion of Valiant transform for normal graphs. Exploiting this synthesis, we establish a more general version of Holant Theorem, which allows an alternative interpretation of the duality results on normal graphs.

Under the tuple-level uncertainty paradigm, we formalize the use of a novel graphical model, Generator-Recognizer Network (GRN), as a model of probabilistic databases. The GRN modeling framework is capable of representing a much wider range of tuple dependency structure. We show that a GRN representation of a probabilistic database may undergo transitions induced by imposing constraints or evaluating queries. We formalize procedures for these two types of transitions such that the resulting graphical models after transitions remain as GRNs. This formalism makes GRN a self-contained modeling framework and a closed representation system for probabilistic databases - a property that is lacking in most existing models. In addition, we show that exploiting the transitional mechanisms allows a systematic approach to constructing GRNs for arbitrary probabilistic data at arbitrary stages. Advantages of GRNs in query evaluation are also demonstrated.

The survey propagation (SP) algorithm for solving$k$-SAT problems has been shown recently as an instance of the belief propagation (BP) algorithm. In this paper, we show that for general constraint-satisfaction problems, SP may not be reducible from BP. We also establish the conditions under which such a reduction is possible. Along our development, we present a unification of the existing SP algorithms in terms of a probabilistically interpretable iterative procedure — weighted probabilistic token passing.

This paper studies the problem of Raptor-code design for binary-input AWGN (BIAWGN) channels using the mean-LLR-EXIT chart approach presented. We report that there exist situations where such a design approach may fail or fail to produce capacity-achieving codes, for certain ranges of channel SNR. Suggestions and discussions are provided pertaining to the design of Raptor codes for BIAWGN channels using the mean-LLR-EXIT chart.

This paper studies the problem of Raptor-code design for binary-input AWGN (BIAWGN) channels using the mean-LLR-EXIT chart approach presented in [1]. We report that there exist situations where such a design approach may fail or fail to produce capacity-achieving codes, for certain ranges of channel SNR. Suggestions and discussions are provided pertaining to the design of Raptor codes for BIAWGN channels using the mean-LLR-EXIT chart.

We propose a novel coding framework for wireless relay channels based on rateless codes, which allows for a natural extension to multiple antenna and multiple relay settings. The relaying protocol is half-duplex, and relays independently choose when to collaborate, if at all. With a simulated fountain code based implementation of this framework, we show that the use of rateless codes is both robust and efficient when the channel state information is not available at the transmitters

Fountain codes are a universal class of rateless codes originally designed for erasure channels. Naturally adapting to channel states without channel knowledge at the transmitter, fountain codes have recently been demonstrated also as an appealing solution for communication over fading channels. However, their relatively high decoding complexity limits their practical use in a wireless setting. In this paper, we present a simple modification of the decoding algorithm for Raptor codes - a type of fountain codes - over fading channels, where the complexity is significantly reduced without sacrifice of performance.

We explore the use of rateless coding for communication over fading channels with delay constraints. Both quasi-static fading and block-fading channels are considered. When only the receiver has channel information, we show there exist rateless codes that are both reliable and efficient for every channel realization of such channels. We then apply these codes to a wireless streaming application with a sequence of playback deadlines. Rateless strategies demonstrate benefits in terms of throughput and outage probability compared to fixed-rate schemes

A celebrated algorithmic discovery in solving constraint satisfaction problems, survey propagation (SP) and its generalization have recently demonstrated their power in areas of communications and data compression. It is known that under certain Markov random field (MRF) formalism of k-SAT problems, SP may be interpreted as an instance of belief propagation (BP). In this paper, we borrow the notion of generalized states from system theory and coding theory, and introduce a new MRF formalism - normal realization - for k-SAT problems. We show that when BP applies to this MRF, generalized SP is resulted. This new MRF formalism appears to be simpler than the existing one and the interpretation of SP as BP in this framework also appears more transparent

We propose a novel coding framework for wireless relay channels based on rateless codes. With a concrete Fountain-code implementation of this framework, we show that rateless codes are both robust and efficient when the channel state information is not available at the transmitters

The highly stochastic nature of wireless environments makes it desirable to monitor link loss rates in wireless sensor networks. In a wireless sensor network, link loss monitoring is particularly supported by the data aggregation communication paradigm of network traffic: the data collecting node can infer link loss rates on all links in the network by exploiting whether packets from various sensors are received, and there is no need to actively inject probing packets for inference purposes. In this paper, we present a low complexity algorithmic framework for link loss monitoring based on the recent modeling and computational methodology of factor graphs. The proposed algorithm iteratively updates the estimates of link losses upon receiving (or detecting the loss of) recently sent packets by the sensors. The algorithm exhibits good performance and scalability, and can be easily adapted to different statistical models of networking scenarios. In particular, due to its low complexity, the algorithm is particularly suitable as a long-term monitoring facility.

We introduce the concept of convolutional factor graphs, which represent convolutional factorizations of multivariate functions, just as conventional (multiplicative) factor graphs represent multiplicative factorizations. Convolutional and multiplicative factor graphs arise as natural Fourier transform duals. In coding theory applications, algebraic duality of group codes is essentially an instance of Fourier transform duality. Convolutional factor graphs arise when a code is represented as a sum of subcodes, just as conventional multiplicative factor graphs arise when a code is represented as an intersection of supercodes. With auxiliary variables, convolutional factor graphs give rise to "syndrome realizations" of codes, just as multiplicative factor graphs with auxiliary variables give rise to "state realizations." We introduce normal and co-normal extensions of a multivariate function, which essentially allow a given function to be represented with either a multiplicative or a convolutional factorization, as is convenient. We use these function extensions to derive a number of duality relationships among the corresponding factor graphs, and use these relationships to obtain the duality properties of Forney graphs as a special case.

The best known practical algorithm for the decoding of low-density parity-check (LDPC) codes is the iterative sum-product or belief propagation algorithm, operating on a Tanner graph (TG) of the code. Conventionally, in each iteration, all the symbol nodes and subsequently all the check nodes in the TG pass new messages to their neighbors (the so-called "flooding schedule"). We propose a new message-passing schedule, called "probabilistic schedule". Unlike flooding, the probabilistic schedule operation is based on the structure of the TG, and probabilistically balances the frequency at which different symbol nodes update their outgoing messages in accordance with their girths. Our results show that, particularly for short block lengths, the new schedule offers a much better performance/complexity trade-off. For a particular example of a (1268, 456) code, at no cost in complexity, the probabilistic schedule not only decreases both the bit and message error rates by an order of magnitude, but also reduces the number of undetected errors considerably. This work shows the importance of scheduling in the performance of iterative decoding algorithms and suggests that a schedule which matches the structure of the TG can substantially improve the performance/complexity trade-off in the decoding of short LDPC codes.

For a given block length and given degree sequences of the underlying Tanner graph (TG), the ensemble of short low-density parity-check (LDPC) codes can have considerable variation in performance. We present an efficient heuristic method to find good LDPC codes based on what we define as the girth distribution of the TG. This method can be used effectively to design short codes for applications where delay and complexity are of major concern.