A graph is a suitable data structure to represent the structural information of text.Recently, multi-hop question answering (MHQA) tasks, which require inter-paragraph/sentence linkages, have come to exploit such properties of a graph.Previous approaches to MHQA relied on leveraging the graph information along with the pre-trained language model (PLM) encoders.However, this trend exhibits the following drawbacks: (i) sample inefficiency while training in a low-resource setting; (ii) lack of reusability due to changes in the model structure or input.Our work proposes the Graph-Induced Transformer (GIT) that applies graphderived attention patterns directly into a PLM, without the need to employ external graph modules.GIT can leverage the useful inductive bias of graphs while retaining the unperturbed Transformer structure and parameters.Our experiments on HotpotQA successfully demonstrate both the sample efficient characteristic of GIT and its capacity to replace the graph modules while preserving model performance.

The semantic matching capabilities of neural information retrieval can ameliorate synonymy and polysemy problems of symbolic approaches.However, neural models' dense representations are more suitable for re-ranking, due to their inefficiency.Sparse representations, either in symbolic or latent form, are more efficient with an inverted index.Taking the merits of the sparse and dense representations, we propose an ultra-high dimensional (UHD) representation scheme equipped with directly controllable sparsity.UHD's large capacity and minimal noise and interference among the dimensions allow for binarized representations, which are highly efficient for storage and search.Also proposed is a bucketing method, where the embeddings from multiple layers of BERT are selected/merged to represent diverse linguistic aspects.We test our models with MS MARCO and TREC CAR, showing that our models outperforms other sparse models.

Tag recommendation relies on either a ranking function for top-k tags or an autoregressive generation method.However, the previous methods neglect one of two seemingly conflicting yet desirable characteristics of a tag set: orderlessness and inter-dependency.While the ranking approach fails to address the interdependency among tags when they are ranked, the autoregressive approach fails to take orderlessness into account because it is designed to utilize sequential relations among tokens.We propose a sequence-oblivious generation method for tag recommendation, in which the next tag to be generated is independent of the order of the generated tags and the order of the ground truth tags occurring in training data.Empirical results on two different domains, Instagram and Stack Overflow, show that our method is significantly superior to the previous approaches.

Numerical reasoning in machine reading comprehension (MRC) has shown drastic improvements over the past few years.While the previous models for numerical MRC are able to interpolate the learned numerical reasoning capabilities, it is not clear whether they can perform just as well on numbers unseen in the training dataset.Our work rigorously tests state-of-the-art models on DROP, a numerical MRC dataset, to see if they can handle passages that contain out-of-range numbers.One of the key findings is that the models fail to extrapolate to unseen numbers.Presenting numbers as digit-by-digit input to the model, we also propose the E-digit number form that alleviates the lack of extrapolation in models and reveals the need to treat numbers differently from regular words in the text.Our work provides a valuable insight into the numerical MRC models and the way to represent number forms in MRC.

Sentence encoders based on the transformer architecture have shown promising results on various natural language tasks.The main impetus lies in the pre-trained neural language models that capture long-range dependencies among words, owing to multi-head attention that is unique in the architecture.However, little is known for how linguistic properties are processed, represented, and utilized for downstream tasks among hundreds of attention heads inside the pre-trained transformerbased model.For the initial goal of examining the roles of attention heads in handling a set of linguistic features, we conducted a set of experiments with ten probing tasks and three downstream tasks on four pre-trained transformer families (GPT, GPT2, BERT, and ELECTRA).Meaningful insights are shown through the lens of heat map visualization and utilized to propose a relatively simple sentence representation method that takes advantage of most influential attention heads, resulting in additional performance improvements on the downstream tasks.

Advances in Question Answering (QA) research require additional datasets for new domains, languages, and types of questions, as well as for performance increases.Human creation of a QA dataset like SQuAD, however, is expensive.As an alternative, an unsupervised QA approach has been proposed so that QA training data can be generated automatically.However, the performance of unsupervised QA is much lower than that of supervised QA models.We identify two anomalies in the automatically generated questions and propose how they can be mitigated.We show our approach helps improve unsupervised QA significantly across a number of QA tasks. Context Generated Question..

How can we find patterns from an enormous graph with billions of vertices and edges? The subgraph enumeration, which is to find patterns from a graph, is an important task for graph data analysis with many applications, including analyzing the social network evolution, measuring the significance of motifs in biological networks, observing the dynamics of Internet, and so on. Especially, the triangle enumeration, a special case of the subgraph enumeration, where the pattern is a triangle, has many applications such as identifying suspicious users in social networks, detecting web spams, and finding communities. However, recent networks are so large that most of the previous algorithms fail to process them. Recently, several MapReduce algorithms have been proposed to address such large networks; however, they suffer from the massive shuffled data resulting in a very long processing time. In this article, we propose scalable methods for enumerating trillion subgraphs on distributed systems. We first propose PTE ( Pre-partitioned Triangle Enumeration ), a new distributed algorithm for enumerating triangles in enormous graphs by resolving the structural inefficiency of the previous MapReduce algorithms. PTE enumerates trillions of triangles in a billion scale graph by decreasing three factors: the amount of shuffled data, total work, and network read. We also propose PSE ( Pre-partitioned Subgraph Enumeration ), a generalized version of PTE for enumerating subgraphs that match an arbitrary query graph. Experimental results show that PTE provides 79 times faster performance than recent distributed algorithms on real-world graphs, and succeeds in enumerating more than 3 trillion triangles on the ClueWeb12 graph with 6.3 billion vertices and 72 billion edges. Furthermore, PSE successfully enumerates 265 trillion clique subgraphs with 4 vertices from a subdomain hyperlink network, showing 47 times faster performance than the state of the art distributed subgraph enumeration algorithm.

Inspired by the notion of a curriculum that allows human learners to acquire knowledge from easy to difficult materials, curriculum learning (CL) has been applied to many areas including Natural Language Processing (NLP). Most previous CL methods in NLP learn texts according to their lengths. We posit, however, that learning semantically similar texts is more effective than simply relying on superficial easiness such as text lengths. As such, we propose a new CL method that considers semantic dissimilarity as the complexity measure and a tree-structured curriculum as the organization method. The proposed CL method shows better performance than previous CL methods on a sentiment analysis task in an experiment.

A distributed representation has become a popular approach to capturing a word meaning. Besides its success and practical value, however, questions arise about the relationships between a true word meaning and its distributed representation. In this paper, we examine such a relationship via polymodal embedding approach inspired by the theory that humans tend to use diverse sources in developing a word meaning. The result suggests that the existing embeddings lack in capturing certain aspects of word meanings which can be significantly improved by the polymodal approach. Also, we show distinct characteristics of different types of words (e.g. concreteness) via computational studies. Finally, we show our proposed embedding method outperforms the baselines in the word similarity measure tasks and the hypernym prediction tasks.

How can we find all connected components in an enormous graph with billions of nodes and edges?Finding connected components is a fundamental operation for various graph computation tasks such as pattern recognition, reachability, graph compression, etc. Many algorithms have been proposed for decades, but most of them are not scalable enough to process recent web scale graphs. Recently, a MapReduce algorithm was proposed to handle such large graphs. However, the algorithm repeatedly reads and writes numerous intermediate data that cause network overload and prolong the running time. In this paper, we propose PACC (Partition-Aware Connected Components), a new distributed algorithm based on graph partitioning for load-balancing and edge-filtering. Experimental results show that PACC significantly reduces the intermediate data, and provides up to 10 times faster performance than the current state-of-the-art MapReduce algorithm on real world graphs.

How can we enumerate triangles from an enormous graph with billions of vertices and edges? Triangle enumeration is an important task for graph data analysis with many applications including identifying suspicious users in social networks, detecting web spams, finding communities, etc. However, recent networks are so large that most of the previous algorithms fail to process them. Recently, several MapReduce algorithms have been proposed to address such large networks; however, they suffer from the massive shuffled data resulting in a very long processing time. In this paper, we propose PTE (Pre-partitioned Triangle Enumeration), a new distributed algorithm for enumerating triangles in enormous graphs by resolving the structural inefficiency of the previous MapReduce algorithms. PTE enumerates trillions of triangles in a billion scale graph by decreasing three factors: the amount of shuffled data, total work, and network read.

People in different regions or times may have different views and therefore may talk about different sub-topics in a social media. Versatility of a topic in this research refers to the degree to which a topic discussed in a social media covers different points of view or sub-topics. We introduce this notion of versatility for individual topics embedded in Twitter data originated from different regions over time. Uniqueness of a region with respect to a topic is first computed based on how its term distribution differs from those in other regions. Uniqueness values associated with all the regions for a topic are then used to compute its versatility. Since versatility of a topic captures its characteristics across different regions, identifying versatile topics can help understanding regional interests and thus providing region-dependent services. In addition, it becomes possible to identify regions with minority sub-topics, which can be buried easily. By analyzing topic versatility over time, furthermore, we can analyze the behavior of a topic in terms of when it is diverged or converged across the regions.

Web forums are platforms for personal communications on sharing information with others. Such information is often expressed in the form of advice. In this paper, we address the problem of advice-revealing text unit (ATU) extraction from online forums due to its usefulness in travel domain. We represent advice as a two-tuple comprising an advice-revealing sentence and its context sentences. To extract the advice-revealing sentences, we propose to define the task as a sequence labeling problem, using three different types of features: syntactic, contextual, and semantic features. To extract the context sentences, we propose to use a 2 Dimensional CRF (2D-CRF) model, which gives the best performance compared to traditional machine learning models. Finally, we present a solution to the integrated problem of extracting both advice-revealing sentences and their respective context sentences at the same time using our proposed models, i.e., Multiple Linear CRF (ML-CRF) and 2 Dimensional CRF Plus (2D-CRF+). The experimental results show that ML-CRF performs better than any other models studied in this paper for extracting advice-revealing sentences and context sentences.

Problem solving knowledge is omnipresent and scattered on the Web. While extracting and gathering such knowledge has been a focus of attention, it is equally important to devise a way to organize such knowledge for both human and machine consumption with respect to task goals. As a way to provide an extensive knowledge structure for human task goals, with which human problem solving knowledge extracted from Web resources can be organized, we devised a method for automatically grouping and organizing the goal statements in a Web 2.0 site that contains over two millions how-to instruction articles covering almost all task domains. In the proposed method, task goals having semantically and task-categorically similar action types and object types are grouped together by analyzing predicate-argument association patterns across all the goal statements through bipartite EM-like modeling. The result obtained with the unsupervised machine learning algorithm was evaluated by means of a human-annotated data set in a sample domain.

Web forums often contain explicit key learnings gleaned from people's experiences since they are platforms for personal communications on sharing information with others. One of the key learnings contained inWeb forums is often expressed in the form of advice. As part of human experience mining from Web resources, we aim to provide a methodology to extract advice-revealing sentences from Web forums due to its usefulness, especially in travel domain. Instead of viewing the problem as a simple classification, we define it as a sequence labeling problem using various features. We identify three different types of features (i.e., syntactic features, context features, and sentence informativeness) and propose a new way of using Hidden Markov Model (HMM) for labeling sequential sentences, which in our experiment gave the best performance for our task. Moreover, the sentence informativeness score serves as an important feature for this task. It is worth noting that this work is the first attempt to extract advice-revealing sentences from Web forums.

Weblog, one of the fastest growing user generated contents, often contains key learnings gleaned from people's past experiences which are really worthy to be well presented to other people. One of the key learnings contained in weblogs is often vented in the form of advice. In this paper, we aim to provide a methodology to extract sentences that reveal advices on weblogs. We observed our data to discover the characteristics of advices contained in weblogs. Based on this observation, we define our task as a classification problem using various linguistic features. We show that our proposed method significantly outperforms the baseline. The presence or absence of imperative mood expression appears to be the most important feature in this task. It is also worth noting that the work presented in this paper is the first attempt on mining advices from English data.

As complex indoor-robot systems are developed and deployed into the real-world, the demand for human-robot interaction is increasing. Mixed-initiative human-robot interaction is a good method to coordinate actions of a human and a robot in a complementary fashion. In order to support such interactions, we employ scripts that are rich, flexible, and extensible for a robotpsilas interactions in a variety of situations. Scripts are amenable for expressing knowledge in an applicable form, especially describing a sequence of actions in organizing tasks. In this paper, we propose a script-based cognitive architecture for collaboration, which is based on three-level cognitive models. It incorporates dynamic Bayesian network (DBN) to automatically govern action sequences in the scripts and detect userpsilas intention or goal. Starting from an understanding of user initiatives, our intelligent task manager suggests the most relevant initiatives for an efficient collaboration. DBN has been evaluated in real indoor task scenarios for its efficacy in interaction reduction, error minimization, and task satisfaction.

Home-service robots are expected to perform a wide range of tasks commonly encountered in a household environment. For autonomous operations robots should be able to plan their actions to carry out these tasks in advance and they should at least have the ability to plan for additional tasks during their operation. Because of the variability and uncertainty in the environment, it is best to endow robots with a learning-based task planning capability that rests on human-robot interaction (HRI). We take a case-based reasoning (CBR) approach to home-service-robot learning and incorporate the cognitive HRI paradigm that includes four cognitive models (needs, task, interaction, and user model) for case adaptations to the given situation. Given a new command from user, a robot finds the closest task case from already existing tasks to start with a plan and modifies it (i.e. action sequences) to adapt to the given situation based on the cognitive models. In order to promote the reusability and flexibility of task cases used in our CBR approach, a robot task description language (RTDL) is designed to represent tasks using an atomic action taxonomy [1]. The proposed approach is applied to a "Bringmeacoke" scenario and implemented in our robot system called IDRO.

Mood classification for blogs is useful in helping user-to-agent interaction for a variety of applications involving the web, such as user modeling, recommendation systems, and user interface fields. It is challenging at the same time because of the diversity of the characteristics of bloggers, their experiences, and the way moods are expressed. As an attempt to handle the diversity, we combine multiple sources of evidence for a mood type. Support vector machine based mood classifier (SVMMC) is integrated with mood flow analyzer (MFA) that incorporates commonsense knowledge obtained from the general public (i.e. ConceptNet), the affective norms english words (ANEW) list, and mood transitions. In combining the two different approaches, we employ a statistically weighted voting scheme based on the support vector machine (SVM). For evaluation, we have built a mood corpus consisting of manually annotated blogs, which amounts to over 4000 blogs. Our proposed method outperforms SVMMC by 5.68% in precision. The improvement is attributed to the strategy of choosing more trustable classification results in an interleaving fashion between the SVMMC and our MFA.

We propose a semantic passage segmentation method for a Question Answering (QA) system. We define a semantic passage as sentences grouped by semantic coherence, determined by the topic assigned to individual sentences. Topic assignments are done by a sentence classifier based on a statistical classification technique, Maximum Entropy (ME), combined with multiple linguistic features. We ran experiments to evaluate the proposed method and its impact on application tasks, passage retrieval and template-filling for question answering. The experimental result shows that our semantic passage retrieval method using topic matching is more useful than fixed length passage retrieval. With the template-filling task used for information extraction in the QA system, the value of the sentence topic assignment method was reinforced.

Due to the historical and cultural reasons, English phases, especially the proper nouns and new words, frequently appear in Web pages written primarily in Asian languages such as Chinese and Korean. Although these English terms and their equivalences in the Asian languages refer to the same concept, they are erroneously treated as independent index units in traditional Information Retrieval (IR). This paper describes the degree to which the problem arises in IR and suggests a novel technique to solve it. Our method firstly extracts an English phrase from Asian language Web pages, and then unifies the extracted phrase and its equivalence(s) in the language as one index unit. Experimental results show that the high precision of our conceptual unification approach greatly improves the IR performance.

While naive Bayes is quite effective in various data mining tasks, it shows a disappointing result in the automatic text classification problem. Based on the observation of naive Bayes for the natural language text, we found a serious problem in the parameter estimation process, which causes poor results in text classification domain. In this paper, we propose two empirical heuristics: per-document text normalization and feature weighting method. While these are somewhat ad hoc methods, our proposed naive Bayes text classifier performs very well in the standard benchmark collections, competing with state-of-the-art text classifiers based on a highly complex learning method such as SVM.

Temporal information plays an important role in natural language processing (NLP) applications such as information extraction, discourse analysis, automatic summarization, and question-answering. In the topic detection and tracking (TDT) area, the temporal information often used is the publication date of a message, which is readily available but limited in its usefulness. We developed a relatively simple NLP method for extracting temporal information from Korean news articles, with the goal of improving performance of TDT tasks. To extract temporal information, we make use of finite state automata and a lexicon containing timerevealing vocabulary. Extracted information is converted into a canonicalized representation of a time point or a time duration. We first evaluated and investigated the extraction and canonicalization methods for their accuracy and the extent to which temporal information extracted as such can help TDT tasks. The experimental results show that time information extracted from the text does indeed help to significantly improve both precision and recall.

No abstract available.

Subject or prepositional content has been the focus of most classification research. Genre or style, on the other hand, is a different and important property of text, and automatic text genre classification is becoming important for classification and retrieval purposes as well as for some natural language processing research. In this paper, we present a method for automatic genre classification that is based on statistically selected features obtained from both subject-classified and genre classified training data. The experimental results show that the proposed method outperforms a direct application of a statistical learner often used for subject classification. We also observe that the deviation formula and discrimination formula using document frequency ratios also work as expected. We conjecture that this dual feature set approach can be generalized to improve the performance of subject classification as well.

As WWW grows at an increasing speed, a classifier targeted at hypertext has become in high demand. While document categorization is quite a mature, the issue of utilizing hypertext structure and hyperlinks has been relatively unexplored. In this paper, we propose a practical method for enhancing both the speed and the quality of hypertext categorization using hyperlinks. In comparison against a recently proposed technique that appears to be the only one of the kind, we obtained up to 18.5% of improvement in effectiveness while reducing the processing time dramatically. We attempt to explain through experiments what factors contribute to the improvement.

An easy way of translating queries in one language to the other for cross-language information retrieval (IR) is to use a simple bilingual dictionary. Because of the general-purpose nature of such dictionaries, however, this simple method yields a severe translation ambiguity problem. This paper describes the degree to which this problem arises in Korean-English cross-language IR and suggests a relatively simple yet effective method for disambiguation using mutual information statistics obtained only from the target document collection. In this method, mutual information is used not only to select the best candidate but also to assign a weight to query terms in the target language. Our experimental results based on the TREC-6 collection shows that this method can achieve up to 85% of the monolingual retrieval case and 96% of the manual disambiguation case.

For cross-language information retrieval (CLIR), often queries or documents are translated into the other language to create a mono-lingual information retrieval situation. Having surveyed recent research results on translation-based CLIR, we have convinced ourselves that an effective query translation method is an essential element for a practical CLIR system with a reasonable quality. After summarizing the arguments and methods for query translation and survey results for dictionary-based translation methods, this paper describes a relatively simple yet effective method of using mutual information to handle the ambiguity problem known to be the major factor for low performance compared to mono-lingual situation. Our experimental results based on the TREC-6 collection shows that this method can achieve up to 85% of the monolingual retrieval case and 96% of the manual disambiguation case.

Abstract In traditional information retrieval (IR) systems, a document as a whole is the target for a query. With increasing interests in structured documents like SGML documents, there is a growing need to build an LR system that can retrieve parts of documents, which satisfy not only content-based but also structure-based requirements. In this paper, we describe an inference-net-based approach to this problem. The model is capable of retrieving elements at any level in a principled way, satisfying certain containment constraints in a quety. Moreover, lvhile the model is general enough to reproduce the ranking strategy adopted by conventional document retrieval systems by making use of document and collection level statistics such as TF and IDF, its flexibility allows for incorporation of a variety of pragmatic and semantic information associated with document structures. We implemented the model and ran a series of experiments to show that, in addition to the added functionality, the use of the structural information embedded in SGML documents can improve the effectiveness of document retrieval, compared to the case where no such information is used. We also show that giving a pragmatic preference to a certain element tape of the SGML documents can enhance retrieval effectiveness. 1

effectively store and retrieve them based on their contents. Retrievingimages based on their contents is a difficult problem.Instead of using manually assigned content descriptors for retrieval, we take an approach where images are indexed and organized automatically so that the users can retrieve images by visually browsing the organized image space.For image indexing, the objects in an image are first analyzed for their shape features such as roundness, rectangularity, elipticit y, eccentricity, bending energy.These features are used to form a feature vector that represents the rmage.Subsequently, the feature vectors representing all the images in a image database are organized by a unsupervised neural net learning algorithm called Self-Organizing Map.Since this image feature map reflects the statistical patterns, i.e., the inter-similarities of the objects, the relationships among the images can be recognized by their location, neighborhood, and the way the map is organized.For the feasibdity and practicality of the approach, a prototype system has been developed and tested with some experiments.

Development of an information retrieval system that can be personalized to each user requires maintaining and continually updating an interest profile for each individual user. Since people tend to be poor at self-description, it is suggested that profile development and maintenance is an area in which machine learning and knowledge based techniques can be profitably employed. This paper presents a model for such an application of AI techniques.