Sahithya Ravi, Patrick Huber, Akshat Shrivastava, Vered Shwartz, Arash Einolghozati. Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2024.

Arash Einolghozati, Abhinav Arora, Lorena Sainz-Maza Lecanda, Anuj Kumar, Sonal Gupta. Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume. 2021.

Peyman Heidari, Arash Einolghozati, Shashank Jain, Soumya Batra, Lee Callender, Ankit Arun, Shawn Mei, Sonal Gupta, Pinar Donmez, Vikas Bhardwaj, Anuj Kumar, Michael White. Proceedings of the 22nd Annual Meeting of the Special Interest Group on Discourse and Dialogue. 2021.

The task of identifying out-of-domain (OOD) input examples directly at test-time has seen renewed interest recently due to increased real world deployment of models. In this work, we focus on OOD detection for natural language sentence inputs to task-based dialog systems. Our findings are three-fold:First, we curate and release ROSTD (Real Out-of-Domain Sentences From Task-oriented Dialog) - a dataset of 4K OOD examples for the publicly available dataset from (Schuster et al. 2019). In contrast to existing settings which synthesize OOD examples by holding out a subset of classes, our examples were authored by annotators with apriori instructions to be out-of-domain with respect to the sentences in an existing dataset.Second, we explore likelihood ratio based approaches as an alternative to currently prevalent paradigms. Specifically, we reformulate and apply these approaches to natural language inputs. We find that they match or outperform the latter on all datasets, with larger improvements on non-artificial OOD benchmarks such as our dataset. Our ablations validate that specifically using likelihood ratios rather than plain likelihood is necessary to discriminate well between OOD and in-domain data.Third, we propose learning a generative classifier and computing a marginal likelihood (ratio) for OOD detection. This allows us to use a principled likelihood while at the same time exploiting training-time labels. We find that this approach outperforms both simple likelihood (ratio) based and other prior approaches. We are hitherto the first to investigate the use of generative classifiers for OOD detection at test-time.

We introduce a new task of rephrasing for a more natural virtual assistant.Currently, virtual assistants work in the paradigm of intentslot tagging and the slot values are directly passed as-is to the execution engine.However, this setup fails in some scenarios such as messaging when the query given by the user needs to be changed before repeating it or sending it to another user.For example, for queries like 'ask my wife if she can pick up the kids' or 'remind me to take my pills', we need to rephrase the content to 'can you pick up the kids' and 'take your pills'.In this paper, we study the problem of rephrasing with messaging as a use case and release a dataset of 3000 pairs of original query and rephrased query.We show that BART, a pre-trained transformers-based masked language model with auto-regressive decoding, is a strong baseline for the task, and show improvements by adding a copy-pointer and copy loss to it.We analyze different tradeoffs of BART-based and LSTM-based seq2seq models, and propose a distilled LSTM-based seq2seq as the best practical model.

The web contains countless semi-structured websites, which can be a rich source of information for populating knowledge bases. Existing methods for extracting relations from the DOM trees of semi-structured webpages can achieve high precision and recall only when manual annotations for each website are available. Although there have been efforts to learn extractors from automatically generated labels, these methods are not sufficiently robust to succeed in settings with complex schemas and information-rich websites. In this paper we present a new method for automatic extraction from semi-structured websites based on distant supervision. We automatically generate training labels by aligning an existing knowledge base with a website and leveraging the unique structural characteristics of semi-structured websites. We then train a classifier based on the potentially noisy and incomplete labels to predict new relation instances. Our method can compete with annotation-based techniques in the literature in terms of extraction quality. A large-scale experiment on over 400,000 pages from dozens of multi-lingual long-tail websites harvested 1.25 million facts at a precision of 90%.

In this paper, we propose using stochastic framework for computations by biological cells. The key observation is that the input molecules activate receptors of a biological cell independently with probability p that is dependent on the molecule's concentration. Hence, the (active/inactive) states of the receptors can be viewed as a stochastic number representing the input concentration or probability p. We construct the addition operation via a cell having two different types of receptors. We also develop the multiplication by using a receptor that is active (with some probability) when both types of input molecules present. We analyze the computing accuracy of a cell w.r.t. parameters such as number of receptors and the input sensitivity of the cell.

Despite recent advances in molecular communication among bio agents, the design of reliable communication schemes remains an open problem. One of the requirements is to develop suitable coding schemes, which meet the molecular communication specific constraints in terms of reliability and complexity, and take into account the communication channel properties. In this paper, we consider diffusion-based molecular communication in which the information is encoded into the concentration (e.g., on/off keying). Such a communication system is modeled as operating over a completely asymmetric channel where one of the bits can be transmitted without any error while the other can undergo a random error by the channel. Because of the limitations of bio-agents, we focus on error-detection schemes, which require far less complexity at the receiver relative to error-correction codes. To obtain an optimal detection scheme, we model the detection problem via an erasure channel and propose algorithms to obtain the optimal codewords efficiently for two different optimality measures. Then, we consider an error-free subfamily of such codes, namely constant weight codes, and propose an implementation specific to the molecular communication. We analyze the rate of the constant-weight coding scheme, compare it to the theoretical limits and specify the optimal weights and lengths of such codes.

Despite the recent research activities in molecular communication among bio agents, the design of reliable schemes remains an open problem. One of the challenges is to develop suitable coding schemes which meet the molecular communication specific constraints in terms of reliability and complexity. In this paper, we consider diffusion-based molecular communication in which the information is encoded into the concentration (e.g., on/off keying). Such a communication system operates over a completely asymmetric channel where one of the bits can be transmitted without any error while the other can undergo a random error by the channel. Because of the limitations of bio agents, we focus on error-detecting schemes which require far less complexity at the receiver relative to error-correction codes. We model the detection process at the receiver via an erasure channel and propose an algorithm that obtains the optimal codewords efficiently. Then, we consider an error-free sub-family of such codes, namely constant weight codes, and propose an implementation specific to the molecular communication. We analyze the rate of the constant-weight coding scheme and specify the optimal weights and lengths of such codes. We also show that this coding scheme, by design, would enable the nodes to synchronize their communications.

Molecular communication between biological entities is a new paradigm in which biological nodes sense the environment, communicate and cooperate with each other. Ligand receptors are among the most common mechanisms used by biological entities such as bacteria to sense the molecular signals in their surroundings. In such a mechanism, molecules (i.e., ligands) bind to certain proteins (i.e., receptors) and activate a signaling cascade inside the cell. In this paper, we study the distortion in sensing and estimation of the concentration of molecular signals by ligand receptors in biological agents. The sensing distortion is caused by both the randomness in the ligand reception and the quantization of the final receiver output. The random measurement of the signal by the binding activity differentiates this case from classical quantization problems. We propose an optimal random quantization technique that minimizes the overall distortion described above. The performance of this optimal technique is compared with a uniform quantizer design and the regions where the optimal quantizer can offer a considerable advantage are identified. Furthermore, we analyze the effect of the number of the output levels (i.e., the output rate) on the overall distortion compared with the theoretical limit given by Shannon. Following this, the best practical number of levels beyond which no significant improvement can be made is presented.

Molecular communication allows bio nodes to communicate and cooperate in an aqueous environment. We recently proposed an m-ary modulation scheme in which the information is encoded into the concentration of molecules emitted by the bio nodes. The performance of such scheme, among other factors, is limited by the maximum concentration of molecules that can be induced by the transmitter at the receiver. This paper investigates relaying to improve the reliability of such molecular communication. We consider the case that nodes consist of a population of biological agents and study the scenario in which the relay node decodes the incoming information symbol and forwards it to the destination using the same or a different type of molecules as the transmitter. We show how the use of relaying in molecular communication can increase the effective range of molecular concentration induced at the receiver and also can help with achieving diversity at the receiver. We use a generalized form of Maximum Ratio Combining (MRC) and show as to how the probability of error is improved using the optimal relaying. We also compare this scenario with the case that the relay node uses the same type of the molecule.

This paper is eligible for the student paper award. Molecular communication between biological entities is a new paradigm in communications. Recently, we studied molecular communication between two nodes formed from synthetic bacteria. Due to high randomness in behavior of bacteria, we used a population of them in each node. The reliability of such communication systems depends on both the maximum concentration of molecules that a transmitter node is able to produce at the receiver node as well as the number of bacteria in each nodes. This maximum concentration of molecules falls with distance which makes the communication to the far nodes nearly impossible. In order to alleviate this problem, in this paper, we propose to use a molecular relaying node. The relay node can resend the message either by the different or the same type of molecules as the original signal from the transmitter. We study two scenarios of relaying. In the first scenario, the relay node simply senses the received concentration and forwards it to the receiver. We show that this sense and forward scenario, depending on the type of molecules used for relaying, results in either increasing the range of concentration of molecules at the receiver or increasing the effective number of bacteria in the receiver node. For both cases of sense and forward relaying, we obtain the resulting improvement in channel capacity. We conclude that multi-type molecular relaying outperforms the single-type relaying. In the second scenario, we study the decode and forward relaying for the M-ary signaling scheme. We show that this relaying strategy increases the reliability of M-ary communication significantly.

In this paper, we develop a Belief Propagation (BP) algorithm for similarity computation to improve the recommendation accuracy of the neighborhood method, which is one of the most popular Collaborative Filtering (CF) recommendation algorithms. We formulate a probabilistic inference problem as to compute the marginal posterior distributions of similarity variables from their joint posterior distribution given the observed ratings. However, direct computation is prohibitive in large-scale recommender systems. Therefore, we introduce an appropriate chosen factor graph to express the factorization of the joint distribution function, and utilize the BP algorithm that operates in the factor graph to exploit the factorization for efficient inference. In addition, since the high degree at the factor node incurs an exponential increase in computational complexity, we also propose a complexity-reduction technique. The overall complexity of the proposed BP algorithm on a factor graph is linear in the number of variables, which ensures scalability. Finally, through experiments on the MovieLens dataset, we show the superior prediction accuracy of the proposed BP-based similarity computation algorithm for recommendation.

The design of biologically-inspired wireless communication systems using bacteria as the basic element of the system is initially motivated by a phenomenon called Quorum Sensing. Due to high randomness in the individual behavior of a bacterium, reliable communication between two bacteria is almost impossible. Therefore, we have recently proposed that a population of bacteria in a cluster is considered as a bio node in the network capable of molecular transmission and reception. This proposition enables us to form a reliable bio node out of many unreliable bacteria. In this paper, we study the communication between two nodes in such a network where information is encoded in the concentration of molecules by the transmitter. The molecules produced by the bacteria in the transmitter node propagate through the diffusion channel. Then, the concentration of molecules is sensed by the bacteria population in the receiver node which would decode the information and output light or fluorescent as a result. The uncertainty in the communication is caused by all three components of communication, i.e., transmission, propagation and reception. We study the theoretical limits of the information transfer rate in the presence of such uncertainties. Finally, we consider M-ary signaling schemes and study their achievable rates and corresponding error probabilities.

In this paper we introduce the first application of the Belief Propagation (BP) algorithm in the design of recommender systems. We formulate the recommendation problem as an inference problem and aim to compute the marginal probability distributions of the variables which represent the ratings to be predicted. However, computing these marginal probability functions is computationally prohibitive for large-scale systems. Therefore, we utilize the BP algorithm to efficiently compute these functions. Recommendations for each active user are then iteratively computed by probabilistic message passing. As opposed to the previous recommender algorithms, BPRS does not require solving the recommendation problem for all the users if it wishes to update the recommendations for only a single active. Further, BPRS computes the recommendations for each user with linear complexity and without requiring a training period. Via computer simulations (using the 100K MovieLens dataset), we verify that BPRS iteratively reduces the error in the predicted ratings of the users until it converges. Finally, we confirm that BPRS is comparable to the state of art methods such as Correlation-based neighborhood model (CorNgbr) and Singular Value Decomposition (SVD) in terms of rating and precision accuracy. Therefore, we believe that the BP-based recommendation algorithm is a new promising approach which offers a significant advantage on scalability while providing competitive accuracy for the recommender systems.

The design of biological networks using bacteria as the basic elements of the network is initially motivated by a phenomenon called quorum sensing. Through quorum sensing, each bacterium performs sensing the medium and communicating it to others via molecular communication. As a result, bacteria can orchestrate and act collectively and perform tasks impossible otherwise. In this paper, we consider a population of bacteria as a single node in a network. In our version of biological communication networks, such a node would communicate with one another via molecular signals. As a first step toward such networks, this paper focuses on the study of the transfer of information to the population (i.e., the node) by stimulating it with a concentration of special type of a molecules signal. These molecules trigger a chain of processes inside each bacteria that results in a final output in the form of light or fluorescence. Each stage in the process adds noise to the signal carried to the next stage. Our objective is to measure (compute) the maximum amount of information that we can transfer to the node. This can be viewed as the collective sensing capacity of the node. The molecular concentration, which carries the information, is the input to the node, which should be estimated by observing the produced light as the output of the node (i.e., the entire population of bacteria forming the node. The molecules are trapped in the bacteria receptors forming complexes inside the bacteria which affect the genes responsible for producing the light. We focus on the noise caused by the random process of trapping molecules at the receptors as well as the variation of outputs of different bacteria in the node. The optimal input distribution to maximize the mutual information between the output of the node, e.g., light, and the applied molecule concentration is derived. Further, the capacity variation with the number of bacteria in the node and the number of receptors per bacteria is obtained. Finally, we investigated the collective sensing capability of the node when a specific form of molecular signaling concentration (which resembles M-ary modulation) is used. The achievable sensing capacity and the corresponding error probabilities were obtained for such practical signaling techniques.

Molecular communication is an expanding body of research. Recent advances in biology have encouraged using genetically engineered bacteria as the main component in the molecular communication. This has stimulated a new line of research that attempts to study molecular communication among bacteria from an information-theoretic point of view. Due to high randomness in the individual behavior of the bacterium, reliable communication between two bacteria is almost impossible. Therefore, we recently proposed that a population of bacteria in a cluster is considered as a node capable of molecular transmission and reception. This proposition enables us to form a reliable node out of many unreliable bacteria. The bacteria inside a node sense the environment and respond accordingly. In this paper, we study the communication between two nodes, one acting as the transmitter and the other as the receiver. We consider the case in which the information is encoded in the concentration of molecules by the transmitter. The molecules produced by the bacteria in the transmitter node propagate in the environment via the diffusion process. Then, their concentration sensed by the bacteria in the receiver node would decode the information. The randomness in the communication is caused by both the error in the molecular production at the transmitter and the reception of molecules at the receiver. We study the theoretical limits of the information transfer rate in such a setup versus the number of bacteria per node. Finally, we consider M-ary modulation schemes and study the achievable rates and their error probabilities.

In diffusion-based molecular communications, messages can be conveyed via the variation in the concentration of molecules in the medium. In this paper, we intend to analyze the achievable capacity in transmission of information from one node to another in a diffusion channel. We observe that because of the molecular diffusion in the medium, the channel possesses memory. We then model the memory of the channel by a two-step Markov chain and obtain the equations describing the capacity of the diffusion channel. By performing a numerical analysis, we obtain the maximum achievable rate for different levels of the transmitter power, i.e., the molecule production rate.

A diffusion-based molecular communication system has two major components: the diffusion in the medium, and the ligand-reception. Information bits, encoded in the time variations of the concentration of molecules, are conveyed to the receiver front through the molecular diffusion in the medium. The receiver, in turn, measures the concentration of the molecules in its vicinity in order to retrieve the information. This is done via ligand-reception process. In this paper, we develop models to study the constraints imposed by the concentration sensing at the receiver side and derive the maximum rate by which a ligand-receiver can receive information. Therefore, the overall capacity of the diffusion channel with the ligand receptors can be obtained by combining the results presented in this paper with our previous work on the achievable information rate of molecular communication over the diffusion channel.