Recent advances in Large Language Models (LLMs) - particularly model scaling and test-time techniques - have greatly enhanced the reasoning capabilities of language models at the expense of higher inference costs. To lower inference costs, prior works train router models or deferral mechanisms that allocate easy queries to a small, efficient model, while forwarding harder queries to larger, more expensive models. However, these trained router models often lack robustness under domain shifts and require expensive data synthesis techniques such as Monte Carlo rollouts to obtain sufficient ground-truth routing labels for training. In this work, we propose Confidence-Guided Stepwise Model Routing for Cost-Efficient Reasoning (STEER), a domain-agnostic, framework that performs fine-grained, step-level routing between smaller and larger LLMs without utilizing external models. STEER leverages confidence scores from the smaller model’s logits prior to generating a reasoning step, so that the large model is invoked only when necessary. Extensive evaluations using different LLMs on a diverse set of challenging benchmarks across multiple domains such as Mathematical Reasoning, Multi-Hop QA, and Planning tasks indicate that STEER achieves competitive or enhanced accuracy while reducing inference costs (up to +20% accuracy with 48% less FLOPs compared to solely using the larger model on AIME), outperforming baselines that rely on trained external modules. Our results establish model-internal confidence as a robust, domain-agnostic signal for model routing, offering a scalable pathway for efficient LLM deployment.

Story visualization requires generating a coherent sequence of images that collectively form a narrative, yet existing evaluation metrics and datasets often overlook visual continuity and narrative diversity.In this paper, we introduce the Visual Context-Aware Metric for Story Visualization (VCMS), which uses large vision-language models to jointly assess caption fidelity and inter-image consistency, achieving Spearman's correlation comparable to human agreement on two benchmarks.Also, to address the shortcomings of narrowly defined datasets with low diversity, we propose a diffusion-augmented evaluation pipeline that blends diverse and controlled narrative elements at adjustable ratios, enabling the creation of evaluation sets tailored to specific objectives.By combining VCMS with this pipeline, we provide a scalable, human-aligned framework for evaluating story visualization models.

Large language models leverage both parametric knowledge acquired during pretraining and in-context knowledge provided at inference time.Crucially, when these sources conflict, models arbitrate based on their internal confidence, preferring parametric knowledge for high-confidence facts while deferring to context for less familiar ones.However, the training conditions that give rise to these fundamental behaviors remain unclear.Here we conduct controlled experiments using synthetic corpora to identify the specific data properties that shape knowledge utilization.Our results reveal a counterintuitive finding: the robust, balanced use of both knowledge sources is an emergent property that requires the cooccurrence of three factors typically considered detrimental, including (i) intra-document repetition, (ii) a moderate degree of intra-document inconsistency, and (iii) a skewed knowledge distribution.We further show that these dynamics arise in real-world language model pretraining and analyze how post-training procedures reshape arbitration strategies.Together, our findings provide empirical guidance for designing training data that supports the reliable integration of parametric and in-context knowledge in language models.

Despite the fact that large language models (LLMs) show exceptional skill in instruction following tasks, this strength can turn into a vulnerability when the models are required to disregard certain instructions.Instruction following tasks typically involve a clear task description and input text containing the target data to be processed.However, when the input itself resembles an instruction, confusion may arise, even if there is explicit prompting to distinguish between the task instruction and the input.We refer to this phenomenon as instructional distraction.In this paper, we introduce a novel benchmark, named DIM-Bench, specifically designed to assess LLMs' performance under instructional distraction.The benchmark categorizes real-world instances of instructional distraction and evaluates LLMs across four instruction tasks: rewriting, proofreading, translation, and style transfer-alongside five input tasks: reasoning, code generation, mathematical reasoning, bias detection, and question answering.Our experimental results reveal that even the most advanced LLMs are susceptible to instructional distraction, often failing to accurately follow user intent in such cases. Instruction Input ExampleRewrite Reasoning Instruction: Paraphrase the following text.Input: Laundry detergents were once manufactured to contain high ... which would a lake become as a result of the phosphorous in the detergent?Options : A. canyon B. desert C. swamp D. river

Enabled by large-scale text corpora with huge parameters, pre-trained language models operate as multi-task experts using a single model architecture. However, recent studies have revealed that certain neurons play disproportionately important roles in solving specific tasks, suggesting that task-relevant substructures can be isolated and selectively activated for each task. Therefore, we introduce Decomposition of Experts (DoE), a novel framework that dynamically identifies and activates task-specific experts within a language model to reduce inference cost without sacrificing accuracy. We first define a task expert as a set of parameters that significantly influence the performance of a specific task and propose a four-step unplug-and-play process: (1) receiving a user request, (2) identifying the corresponding task expert, (3) performing inference using the expert-localized model, and (4) restoring the original model and waiting for the next task. Using attribution methods and prompt tuning, DoE isolates task-relevant neurons, minimizing computational overhead while maintaining task performance. We assume a setting where a language model receives user requests from five widely used natural language understanding benchmarks, processing one task at a time. In this setup, we demonstrate that DoE achieves up to a x1.73 inference speed-up with a 65% pruning rate, without compromising accuracy. Comparisons with various task expert localization methods reveal that DoE effectively identifies task experts, while ablation studies validate the importance of its components. Additionally, we analyze the effects of batch size, token count, and layer types on inference speed-up, providing practical insights for adopting DoE. The proposed framework is both practical and scalable, applicable to any transformer-based architecture, offering a robust solution for efficient task-specific inference.

Recently, directly using large language models (LLMs) has been shown to be the most reliable method to evaluate QA models. However, it suffers from limited interpretability, high cost, and environmental harm. To address these, we propose to use soft exact match (EM) with entity-driven answer set expansion. Our approach expands the gold answer set to include diverse surface forms, based on the observation that the surface forms often follow particular patterns depending on the entity type. The experimental results show that our method outperforms traditional evaluation methods by a large margin. Moreover, the reliability of our evaluation method is comparable to that of LLM-based ones, while offering the benefits of high interpretability and reduced environmental harm.

Recently, large vision–language models (LVLMs) have emerged as the preferred tools for judging text–image alignment, yet their robustness along the visual modality remains underexplored. This work is the first study to address a key research question: Can adversarial visual manipulations systematically fool LVLM judges into assigning unfairly inflated scores? We define potential image-induced biases within the context of T2I evaluation and examine how these biases affect the evaluations of LVLM judges. Moreover, we introduce a novel, fine-grained, multi-domain meta-evaluation benchmark named FRAME, which is deliberately constructed to exhibit diverse score distributions. By introducing the defined biases into the benchmark, we reveal that all tested LVLM judges exhibit vulnerability across all domains, consistently inflating scores for manipulated images. Further analysis reveals that combining multiple biases amplifies their effects, and pairwise evaluations are similarly susceptible. Moreover, we observe that visual biases persist despite prompt-based mitigation strategies, highlighting the vulnerability of current LVLM evaluation systems and underscoring the urgent need for more robust LVLM judges.

Large Language Models (LLMs) have demonstrated remarkable capabilities across diverse tasks, but their potential misuse for harmful purposes remains a significant concern.To strengthen defenses against such vulnerabilities, it is essential to investigate universal jailbreak attacks that exploit intrinsic weaknesses in the architecture and learning paradigms of LLMs.In response, we propose Harmful Prompt Laundering (HaPLa), a novel and broadly applicable jailbreaking technique that requires only black-box access to target models.HaPLa incorporates two primary strategies: 1) abductive framing, which instructs LLMs to infer plausible intermediate steps toward harmful activities, rather than directly responding to explicit harmful queries; and 2) symbolic encoding, a lightweight and flexible approach designed to obfuscate harmful content, given that current LLMs remain sensitive primarily to explicit harmful keywords.Experimental results show that HaPLa achieves over 95% attack success rate on GPT-series models and 70% across all targets.Further analysis with diverse symbolic encoding rules also reveals a fundamental challenge: it remains difficult to safely tune LLMs without significantly diminishing their helpfulness in responding to benign queries.

Recent advances in LLM agents have largely built on reasoning backbones like ReAct (Yao et al., 2023), which interleaves thought and action in complex environments.However, Re-Act often produces ungrounded or incoherent reasoning steps, leading to misalignment between the agent's actual state and goal.Our analysis finds that this stems from ReAct's inability to maintain consistent internal beliefs and goal alignment, causing compounding errors and hallucinations.To address this, we introduce ReflAct, a novel backbone that shifts reasoning from merely planning next actions to continuously reflecting on the agent's state relative to its goal.By explicitly grounding decisions in states and enforcing ongoing goal alignment, ReflAct dramatically improves strategic reliability.This design delivers substantial empirical gains: ReflAct surpasses Re-Act by 27.7% on average, achieving a 93.3% success rate in ALFWorld.Notably, ReflAct even outperforms ReAct with added enhancement modules (e.g., Reflexion, WKM), showing that strengthening the core reasoning backbone is key to reliable agent performance.Observation: You pick up the apple 1 from the countertop 1. Thought: Now I take an apple 1.Next, I need to go to a microwave 1 and heat it.Action: go to microwave 1 Observation: The microwave 1 is closed.Thought: The microwave 1 is closed, so I need to open it first.Action: open microwave 1 Observation: You open the microwave 1.The microwave 1 is open.In it, you see nothing.

Although auto-regressive models excel in natural language processing, they often struggle to generate diverse text and provide limited controllability.Non-auto-regressive methods could be an alternative but often produce degenerate outputs and exhibit shortcomings in conditional generation.To address these challenges, we propose Diffusion-EAGS, a novel framework that integrates conditional masked language models into diffusion language models through the theoretical lens of a conditional Markov Random Field.In doing so, we propose entropy-adaptive Gibbs sampling and entropybased noise scheduling to counterbalance each model's shortcomings.Experimental results show that Diffusion-EAGS outperforms baselines and achieves the best quality-diversity tradeoff, demonstrating its effectiveness in nonautoregressive text generation.Context Jake was playing with his toys.He accidentally broke his favorite one.He cried a lot over it.His parents decided to replace it for him.Keyword not stop Jake just could not stop crying.Jake feel It made Jake feel So much better.would enjoy Jake said he would enjoy the new toy Context Neil was in Sofia, Bulgaria.He was enjoying a trip backpacking through Europe....He thought the food and culture in

Large Language Models (LLMs) often generate repetitive and monotonous outputs, especially in tasks like story generation, due to limited creative diversity when given the same input prompt.To address this challenge, we propose a novel decoding strategy, Avoidance Decoding, that modifies token logits by penalizing similarity to previously generated outputs, thereby encouraging more diverse multi-branch stories.This penalty adaptively balances two similarity measures: (1) Concept-level Similarity Penalty, which is prioritized in early stages to diversify initial story concepts, and (2) Narrative-level Similarity Penalty, which is increasingly emphasized later to ensure natural yet diverse plot development.Notably, our method achieves up to 2.6 times higher output diversity and reduces repetition by an average of 30% compared to strong baselines, while effectively mitigating text degeneration.Furthermore, we reveal that our method activates a broader range of neurons, demonstrating that it leverages the model's intrinsic creativity.

Various studies have attempted to remove sensitive or private knowledge from a language model to prevent its unauthorized exposure.However, prior studies have overlooked the inherent complexity and interconnectedness of knowledge, which requires careful examination.To resolve this problem, we first define a new concept called superficial unlearning, which refers to the phenomenon where an unlearning method either fails to erase the interconnected knowledge it should remove or unintentionally erases irrelevant knowledge.Based on the definition, we introduce a novel benchmark, FAITHUN, to analyze and evaluate the faithfulness of unlearning in real-world knowledge QA settings.Furthermore, we propose a novel unlearning method, KLUE, which updates only knowledge-related neurons to achieve faithful unlearning.KLUE leverages a regularized explainability method to localize contextual knowledge neurons, updating only these neurons using carefully selected unforgotten samples.Experimental results demonstrate that existing unlearning methods fail to ensure faithful unlearning, while our method shows significant effectiveness in real-world QA unlearning.

As large language models (LLMs) are increasingly used across various applications, there is a growing need to control text generation to satisfy specific constraints or requirements. This raises a crucial question: Is it possible to guarantee strict constraint satisfaction in generated outputs while preserving the distribution of the original model as much as possible? We first define the ideal distribution — the one closest to the original model, which also always satisfies the expressed constraint — as the ultimate goal of guaranteed generation. We then state a fundamental limitation, namely that it is impossible to reach that goal through autoregressive training alone. This motivates the necessity of combining training-time and inference-time methods to enforce such guarantees. Based on this insight, we propose GUARD, a simple yet effective approach that combines an autoregressive proposal distribution with rejection sampling. Through GUARD’s theoretical properties, we show how controlling the KL divergence between a specific proposal and the target ideal distribution simultaneously optimizes inference speed and distributional closeness. To validate these theoretical concepts, we conduct extensive experiments on two text generation settings with hard-to-satisfy constraints: a lexical constraint scenario and a sentiment reversal scenario. These experiments show that GUARD achieves perfect constraint satisfaction while almost preserving the ideal distribution with highly improved inference efficiency. GUARD provides a principled approach to enforcing strict guarantees for LLMs without compromising their generative capabilities.

Minbeom Kim, Hwanhee Lee, Joonsuk Park, Hwaran Lee, Kyomin Jung. Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2025.

Dongryeol Lee, Yerin Hwang, Yongil Kim, Joonsuk Park, Kyomin Jung. Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2025.

Kang-il Lee, Hyukhun Koh, Dongryeol Lee, Seunghyun Yoon, Minsung Kim, Kyomin Jung. Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2025.

We introduce transductive program synthesis, a new formulation of the program synthesis task that explicitly leverages test inputs during synthesis. While prior approaches to program synthesis--whether based on natural language descriptions or input-output examples--typically aim to generalize from training examples, they often struggle with robustness, especially in real-world settings where training examples are limited and test inputs involve various edge cases. To address this, we propose a novel framework that improves robustness by treating synthesis as an active learning over a finite hypothesis class defined by programs' outputs. We use an LLM to predict outputs for selected test inputs and eliminate inconsistent hypotheses, where the inputs are chosen via a greedy maximin algorithm to minimize the number of LLM queries required. We evaluate our approach on four benchmarks: Playgol, MBPP+, 1D-ARC, and programmatic world modeling on MiniGrid. We demonstrate that our method significantly improves program synthesis in both accuracy and efficiency. We release our code at https://github.com/klee972/SYNTRA.

Instruction-following language models often show undesirable biases.These undesirable biases may be accelerated in the real-world usage of language models, where a wide range of instructions is used through zero-shot example prompting.To solve this problem, we first define the bias neuron, which significantly affects biased outputs, and prove its existence empirically.Furthermore, we propose a novel and practical bias mitigation method, CRISPR, to eliminate bias neurons of language models in instruction-following settings.CRISPR automatically determines biased outputs and categorizes neurons that affect the biased outputs as bias neurons using an explainability method.Experimental results demonstrate the effectiveness of our method in mitigating biases under zero-shot instruction-following settings without losing the model's task performance and existing knowledge.The experimental results reveal the generalizability of our method as it shows robustness under various instructions and datasets.Surprisingly, our method can mitigate the bias in language models by eliminating only a few neurons (at least three).

With the explosion of multimedia content, video moment retrieval (VMR), which aims to detect a video moment that matches a given text query from a video, has been studied intensively as a critical problem. However, the existing VMR framework evaluates video moment retrieval performance, assuming that a video is given, which may not reveal whether the models exhibit overconfidence in the falsely given video. In this paper, we propose the MVMR (Massive Videos Moment Retrieval for Faithfulness Evaluation) task that aims to retrieve video moments within a massive video set, including multiple distractors, to evaluate the faithfulness of VMR models. For this task, we suggest an automated massive video pool construction framework to categorize negative (distractors) and positive (false-negative) video sets using textual and visual semantic distance verification methods. We extend existing VMR datasets using these methods and newly construct three practical MVMR datasets. To solve the task, we further propose a strong informative sample-weighted learning method, CroCs, which employs two contrastive learning mechanisms: (1) weakly-supervised potential negative learning and (2) cross-directional hard-negative learning. Experimental results on the MVMR datasets reveal that existing VMR models are easily distracted by the misinformation (distractors), whereas our model shows significantly robust performance, demonstrating that CroCs is essential to distinguishing positive moments against distractors.

Existing English-based text similarity measurements primarily focus on the semantic dimension, neglecting the unique linguistic attributes found in languages like Korean, where honorific expressions are explicitly integrated. To address this limitation, this study proposes Kosmic, a novel Korean text-similarity metric that encompasses the semantic and tonal facets of a given text pair. For the evaluation, we introduce a novel benchmark annotated by human experts, empirically showing that Kosmic outperforms the existing method. Moreover, by leveraging Kosmic, we assess various Korean paraphrasing methods to determine which techniques are most effective in preserving semantics and tone.

Despite advancements in on-topic dialogue systems, effectively managing topic shifts within dialogues remains a persistent challenge, largely attributed to the limited availability of training datasets.To address this issue, we propose Multi-Passage to Dialogue (MP2D), a data generation framework that automatically creates conversational questionanswering datasets with natural topic transitions.By leveraging the relationships between entities in a knowledge graph, MP2D maps the flow of topics within a dialogue, effectively mirroring the dynamics of human conversation.It retrieves relevant passages corresponding to the topics and transforms them into dialogues through the passage-to-dialogue method.Through quantitative and qualitative experiments, we demonstrate MP2D's efficacy in generating dialogue with natural topic shifts.Furthermore, this study introduces a novel benchmark for topic shift dialogues, TS-WikiDialog.Utilizing the dataset, we demonstrate that even Large Language Models (LLMs) struggle to handle topic shifts in dialogue effectively, and we showcase the performance improvements of models trained on datasets generated by MP2D across diverse topic shift dialogue tasks.

Recently, Self-Supervised Features (SSF) trained on extensive speech datasets have shown significant performance gains across various speech processing tasks. Nevertheless, their effectiveness in Speech Enhancement (SE) systems is often suboptimal due to insufficient optimization for noisy environments. To address this issue, we present a novel methodology that directly utilizes SSFs extracted from clean speech for enhancing SE models. Specifically, we leverage the clean SSFs for latent space modeling within the Conditional Variational Autoencoder (CVAE) framework. Consequently, we enable our model to fully leverage the knowledge existing in the clean SSFs without the interference of noise. In experiments, our approach yields clear improvements over existing methods that use SSFs across six evaluation metrics. Furthermore, we provide comprehensive analyses to validate the effectiveness of 1) incorporating clean SSFs within the CVAE framework and 2) the training techniques used to achieve optimal performance from our approach in SE systems. Code and audio samples are available at https://github.com/YoonhyungLee94/SSFCVAE

Yunah Jang, Kang-il Lee, Hyunkyung Bae, Hwanhee Lee, Kyomin Jung. Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2024.

Minwoo Lee, Hyukhun Koh, Minsung Kim, Kyomin Jung. Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2024.

Despite the recent advances in dialogue state tracking (DST), the joint goal accuracy (JGA) of the existing methods on MultiWOZ 2.1 still remains merely 60%.In our preliminary error analysis, we find that beam search produces a pool of candidates that is likely to include the correct dialogue state.Motivated by this observation, we introduce a novel framework, called BREAK (Beam search and RE-rAnKing), that achieves outstanding performance on DST.Our proposed method performs DST in two stages: (i) generating k-best dialogue state candidates with beam search and (ii) re-ranking the candidates to select the correct dialogue state.This simple yet powerful framework shows state-of-the-art performance on all versions of MultiWOZ and M2M datasets.Most notably, we push the joint goal accuracy to 80-90% on MultiWOZ 2.1-2.4,which is an improvement of 23.6%, 26.3%, 21.7%, and 10.8% over the previous best-performing models, respectively.

Gender bias is a significant issue in machine translation, leading to ongoing research efforts in developing bias mitigation techniques.However, most works focus on debiasing bilingual models without much consideration for multilingual systems.In this paper, we specifically target the gender bias issue of multilingual machine translation models for unambiguous cases where there is a single correct translation, and propose a bias mitigation method based on a novel approach.Specifically, we propose Gender-Aware Contrastive Learning, GACL, which encodes contextual gender information into the representations of non-explicit gender words.Our method is target languageagnostic and is applicable to pre-trained multilingual machine translation models via finetuning.Through multilingual evaluation, we show that our approach improves gender accuracy by a wide margin without hampering translation performance.We also observe that incorporated gender information transfers and benefits other target languages regarding gender accuracy.Finally, we demonstrate that our method is applicable and beneficial to models of various sizes. 1

To address the data scarcity issue in Conversational question answering (ConvQA), a dialog inpainting method, which utilizes documents to generate ConvQA datasets, has been proposed.However, the original dialog inpainting model is trained solely on the dialog reconstruction task, resulting in the generation of questions with low contextual relevance due to insufficient learning of question-answer alignment.To overcome this limitation, we propose a novel framework called Dialogizer, which has the capability to automatically generate ConvQA datasets with high contextual relevance from textual sources.The framework incorporates two training tasks: question-answer matching (QAM) and topic-aware dialog generation (TDG).Moreover, re-ranking is conducted during the inference phase based on the contextual relevance of the generated questions.Using our framework, we produce four Con-vQA datasets by utilizing documents from multiple domains as the primary source.Through automatic evaluation using diverse metrics, as well as human evaluation, we validate that our proposed framework exhibits the ability to generate datasets of higher quality compared to the baseline dialog inpainting model.

With the rapid advancement in deep generative models, recent neural Text-To-Speech (TTS) models have succeeded in synthesizing humanlike speech.There have been some efforts to generate speech with various prosody beyond monotonous prosody patterns.However, previous works have several limitations.First, typical TTS models depend on the scaled sampling temperature for boosting the diversity of prosody.Speech samples generated at high sampling temperatures often lack perceptual prosodic diversity, thereby hampering the naturalness of the speech.Second, the diversity among samples is neglected since the sampling procedure often focuses on a single speech sample rather than multiple ones.In this paper, we propose DPP-TTS: a text-to-speech model based on Determinantal Point Processes (DPPs) with a new objective function and prosody diversifying module.Our TTS model is capable of generating speech samples that simultaneously consider perceptual diversity in each sample and among multiple samples.We demonstrate that DPP-TTS generates speech samples with more diversified prosody than baselines in the side-by-side comparison test considering the naturalness of speech at the same time.

The problem of spurious programs is a longstanding challenge when training a semantic parser from weak supervision.To eliminate such programs that have wrong semantics but correct denotation, existing methods focus on exploiting similarities between examples based on domain-specific knowledge.In this paper, we propose a domain-agnostic filtering mechanism based on program execution results.Specifically, for each program obtained through the search process, we first construct a representation that captures the program's semantics as execution results under various inputs.Then, we run a majority vote on these representations to identify and filter out programs with significantly different semantics from the other programs.In particular, our method is orthogonal to the program search process so that it can easily augment any of the existing weakly supervised semantic parsing frameworks.Empirical evaluations on the Natural Language Visual Reasoning and WIKITABLEQUESTIONS demonstrate that applying our method to the existing semantic parsers induces significantly improved performances.Code is available at https://github.com/klee972/exec-filter.

The inductive link prediction in knowledge graphs (KGs) is often addressed to induce logical rules that capture entity-independent relational semantics. Recent studies suggest graph representation learning to encode these logical rules within the local subgraph structures. With this approach, the model can have the inductive ability to cope with unseen entities, which is practical for evolving nature of real-world KGs. However, despite the importance of a high-quality negative sample in link prediction, there is currently no method for selecting hard negatives for inductive link prediction. To overcome this limitation, we propose a new sampling method for selecting hard negative samples given a positive triplet. We also propose Subgraph Infomax (SGI), a novel inductive link prediction model, with a newly-proposed training objective that maximizes the mutual information (MI) between the target relation and the enclosing subgraph. We select hard negative samples by using the pretrained MI estimator of SGI. The model is then fine-tuned using the selected hard negative samples. Empirically, we demonstrate superior performances of our model on multiple datasets of the inductive KGC benchmark, showing the enhanced connectivity between the target relation embedding and the subgraph representation.

There are two types of methods for non-autoregressive text-to-speech models to learn the one-to-many relationship between text and speech effectively. The first one is to use an advanced generative framework such as normalizing flow (NF). The second one is to use variance information such as pitch or energy together when generating speech. For the second type, it is also possible to control the variance factors by adjusting the variance values provided to a model. In this paper, we propose a novel model called VarianceFlow combining the advantages of the two types. By modeling the variance with NF, VarianceFlow predicts the variance information more precisely with improved speech quality. Also, the objective function of NF makes the model use the variance information and the text in a disentangled manner resulting in more precise variance control. In experiments, VarianceFlow shows superior performance over other state-of-the-art TTS models both in terms of speech quality and controllability.

Recently, Integrated Gradients-based (IG) methods have been commonly used to explain the decision process of deep neural networks (DNNs). However, they have only considered the information of the predicted class while neglecting the in-formation of the rest classes. In this paper, we propose a novel counterfactual explanation method, Discriminative Gradients (DiscGrad) that derives explainable discriminative attributes by considering not only the predicted class but also the counterfactual classes. Specifically, we calculate the discriminative attributes by removing the attribute of the counterfactual classes, and this process makes it possible to derive only key discriminative attributes that contrast with other decisions. Also, we determine the weights for discriminative attributes using the degree of confusion about counterfactual classes. We evaluated our method by measuring how much logit decreases by perturbing important attributes. Experimental results on the widely used image and text datasets show that our proposed method outperforms the strong baseline, IG. In addition, we examine the relationship between class correlation and the performance of discriminative attribute to demonstrate the effectiveness of our method.

Video-and-Language learning, such as video question answering or video captioning, is the next challenge in the deep learning society, as it pursues the way how human intelligence perceives everyday life. These tasks require the ability of multi-modal reasoning which is to handle both visual information and text information simultaneously across time. In this point of view, a cross-modality attention module that fuses video representation and text representation takes a critical role in most recent approaches. However, existing Video-and-Language models merely compute the attention weights without considering the different characteristics of video modality and text modality. Such na ̈ıve attention module hinders the current models to fully enjoy the strength of cross-modality. In this paper, we propose a novel Modality Alignment method that benefits the cross-modality attention module by guiding it to easily amalgamate multiple modalities. Specifically, we exploit Centered Kernel Alignment (CKA) which was originally proposed to measure the similarity between two deep representations. Our method directly optimizes CKA to make an alignment between video and text embedding representations, hence it aids the cross-modality attention module to combine information over different modalities. Experiments on real-world Video QA tasks demonstrate that our method outperforms conventional multi-modal methods significantly with +3.57% accuracy increment compared to the baseline in a popular benchmark dataset. Additionally, in a synthetic data environment, we show that learning the alignment with our method boosts the performance of the cross-modality attention.

Logical reasoning tasks over symbols, such as learning arithmetic operations and computer program evaluations, have become challenges to deep learning. In particular, even state-of-the-art neural networks fail to achieve \textit{out-of-distribution} (OOD) generalization of symbolic reasoning tasks, whereas humans can easily extend learned symbolic rules. To resolve this difficulty, we propose a neural sequence-to-grid (seq2grid) module, an input preprocessor that automatically segments and aligns an input sequence into a grid. As our module outputs a grid via a novel differentiable mapping, any neural network structure taking a grid input, such as ResNet or TextCNN, can be jointly trained with our module in an end-to-end fashion. Extensive experiments show that neural networks having our module as an input preprocessor achieve OOD generalization on various arithmetic and algorithmic problems including number sequence prediction problems, algebraic word problems, and computer program evaluation problems while other state-of-the-art sequence transduction models cannot. Moreover, we verify that our module enhances TextCNN to solve the bAbI QA tasks without external memory.

Targeted Opinion Word Extraction (TOWE) is a subtask of aspect-based sentiment analysis, which aims to identify the correspondingopinion terms for given opinion targets in a review. To solve theTOWE task, recent works mainly focus on learning the target-aware context representation that infuses target information intocontext representation by using various neural networks. However,it has been unclear how to encode the target information to BERT,a powerful pre-trained language model. In this paper, we proposea novel TOWE model, RABERT (Relation-Aware BERT), that canfully utilize BERT to obtain target-aware context representations.To introduce the target information into BERT layers clearly, wedesign a simple but effective encoding method that adds targetmarkers indicating the opinion targets to the sentence. In addi-tion, we find that the neighbor word information is also importantfor extracting the opinion terms. Therefore, RABERT employs thetarget-sentence relation network and the neighbor-aware relationnetwork to consider both the opinion target and the neighbor wordsinformation. Our experimental results on four benchmark datasetsshow that RABERT significantly outperforms the other baselinesand achieves state-of-the-art performance. We also demonstrate theeffectiveness of each component of RABERT in further analysis

Fact verification datasets are typically constructed using crowdsourcing techniques due to the lack of text sources with veracity labels. However, the crowdsourcing process often produces undesired biases in data that cause models to learn spurious patterns. In this paper, we propose CrossAug, a contrastive data augmentation method for debiasing fact verification models. Specifically, we employ a two-stage augmentation pipeline to generate new claims and evidences from existing samples. The generated samples are then paired cross-wise with the original pair, forming contrastive samples that facilitate the model to rely less on spurious patterns and learn more robust representations. Experimental results show that our method outperforms the previous state-of-the-art debiasing technique by 3.6% on the debiased extension of the FEVER dataset, with a total performance boost of 10.13% from the baseline. Furthermore, we evaluate our approach in data-scarce settings, where models can be more susceptible to biases due to the lack of training data. Experimental results demonstrate that our approach is also effective at debiasing in these low-resource conditions, exceeding the baseline performance on the Symmetric dataset with just 1% of the original data.

Hwanhee Lee, Seunghyun Yoon, Franck Dernoncourt, Doo Soon Kim, Trung Bui, Joongbo Shin, Kyomin Jung. Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2021.

Recently, BERT has shown overwhelming performance in sequential recommendation by using a bidirectional attention mechanism. Although the bidirectional model effectively captures dynamics from user interaction, its training strategy does not fit well to the inference stage in sequential recommendation which generally proceeds in a left-to-right way. To address this problem, we introduce a new recommendation system built upon BART, which is widely used in NLP tasks. BART uses a left-to-right decoder and injects noise into its bidirectional encoder, which can reduce the gap between training and inference. However, direct usage of BART for recommendation system is challenging due to its model property and domain difference. BART is an auto-regressive generative model, and its noising transformation techniques are originally developed for text sequence. In this paper, we present a novel sequential recommendation model, Entangled BART for Recommendation (E-BART4Rec) that entangles bidirectional encoder and auto-regressive decoder with noisy transformations for user interaction. Unlike BART, where the final output only depends on its output of the decoder, E-BART4Rec dynamically integrates the output of the bidirectional encoder and auto-regressive decoder based on a gating mechanism that calculates the importance of each output. We also employ noisy transformation that imitates the real users' behaviors, such as item deletion, item cropping, item reverse, and item infilling, to the input of the encoder. Extensive experiments on widely used real-world datasets demonstrate that our models significantly outperform the baselines.

OBJECTIVE: We propose an interpretable disease prediction model that efficiently fuses multiple types of patient records using a self-attentive fusion encoder. We assessed the model performance in predicting cardiovascular disease events, given the records of a general patient population. MATERIALS AND METHODS: We extracted 798111 ses and 67 623 controls from the sample cohort database and nationwide healthcare claims data of South Korea. Among the information provided, our model used the sequential records of medical codes and patient characteristics, such as demographic profiles and the most recent health examination results. These two types of patient records were combined in our self-attentive fusion module, whereas previously dominant methods aggregated them using a simple concatenation. The prediction performance was compared to state-of-the-art recurrent neural network-based approaches and other widely used machine learning approaches. RESULTS: Our model outperformed all the other compared methods in predicting cardiovascular disease events. It achieved an area under the curve of 0.839, while the other compared methods achieved between 0.74111 d 0.830. Moreover, our model consistently outperformed the other methods in a more challenging setting in which we tested the model's ability to draw an inference from more nonobvious, diverse factors. DISCUSSION: We also interpreted the attention weights provided by our model as the relative importance of each time step in the sequence. We showed that our model reveals the informative parts of the patients' history by measuring the attention weights. CONCLUSION: We suggest an interpretable disease prediction model that efficiently fuses heterogeneous patient records and demonstrates superior disease prediction performance.

Fully Attentional Networks (FAN) like Transformer (Vaswani et al. 2017) has shown superior results in Neural Machine Translation (NMT) tasks and has become a solid baseline for translation tasks. More recent studies also have reported experimental results that additional contextual sentences improve translation qualities of NMT models (Voita et al. 2018; Müller et al. 2018; Zhang et al. 2018). However, those studies have exploited multiple context sentences as a single long concatenated sentence, that may cause the models to suffer from inefficient computational complexities and long-range dependencies. In this paper, we propose Hierarchical Context Encoder (HCE) that is able to exploit multiple context sentences separately using the hierarchical FAN structure. Our proposed encoder first abstracts sentence-level information from preceding sentences in a self-attentive way, and then hierarchically encodes context-level information. Through extensive experiments, we observe that our HCE records the best performance measured in BLEU score on English-German, English-Turkish, and English-Korean corpus. In addition, we observe that our HCE records the best performance in a crowd-sourced test set which is designed to evaluate how well an encoder can exploit contextual information. Finally, evaluation on English-Korean pronoun resolution test suite also shows that our HCE can properly exploit contextual information.

Even though BERT has achieved successful performance improvements in various supervised learning tasks, BERT is still limited by repetitive inferences on unsupervised tasks for the computation of contextual language representations.To resolve this limitation, we propose a novel deep bidirectional language model called a Transformer-based Text Autoencoder (T-TA).The T-TA computes contextual language representations without repetition and displays the benefits of a deep bidirectional architecture, such as that of BERT.In computation time experiments in a CPU environment, the proposed T-TA performs over six times faster than the BERT-like model on a reranking task and twelve times faster on a semantic similarity task.Furthermore, the T-TA shows competitive or even better accuracies than those of BERT on the above tasks.Code is available at https://github.com/joongbo/tta.

In this work, we explore the impact of visual modality in addition to speech and text for improving the accuracy of the emotion detection system. The traditional approaches tackle this task by independently fusing the knowledge from the various modalities for performing emotion classification. In contrast to these approaches, we tackle the problem by introducing an attention mechanism to combine the information. In this regard, we first apply a neural network to obtain hidden representations of the modalities. Then, the attention mechanism is defined to select and aggregate important parts of the video data by conditioning on the audio and text data. Furthermore, the attention mechanism is again applied to attend the essential parts of speech and textual data by considering other modalities. Experiments are performed on the standard IEMOCAP dataset using all three modalities (audio, text, and video). The achieved results show a significant improvement of 3.65% in terms of weighted accuracy compared to the baseline system.

In this paper, we propose a novel speech emotion recognition model called Cross Attention Network (CAN) that uses aligned audio and text signals as inputs. It is inspired by the fact that humans recognize speech as a combination of simultaneously produced acoustic and textual signals. First, our method segments the audio and the underlying text signals into equal number of steps in an aligned way so that the same time steps of the sequential signals cover the same time span in the signals. Together with this technique, we apply the cross attention to aggregate the sequential information from the aligned signals. In the cross attention, each modality is aggregated independently by applying the global attention mechanism onto each modality. Then, the attention weights of each modality are applied directly to the other modality in a crossed way, so that the CAN gathers the audio and text information from the same time steps based on each modality. In the experiments conducted on the standard IEMOCAP dataset, our model outperforms the state-of-the-art systems by 2.66% and 3.18% relatively in terms of the weighted and unweighted accuracy.

In this study, we propose a novel graph neural network called propagate-selector (PS), which propagates information over sentences to understand information that cannot be inferred when considering sentences in isolation. First, we design a graph structure in which each node represents an individual sentence, and some pairs of nodes are selectively connected based on the text structure. Then, we develop an iterative attentive aggregation and a skip-combine method in which a node interacts with its neighborhood nodes to accumulate the necessary information. To evaluate the performance of the proposed approaches, we conduct experiments with the standard HotpotQA dataset. The empirical results demonstrate the superiority of our proposed approach, which obtains the best performances, compared to the widely used answer-selection models that do not consider the intersentential relationship.

Some news headlines mislead readers with overrated or false information, and identifying them in advance will better assist readers in choosing proper news stories to consume. This research introduces million-scale pairs of news headline and body text dataset with incongruity label, which can uniquely be utilized for detecting news stories with misleading headlines. On this dataset, we develop two neural networks with hierarchical architectures that model a complex textual representation of news articles and measure the incongruity between the headline and the body text. We also present a data augmentation method that dramatically reduces the text input size a model handles by independently investigating each paragraph of news stories, which further boosts the performance. Our experiments and qualitative evaluations demonstrate that the proposed methods outperform existing approaches and efficiently detect news stories with misleading headlines in the real world.

Neural question generation (NQG) is the task of generating a question from a given passage with deep neural networks. Previous NQG models suffer from a problem that a significant proportion of the generated questions include words in the question target, resulting in the generation of unintended questions. In this paper, we propose answer-separated seq2seq, which better utilizes the information from both the passage and the target answer. By replacing the target answer in the original passage with a special token, our model learns to identify which interrogative word should be used. We also propose a new module termed keyword-net, which helps the model better capture the key information in the target answer and generate an appropriate question. Experimental results demonstrate that our answer separation method significantly reduces the number of improper questions which include answers. Consequently, our model significantly outperforms previous state-of-the-art NQG models.

Inspired by number series tests to measure human intelligence, we suggest number sequence prediction tasks to assess neural network models’ computational powers for solving algorithmic problems. We define the complexity and difficulty of a number sequence prediction task with the structure of the smallest automaton that can generate the sequence. We suggest two types of number sequence prediction problems: the number-level and the digit-level problems. The number-level problems format sequences as 2-dimensional grids of digits and the digit-level problems provide a single digit input per a time step. The complexity of a number-level sequence prediction can be defined with the depth of an equivalent combinatorial logic, and the complexity of a digit-level sequence prediction can be defined with an equivalent state automaton for the generation rule. Experiments with number-level sequences suggest that CNN models are capable of learning the compound operations of sequence generation rules, but the depths of the compound operations are limited. For the digitlevel problems, simple GRU and LSTM models can solve some problems with the complexity of finite state automata. Memory augmented models such as Stack-RNN, Attention, and Neural Turing Machines can solve the reverse-order task which has the complexity of simple pushdown automaton. However, all of above cannot solve general Fibonacci, Arithmetic or Geometric sequence generation problems that represent the complexity of queue automata or Turing machines. The results show that our number sequence prediction problems effectively evaluate machine learning models’ computational capabilities.

In automatic speech recognition, language models (LMs) have been used in many ways to improve performance. Some of the studies have tried to use bidirectional LMs (biLMs) for rescoring the $n$-best hypothesis list decoded from the acoustic model. Despite their theoretical advantages over conventional unidirectional LMs (uniLMs), previous biLMs have not given notable improvements compared to the uniLMs in the experiments. This is due to the architectural limitation that the rightward and leftward representations are not fused in the biLMs. Recently, BERT addressed the same issue by proposing the masked language modeling and achieved state-of-the-art performances in many downstream tasks by fine-tuning the pre-trained BERT. In this paper, we propose an effective sentence scoring method by adjusting the BERT to the $n$-best list rescoring task, which has no fine-tuning step. The core idea of how we modify the BERT for the rescoring task is bridging the gap between training and testing environments by considering the only masked language modeling within a single sentence. Experimental results on the LibriSpeech corpus show that the proposed scoring method using our biLM outperforms uniLMs for the $n$-best list rescoring, consistently and significantly in all experimental conditions. Additionally, an analysis about where word errors occur in a sentence demonstrates that our biLM is more robust than the uniLM especially when a recognized sentence is short or a misrecognized word is at the beginning of the sentence. Consequently, we empirically prove that the left and right representations should be fused in biLMs for scoring a sentence.

In this paper, we propose a novel method for a sentence-level answer-selection task that is a fundamental problem in natural language processing. First, we explore the effect of additional information by adopting a pretrained language model to compute the vector representation of the input text and by applying transfer learning from a large-scale corpus. Second, we enhance the compare-aggregate model by proposing a novel latent clustering method to compute additional information within the target corpus and by changing the objective function from listwise to pointwise. To evaluate the performance of the proposed approaches, experiments are performed with the WikiQA and TREC-QA datasets. The empirical results demonstrate the superiority of our proposed approach, which achieve state-of-the-art performance for both datasets.

In this paper, we are interested in exploiting textual and acoustic data of an utterance for the speech emotion classification task. The baseline approach models the information from audio and text independently using two deep neural networks (DNNs). The outputs from both the DNNs are then fused for classification. As opposed to using knowledge from both the modalities separately, we propose a framework to exploit acoustic information in tandem with lexical data. The proposed framework uses two bi-directional long short-term memory (BLSTM) for obtaining hidden representations of the utterance. Furthermore, we propose an attention mechanism, referred to as the multi-hop, which is trained to automatically infer the correlation between the modalities. The multi-hop attention first computes the relevant segments of the textual data corresponding to the audio signal. The relevant textual data is then applied to attend parts of the audio signal. To evaluate the performance of the proposed system, experiments are performed in the IEMOCAP dataset. Experimental results show that the proposed technique outperforms the state-of-the-art system by 6.5% relative improvement in terms of weighted accuracy.

Kernel methods are powerful tools for modeling nonlinear data. However, the amount of computation and memory required for kernel methods becomes the bottleneck when dealing with large-scale problems. In this paper, we propose Nested Nystrom Method (NNM) which achieves a delicate balance between the approximation accuracy and computational efficiency by exploiting the multilayer structure and multiple compressions. Even when the size of the kernel matrix is very large, NNM consistently decomposes very small matrices to update the eigen-decomposition of the kernel matrix. We theoretically show that NNM implicitly updates the principal subspace through the multiple layers, and also prove that its corresponding errors of rank-k PSD matrix approximation and kernel PCA (KPCA) are decreased by using additional sublayers before the final layer. Finally, we empirically demonstrate the decreasing property of errors of NNM with the additional sublayers through the experiments on the constructed kernel matrices of real data sets, and show that NNM effectively controls the efficiency both for rank-k PSD matrix approximation and KPCA.

Seunghyun Yoon, Joongbo Shin, Kyomin Jung. Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers). 2018.

Speech emotion recognition is a challenging task, and extensive reliance has been placed on models that use audio features in building well-performing classifiers. In this paper, we propose a novel deep dual recurrent encoder model that utilizes text data and audio signals simultaneously to obtain a better understanding of speech data. As emotional dialogue is composed of sound and spoken content, our model encodes the information from audio and text sequences using dual recurrent neural networks (RNNs) and then combines the information from these sources to predict the emotion class. This architecture analyzes speech data from the signal level to the language level, and it thus utilizes the information within the data more comprehensively than models that focus on audio features. Extensive experiments are conducted to investigate the efficacy and properties of the proposed model. Our proposed model outperforms previous state-of-the-art methods in assigning data to one of four emotion categories (i.e., angry, happy, sad and neutral) when the model is applied to the IEMOCAP dataset, as reflected by accuracies ranging from 68.8% to 71.8%.

The Nyström method has been one of the most effective techniques for kernel-based approach that scales well to large data sets. Since its introduction, there has been a large body of work that improves the approximation accuracy while maintaining computational efficiency. In this paper, we present a novel Nyström method that improves both accuracy and efficiency based on a new theoretical analysis. We first provide a generalized sampling scheme, CAPS, that minimizes a novel error bound based on the subspace distance. We then present our double Nyström method that reduces the size of the decomposition in two stages. We show that our method is highly efficient and accurate compared to other state-of-the-art Nyström methods by evaluating them on a number of real data sets.

The appearance of web-based crowdsourcing systems gives a promising solution to exploiting the wisdom of crowds efficiently in a short time with a relatively low budget. Despite their efficiency, crowdsourcing systems have an inherent problem in that responses from workers can be unreliable since workers are low-paid and have low responsibility. Although simple majority voting can be a solution, various research studies have sought to aggregate noisy responses to obtain greater reliability in results through effective techniques such as Expectation-Maximization (EM) based algorithms. While EM-based algorithms get the limelight in crowdsourcing systems due to their useful inference techniques, Karger et al. made a significant breakthrough by proposing a novel iterative algorithm based on the idea of low-rank matrix approximations and the message passing technique. They showed that the performance of their iterative algorithm is order-optimal, which outperforms majority voting and EM-based algorithms. However, their algorithm is not always applicable in practice since it can only be applied to binary-choice questions. Recently, they devised an inference algorithm for multi-class labeling, which splits each task into a bunch of binary-choice questions and exploits their existing algorithm. However, it has difficulty in combining into real crowdsourcing systems since it overexploits redundancy in that each split question should be queried in multiple times to obtain reliable results.

In this paper, for overlapping community detection, we propose a novel framework of the link-space transformation that transforms a given original graph into a link-space graph. Its unique idea is to consider topological structure and link similarity separately using two distinct types of graphs: the line graph and the original graph. For topological structure, each link of the original graph is mapped to a node of the link-space graph, which enables us to discover overlapping communities using non-overlapping community detection algorithms as in the line graph. For link similarity, it is calculated on the original graph and carried over into the link-space graph, which enables us to keep the original structure on the transformed graph. Thus, our transformation, by combining these two advantages, facilitates overlapping community detection as well as improves the resulting quality. Based on this framework, we develop the algorithm LinkSCAN that performs structural clustering on the link-space graph. Moreover, we propose the algorithm LinkSCAN* that enhances the efficiency of LinkSCAN by sampling. Extensive experiments were conducted using the LFR benchmark networks as well as some real-world networks. The results show that our algorithms achieve higher accuracy, quality, and coverage than the state-of-the-art algorithms.

Energy minimization algorithms, such as graph cuts, enable the computation of the MAP solution under certain probabilistic models such as Markov random fields. However, for many computer vision problems, the MAP solution under the model is not the ground truth solution. In many problem scenarios, the system has access to certain statistics of the ground truth. For instance, in image segmentation, the area and boundary length of the object may be known. In these cases, we want to estimate the most probable solution that is consistent with such statistics, i.e., satisfies certain equality or inequality constraints. The above constrained energy minimization problem is NP-hard in general, and is usually solved using Linear Programming formulations, which relax the integrality constraints. This paper proposes a novel method that directly finds the discrete approximate solution of such problems by maximizing the corresponding Lagrangian dual. This method can be applied to any constrained energy minimization problem whose unconstrained version is polynomial time solvable, and can handle multiple, equality or inequality, and linear or non-linear constraints. One important advantage of our method is the ability to handle second order constraints with both-side inequalities with a weak restriction, not trivial in the relaxation based methods, and show that the restriction does not affect the accuracy in our cases.We demonstrate the efficacy of our method on the foreground/background image segmentation problem, and show that it produces impressive segmentation results with less error, and runs more than 20 times faster than the state-of-the-art LP relaxation based approaches.

We study a minimum delay routing problem in the context of distributed networks with and without partial load information. Even though a general minimum delay routing problem is NP hard, assuming uniformly distributed K source-destination (SD) pairs at random, we provide a lower bound on the average delay and demonstrate by simulation that it is tight for a certain classes of regularly deployed networks. We also show that some routing in a distributed manner is enough to achieve asymptotically optimal load balancing with high probability as K tends to infinity. In order to set such routing, however, each SD pair should know global load information, which is unrealistic for most networks. We propose novel predetermined path routing algorithms in which each SD pair chooses its routing path only among a set of predetermined paths. We then propose an efficient way of distributed construction for predetermined paths that are able to distribute traffic over a network. Our predetermined path routing algorithms work in a fully distributed manner with very limited load information or without any load information. In various network models, we demonstrate by simulation that the delay of the predetermined path routing algorithms quickly converges to that of the distributed routing with global load information.

In this paper, we consider the Max-Weight protocol for routing and scheduling in wireless networks under an adversarial model. This protocol has received a significant amount of attention dating back to the papers of Tassiulas and Ephremides. In particular, this protocol is known to be throughput-optimal whenever the traffic patterns and propagation conditions are governed by a stationary stochastic process. However, the standard proof of throughput optimality (which is based on the negative drift of a quadratic potential function) does not hold when the traffic patterns and the edge capacity changes over time are governed by an arbitrary adversarial process. Such an environment appears frequently in many practical wireless scenarios when the assumption that channel conditions are governed by a stationary stochastic process does not readily apply. In this paper, we prove that even in the above adversarial setting, the Max-Weight protocol keeps the queues in the network stable (i.e., keeps the queue sizes bounded) whenever this is feasible by some routing and scheduling algorithm. However, the proof is somewhat more complex than the negative potential drift argument that applied in the stationary case. Our proof holds for any arbitrary interference relationships among edges. We also prove the same stability of ε-approximate Max-Weight under the adversarial model. We conclude the paper with a discussion of queue sizes in the adversarial model as well as a set of simulation results.

The problem of identifying rumors is of practical importance especially in online social networks, since information can diffuse more rapidly and widely than the offline counterpart. In this paper, we identify characteristics of rumors by examining the following three aspects of diffusion: temporal, structural, and linguistic. For the temporal characteristics, we propose a new periodic time series model that considers daily and external shock cycles, where the model demonstrates that rumor likely have fluctuations over time. We also identify key structural and linguistic differences in the spread of rumors and non-rumors. Our selected features classify rumors with high precision and recall in the range of 87% to 92%, that is higher than other states of the arts on rumor classification.

Influence maximization is the problem of selecting top k seed nodes in a social network to maximize their influence coverage under certain influence diffusion models. In this paper, we propose a novel algorithm IRIE that integrates the advantages of influence ranking (IR) and influence estimation (IE) methods for influence maximization in both the independent cascade (IC) model and its extension IC-N that incorporates negative opinion propagations. Through extensive experiments, we demonstrate that IRIE matches the influence coverage of other algorithms while scales much better than all other algorithms. Moreover IRIE is much more robust and stable than other algorithms both in running time and memory usage for various density of networks and cascade size. It runs up to two orders of magnitude faster than other state-of-the-art algorithms such as PMIA for large networks with tens of millions of nodes and edges, while using only a fraction of memory.

In this paper we consider the MAX-WEIGHT protocol for routing and scheduling in wireless networks under an adversarial model. This protocol has received a significant amount of attention dating back to the papers of Tassiulas and Ephremides. In particular, this protocol is known to be throughput-optimal whenever the traffic patterns and propagation conditions are governed by a stationary stochastic process. However, the standard proof of throughput optimality (which is based on the negative drift of a quadratic potential function) does not hold when the traffic patterns and the edge capacity changes over time are governed by an arbitrary adversarial process. Such an environment appears frequently in many practical wireless scenarios when the assumption that channel conditions are governed by a stationary stochastic process does not readily apply. In this paper we prove that even in the above adversarial setting, the MAX-WEIGHT protocol keeps the queues in the network stable (i.e. keeps the queue sizes bounded) whenever this is feasible by some routing and scheduling algorithm. However, the proof is somewhat more complex than the negative potential drift argument that applied in the stationary case. Our proof holds for any arbitrary interference relationships among edges. We also prove the stability of ε-approximate MAX-WEIGHT under the adversarial model. We conclude the paper with a discussion of queue sizes in the adversarial model as well as a set of simulation results.

We study a basic information ranking problem in networks where each node holds an individual preference over a set of items and the goal for each node is to identify a sorted list of items with the largest aggregate preference. We would like to achieve this with a fully decentralized algorithm that uses a limited per-node memory and limited pair-wise communications. We show how this problem can be reduced to a plurality selection problem where the goal for each node is to identify an item with the largest aggregate ranking score, and show that solving the reduced problem solves the original ranking problem with high probability. Then we introduce a simple and natural plurality selection algorithm for the selection over m > 1 items that uses only log2(m) + 1 bits of per-node memory and per pair-wise communication. We prove correctness of the algorithm with high probability as the number of nodes grows large for the case when each node communicates with any other node, and establish tight convergence time bounds. The information ranking problem studied in this paper is a basic ranking problem that arises in various applications such as sorting elements in distributed computing systems, parallel databases, and may as well serve as a model of decentralized inference and opinion formation in distributed environments.

Given a directed graph $G = (V,E)$ and an integer $k \geq 1$, a $k$-transitive-closure-spanner ($k$-TC-spanner) of $G$ is a directed graph $H = (V, E_H)$ that has (1) the same transitive-closure as $G$ and (2) diameter at most $k$. These spanners were implicitly studied in the context of circuit complexity, data structures, property testing, and access control, and properties of these spanners have been rediscovered over the span of 20 years. We abstract the common task implicitly tackled in these diverse applications as the problem of constructing sparse TC-spanners. We initiate the study of approximability of the size of the sparsest $k$-TC-spanner of a given directed graph. We completely resolve the approximability of $2$-TC-spanners, showing that it is $\Theta(\log n)$ unless $\textsf{P} = \textsf{NP}$. For $k>2$, we present a polynomial time algorithm that finds a $k$-TC-spanner with size within $O((n \log n)^{1-1/k})$ of the optimum. Our techniques also yield algorithms with the first nontrivial approximation ratio for well-studied problems on directed spanners when $k>3$: Directed $k$-Spanner, Client/Server Directed $k$-Spanner, and $k$-Diameter Spanning Subgraph. For constant $k \geq 3$, we show that the size of the sparsest $k$-TC-spanner is hard to approximate within a factor of $2^{\log^{1-\eps} n}$ for any $\eps \in (0,1)$ unless $\NP \subseteq \text{DTIME}(n^{\polylog n})$. Finally, we study the size of the sparsest $k$-TC-spanners for $H$-minor-free graph families. Combining our constructions with our insight that 2-TC-spanners can be used for designing property testers, we obtain a monotonicity tester with $O(\log^2 n /\eps)$ queries for any poset whose transitive reduction, when viewed as an undirected graph, is free of a fixed minor. Previously, the best upper bound on the query complexity for such graphs was $O(\sqrt{n/\eps})$.

Given a directed graph $G = (V,E)$ and an integer $k \geq 1$, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph $H = (V, E_H)$ that has (1) the same transitive-closure as G and (2) diameter at most k. Transitive-closure spanners are used in access control, property testing and data structures. We show a connection between 2-TC-spanners and local monotonicity filters. A local monotonicity filter, introduced by Saks and Seshadhri [SIAM J. Comput., pp. 2897–2926], is a randomized algorithm that, given access to an oracle for an almost monotone function $f : \{1,2,\dots,m\}^d \to \mathbb{R}$, can quickly evaluate a related function $g : \{1,2,\dots,m\}^d \to \mathbb{R}$ which is guaranteed to be monotone. Furthermore, the filter can be implemented in a distributed manner. We show that an efficient local monotonicity filter implies a sparse 2-TC-spanner of the directed hypergrid, providing a new technique for proving lower bounds for local monotonicity filters. Our connection is, in fact, more general: an efficient local monotonicity filter for functions on any partially ordered set (poset) implies a sparse 2-TC-spanner of the directed acyclic graph corresponding to the poset. We present nearly tight upper and lower bounds on the size of the sparsest 2-TC-spanners of the directed hypercube and hypergrid. These bounds imply stronger lower bounds for local monotonicity filters that nearly match the upper bounds of Saks and Seshadhri.

We consider optimizing the coalition structure in Coalitional Skill Games (CSGs), a succinct representation of coalitional games. In CSGs, the value of a coalition depends on the tasks its members can achieve. The tasks require various skills to complete them, and agents may have different skill sets. The optimal coalition structure is a partition of the agents to coalitions, that maximizes the sum of utilities obtained by the coalitions. We show that CSGs can represent any characteristic function, and consider optimal coalition structure generation in this representation. We provide hardness results, showing that in general CSGs, as well as in very restricted versions of them, computing the optimal coalition structure is hard. On the positive side, we show that the problem can be reformulated as constraint satisfaction on a hyper graph, and present an algorithm that finds the optimal coalition structure in polynomial time for instances with bounded tree-width and number of tasks.

In this paper, we propose a framework for isolating text regions from natural scene images. The main algorithm has two functions: it generates text region candidates, and it verifies of the label of the candidates (text or non-text). The text region candidates are generated through a modified K-means clustering algorithm, which references texture features, edge information and color information. The candidate labels are then verified in a global sense by the Markov Random Field model where collinearity weight is added as long as most texts are aligned. The proposed method achieves reasonable accuracy for text extraction from moderately difficult examples from the ICDAR 2003 database.

Motivated by applications of distributed linear estimation, distributed control, and distributed optimization, we consider the question of designing linear iterative algorithms for computing the average of numbers in a network. Specifically, our interest is in designing such an algorithm with the fastest rate of convergence given the topological constraints of the network. As the main result of this paper, we design an algorithm with the fastest possible rate of convergence using a nonreversible Markov chain on the given network graph. We construct such a Markov chain by transforming the standard Markov chain, which is obtained using the Metropolis-Hastings method. We call this novel transformationpseudo-lifting. We apply our method to graphs with geometry, or graphs with doubling dimension. Specifically, the convergence time of our algorithm (equivalently, the mixing time of our Markov chain) is proportional to the diameter of the network graph and hence optimal. As a byproduct, our result provides the fastest mixing Markov chain given the network topological constraints, and should naturally find their applications in the context of distributed optimization, estimation and control.

We consider a wireless network of n nodes that communicate over a common wireless medium under some interference constraints. Our work is motivated by the need for an efficient and distributed algorithm to determine the n2 dimensional unicast capacity region of such a wireless network. Equivalently, given a vector of end-to-end rates between various source-destination pairs, we seek to determine if it can be supported by the network through a combination of routing and scheduling decisions. This question is known to be NP-hard and hard to even approximate within n1-o(1)factor for general graphs. In this paper, we first show that the whole n2dimensional unicast capacity region can be approximated to (1 plusmn epsiv) factor in polynomial time, and in a distributed manner, whenever the Max Weight Independent Set (MWIS) problem can be approximated in a similar fashion for the corresponding topology. We then consider wireless networks which are usually formed between nodes that are placed in a geographic area and come endowed with a certain geometry, and argue that such situations do lead to approximations to the MWIS problem (in fact, in a completely distributed manner, in a time that is essentially linear in n). Consequently, this gives us a polynomial algorithm to approximate the capacity of wireless networks to arbitrary accuracy. This result hence, is in sharp contrast with previous works that provide algorithms with at least a constant factor loss. An important ingredient in establishing our result is the transient analysis of the maximum weight scheduling algorithm, which can be of interest in its own right.

We consider the question of computing Maximum A Posteriori (MAP) assignment in an arbitrary pair-wise Markov Random Field (MRF). We present a randomized iterative algorithm based on simple local updates. The algorithm, starting with an arbitrary initial assignment, updates it in each iteration by first, picking a random node, then selecting an (appropriately chosen) random local neighborhood and optimizing over this local neighborhood. Somewhat surprisingly, we show that this algorithm finds a near optimal assignment within $2n\ln n$ iterations on average and with high probability for {\em any} $n$ node pair-wise MRF with {\em geometry} (i.e. MRF graph with polynomial growth) with the approximation error depending on (in a reasonable manner) the geometric growth rate of the graph and the average radius of the local neighborhood -- this allows for a graceful tradeoff between the complexity of the algorithm and the approximation error. Through extensive simulations, we show that our algorithm finds extremely good approximate solutions for various kinds of MRFs with geometry.

We define the notion of a transitive-closure spanner of a directed graph. Given a directed graph G = (V, E) and an integer k ≥ 1, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph H = (V, EH) that has (1) the same transitive-closure as G and (2) diameter at most k. These spanners were studied implicitly in access control, property testing, and data structures, and properties of these spanners have been rediscovered over the span of 20 years. We bring these areas under the unifying framework of TC-spanners. We abstract the common task implicitly tackled in these diverse applications as the problem of constructing sparse TC-spanners. We study the approximability of the size of the sparsest k-TC-spanner for a given digraph. Our technical contributions fall into three categories: algorithms for general digraphs, inapproximability results, and structural bounds for a specific graph family which imply an efficient algorithm with a good approximation ratio for that family. Algorithms. We present two efficient deterministic algorithms that find k-TC-spanners of near optimal size. The first algorithm gives an -approximation for k > 2. Our method, based on a combination of convex programming and sampling, yields the first sublinear approximation ratios for (1) Directed k-Spanner, a well-studied generalization of k-TC-Spanner, and (2) its variants Client/Server Directed k-Spanner, and the k-Diameter Spanning Subgraph. This resolves the main open question of Elkin and Peleg (IPCO, 2001). The second algorithm, specific to the k-TC-spanner problem, gives an -approximation. It shows that for , our problem has a provably better approximation ratio than Directed k-Spanner and its variants. This algorithm also resolves an open question of Hesse (SODA, 2003).

For a real-valued functionfdefined on {0,1}n, the linkage graph offis a hypergraph that represents the interactions among the input variables with respect tof. In this paper, lower and upper bounds for the number of function evaluations required to discover the linkage graph are rigorously analyzed in the black box scenario. First, a lower bound for discovering linkage graph is presented. To the best of our knowledge, this is the first result on the lower bound for linkage discovery. The investigation on the lower bound is based on Yao's minimax principle. For the upper bounds, a simple randomized algorithm for linkage discovery is analyzed. Based on the Kruskal-Katona theorem, we present an upper bound for discovering the linkage graph. As a corollary, we rigorously prove thatO(n2logn) function evaluations are enough for bounded functions when the number of hyperedges isO(n), which was suggested but not proven in previous works. To see the typical behavior of the algorithm for linkage discovery, three random models of fitness functions are considered. Using probabilistic methods, we prove that the number of function evaluations on the random models is generally smaller than the bound for the arbitrary case. Finally, from the relation between the linkage graph and the Walsh coefficients, it is shown that, for bounded functions, the proposed bounds are eventually the bounds for finding the Walsh coefficients.

Rate allocation is a fundamental problem in the operation of a wireless network because of the necessity to schedule the operation of mutually interfering links between the nodes. Among the many reasons behind the importance of efficiently determining the membership of an arbitrary rate vector in the feasibility region, is its high relevance in optimal cross layer design. A key feature in a wireless network is that links without common nodes can also conflict (secondary interference constraints). While the node exclusive model problem has efficient algorithms, it has long been known that this is a hard problem with these additional secondary constraints. However, wireless networks are usually deployed in geographic areas that do not span the most general class of all graphs possible. This is the underlying theme of this paper, where we provide algorithms for two restricted instances of wireless network topologies. In the first tractable instance, we consider nodes placed arbitrarily in a region such that (a) the node density is bounded, and (b) a node can only transmit or interfere with other nodes that are within a certain limited radius. We obtain a simple (1 - epsi) polynomial-time approximation scheme for checking feasibility (for any epsi > 0). The second instance considers the membership problem of an arbitrary rate-vector in the feasible set, where the nodes are distributed within a slab of fixed width (there are no density assumptions). Specifically, the results in [13] are shown to extend to a much more general class of graphs, which we call the (dmin,dmax) class of graphs, and this generalization is used to obtain a strongly polynomial time algorithm that decides membership of a rate-vector where the hosts are distributed within an infinite corridor with fixed cross-section.

This paper considers structural and algorithmic problems in stochastic loss networks. The very popular Erlang approximation can be shown to provide relatively poor performance estimates, especially for loss networks in the critically loaded regime. This paper proposes a novel algorithm for estimating the stationary loss probabilities in stochastic loss networks based on structural properties of the exact stationary distribution, which is shown to always converge, exponentially fast, to the asymptotically exact results. Using a variational characterization of the stationary distribution, an alternative proof is provided for an important result due to Kelly, which is simpler and may be of interest in its own right. This paper also determines structural properties of the inverse Erlang function characterizing the region of capacities that ensures offered traffic is served within a set of loss probabilities. Numerical experiments investigate various issues of both theoretical and practical interest.

In a wireless network, a sophisticated algorithm is required to schedule simultaneous wireless transmissions while satisfying interference constraint that two neighboring nodes can not transmit simultaneously. The scheduling algorithm need to be excellent in performance while being simple and distributed so as to be implementable. The result of Tassiulas and Ephremides (1992) imply that the algorithm, scheduling transmissions of nodes in the 'maximum weight independent set' (MWIS) of network graph, is throughput optimal. However, algorithmically the problem of finding MWIS is known to be NP-hard and hard to approximate. This raises the following questions: is it even possible to obtain throughput optimal simple, distributed scheduling algorithm? if yes, is it possible to minimize delay of such an algorithm? Motivated by these questions, we first provide a distributed throughput optimal algorithm for any network topology. However, this algorithm may induce exponentially large delay. To overcome this, we present an order optimal delay algorithm for any non-expanding network topology. Networks deployed in geographic area, like wireless networks, are likely to be of this type. Our algorithm is based on a novel distributed graph partitioning scheme which may be of interest in its own right. Our algorithm for non-expanding graph takes O (n) total message exchanges or O(l) message exchanges per node to compute a schedule.

We present a new local approximation algorithm for computing MAP and log-partition function for arbitrary exponential family distribution represented by a finite-valued pair-wise Markov random field (MRF), say G. Our algorithm is based on decomposing G into appropriately chosen small components; computing estimates locally in each of these components and then producing a good global solution. We prove that the algorithm can provide approximate solution within arbitrary accuracy when $G$ excludes some finite sized graph as its minor and G has bounded degree: all Planar graphs with bounded degree are examples of such graphs. The running time of the algorithm is $\Theta(n)$ (n is the number of nodes in G), with constant dependent on accuracy, degree of graph and size of the graph that is excluded as a minor (constant for Planar graphs). Our algorithm for minor-excluded graphs uses the decomposition scheme of Klein, Plotkin and Rao (1993). In general, our algorithm works with any decomposition scheme and provides quantifiable approximation guarantee that depends on the decomposition scheme.

We study the stability of the max-weight protocol for combined routingand scheduling in communication networks. Previous work has shownthat this protocol is stable for adversarial multicommodity trafficin subcritically loaded static networks and for single-commoditytraffic in critically loaded dynamic networks. We show: The max-weight protocol is stable for adversarial multicommodity traffic in adversarial dynamic networks whenever the network is subcriticallyloaded. The max-weight protocol is stable for fixed multicommodity trafficin fixed networks even if the network is critically loaded.

Distributed computation of average is essential for many tasks such as estimation, eigenvalue computation, scheduling in the context of wireless sensor and ad-hoc networks. The wireless communication imposes the gossip constraint: each node can communicate with at most one other node at a given time. Recent interest in emerging wireless sensor network has led to exciting developments in the context of gossip algorithms for averaging. Most of the known algorithms are iterative and based on certain reversible random walk on the network graph. Subsequently, the running time of algorithm is affected by the diffusive nature of reversible random walk. For example, they take Ω(n2) time to compute average on a simple path or ring graph of n nodes. In contrast, an optimal (simple) centralized algorithm takes [unk](n) time to compute average in a path. This raises the following questions: is it possible for a distributed algorithm to compute average in O(n) time for path graph? is it possible to improve over diffusive behavior of current algorithms in arbitrary graphs? In this paper, we answer the above questions in affirmative. To overcome the diffusive nature of algorithms, we utilize non-reversible random walks. Specifically, we design our algorithms by "projecting down" the "lifted" non-reversible random walks of Diaconis-Holmes-Neal (2000) and Chen-Lovasz-Pak (1999). The running time of our algorithm is square-root of the time taken by corresponding reversible random walk for a large class of graphs including path.

An analysis for the phase transition in a random NK landscape model is given. For the fixed ratio model, NK(n,k,z), Gao and Culberson [17] showed that a random instance generated by NK(n,2,z) with z > z0 = 27-7/√54 is asymptotically insoluble. Based on empirical results, they conjectured that the phase transition occurs around the value z = z0. We prove that an instance generated by NK(n,2,z) with z < z0 is soluble with positive probability by providing a variant of the unit clause algorithm. Using branching process arguments, we also reprove that an instance generated by NK(n,2,z) with z > z0 is asymptotically insoluble. The results show the phase transition around z = z0 for NK(n,2,z). In the course of the analysis, we introduce a generalized random 2-SAT formula, which is of self interest, and show its phase transition phenomenon.