OpenRaiser/Intern-Atlas huggingface dataset:
Logographic Subword Model for Neural Machine Translation
Venue: arXiv cs.CL 2018
Year: 2018

A novel logographic subword model is proposed to reinterpret logograms as abstract subwords for neural machine translation. Our approach drastically reduces the size of an artificial neural network, while maintaining comparable BLEU scores as those attained with the baseline RNN and CNN seq2seq models. The smaller model size also leads to shorter training and inference time. Experiments demonstrate that in the tasks of English-Chinese/Chinese-English translation, the reduction of those aspects can be from $11\%$ to as high as $77\%$. Compared to previous subword models, abstract subwords can be applied to various logographic languages. Considering most of the logographic languages are ancient and very low resource languages, these advantages are very desirable for archaeological computational linguistic applications such as a resource-limited offline hand-held Demotic-English translator.
Mobility-Aware Resource Allocation in VLC Networks Using T-Step Look-Ahead Policy
Venue: arXiv cs.NI 2018
Year: 2018

Visible light communication (VLC) uses huge license-free spectral bandwidth of visible light for high-speed wireless communication. Since each VLC access point covers a small area, handovers of mobile users are inevitable. In order to deal with these handovers, developing fast and effective resource allocation algorithms is a challenge. This paper introduces the problem of mobility-aware optimization of resources in VLC networks using the T-step look-ahead policy and employing the notion of handover efficiency. It is shown that the handover efficiency can correlate the overall performance of the network with future actions based on the mobility of users. Due to the stationary nature of indoor optical wireless channels, future channel state information (CSI) can be predicted by anticipating the future locations of users. A resource allocation algorithm is thus proposed, which uses CSI to dynamically allocate network resources to users. To solve this mathematically intractable problem, a novel relaxation method is proposed, which proves to be a useful tool to develop efficient algorithms for network optimization problems with a proportional fairness utility function. The resulting algorithm is extremely faster than the previous method and awareness of mobility enhances the overall performance of the network in terms of rate and fairness utility function.
Pushing the Limits of Encrypted Databases with Secure Hardware
Venue: arXiv cs.DB 2018
Year: 2018

Encrypted databases have been studied for more than 10 years and are quickly emerging as a critical technology for the cloud. The current state of the art is to use property-preserving encrypting techniques (e.g., deterministic encryption) to protect the confidentiality of the data and support query processing at the same time. Unfortunately, these techniques have many limitations. Recently, trusted computing platforms (e.g., Intel SGX) have emerged as an alternative to implement encrypted databases. This paper demonstrates some vulnerabilities and the limitations of this technology, but it also shows how to make best use of it in order to improve on confidentiality, functionality, and performance.
Neural Generation of Diverse Questions using Answer Focus, Contextual and Linguistic Features
Venue: arXiv cs.CL 2018
Year: 2018

Question Generation is the task of automatically creating questions from textual input. In this work we present a new Attentional Encoder--Decoder Recurrent Neural Network model for automatic question generation. Our model incorporates linguistic features and an additional sentence embedding to capture meaning at both sentence and word levels. The linguistic features are designed to capture information related to named entity recognition, word case, and entity coreference resolution. In addition our model uses a copying mechanism and a special answer signal that enables generation of numerous diverse questions on a given sentence. Our model achieves state of the art results of 19.98 Bleu_4 on a benchmark Question Generation dataset, outperforming all previously published results by a significant margin. A human evaluation also shows that these added features improve the quality of the generated questions.
A Transfer-Learnable Natural Language Interface for Databases
Venue: arXiv cs.AI 2018
Year: 2018

Relational database management systems (RDBMSs) are powerful because they are able to optimize and answer queries against any relational database. A natural language interface (NLI) for a database, on the other hand, is tailored to support that specific database. In this work, we introduce a general purpose transfer-learnable NLI with the goal of learning one model that can be used as NLI for any relational database. We adopt the data management principle of separating data and its schema, but with the additional support for the idiosyncrasy and complexity of natural languages. Specifically, we introduce an automatic annotation mechanism that separates the schema and the data, where the schema also covers knowledge about natural language. Furthermore, we propose a customized sequence model that translates annotated natural language queries to SQL statements. We show in experiments that our approach outperforms previous NLI methods on the WikiSQL dataset and the model we learned can be applied to another benchmark dataset OVERNIGHT without retraining.
Multiple Access in Cellular V2X: Performance Analysis in Highly Congested Vehicular Networks
Venue: arXiv cs.NI 2018
Year: 2018

Vehicle-to-everything (V2X) communication enables vehicles, roadside vulnerable users, and infrastructure facilities to communicate in an ad-hoc fashion. Cellular V2X (C-V2X), which was introduced in the 3rd generation partnership project (3GPP) release 14 standard, has recently received significant attention due to its perceived ability to address the scalability and reliability requirements of vehicular safety applications. In this paper, we provide a comprehensive study of the resource allocation of the C-V2X multiple access mechanism for high-density vehicular networks, as it can strongly impact the key performance indicators such as latency and packet delivery rate. Phenomena that can affect the communication performance are investigated and a detailed analysis of the cases that can cause possible performance degradation or system limitations, is provided. The results indicate that a unified system configuration may be necessary for all vehicles, as it is mandated for IEEE 802.11p, in order to obtain the optimum performance. In the end, we show the inter-dependence of different parameters on the resource allocation procedure with the aid of our high fidelity simulator.
Textual Analogy Parsing: What's Shared and What's Compared among Analogous Facts
Venue: arXiv cs.CL 2018
Year: 2018

To understand a sentence like "whereas only 10% of White Americans live at or below the poverty line, 28% of African Americans do" it is important not only to identify individual facts, e.g., poverty rates of distinct demographic groups, but also the higher-order relations between them, e.g., the disparity between them. In this paper, we propose the task of Textual Analogy Parsing (TAP) to model this higher-order meaning. The output of TAP is a frame-style meaning representation which explicitly specifies what is shared (e.g., poverty rates) and what is compared (e.g., White Americans vs. African Americans, 10% vs. 28%) between its component facts. Such a meaning representation can enable new applications that rely on discourse understanding such as automated chart generation from quantitative text. We present a new dataset for TAP, baselines, and a model that successfully uses an ILP to enforce the structural constraints of the problem.
BLAG: Bandit On Large Action Set Graph
Venue: arXiv cs.SI 2018
Year: 2018

Information diffusion in social networks facilitates rapid and large-scale propagation of content. However, spontaneous diffusion behavior could also lead to the cascading of sensitive information, which is neglected in prior arts. In this paper, we present the first look into adaptive diffusion of sensitive information, which we aim to prevent from widely spreading without incurring much information loss. We undertake the investigation in networks with partially known topology, meaning that some users' ability of forwarding information is unknown. Formulating the problem into a bandit model, we propose BLAG (Bandit on Large Action set Graph), which adaptively diffuses sensitive information towards users with weak forwarding ability that is learnt from tentative transmissions and corresponding feedbacks. BLAG enjoys a low complexity of O(n), and is provably more efficient in the sense of half regret bound compared with prior learning method. Experiments on synthetic and three real datasets further demonstrate the superiority of BLAG in terms of adaptive diffusion of sensitive information over several baselines, with at least 40 percent less information loss, at least 10 times of learning efficiency given limited learning rounds and significantly postponed cascading of sensitive information.
Learning to Solve NP-Complete Problems - A Graph Neural Network for Decision TSP
Venue: arXiv cs.LG 2018
Year: 2018

Graph Neural Networks (GNN) are a promising technique for bridging differential programming and combinatorial domains. GNNs employ trainable modules which can be assembled in different configurations that reflect the relational structure of each problem instance. In this paper, we show that GNNs can learn to solve, with very little supervision, the decision variant of the Traveling Salesperson Problem (TSP), a highly relevant $\mathcal{NP}$-Complete problem. Our model is trained to function as an effective message-passing algorithm in which edges (embedded with their weights) communicate with vertices for a number of iterations after which the model is asked to decide whether a route with cost $<C$ exists. We show that such a network can be trained with sets of dual examples: given the optimal tour cost $C^{*}$, we produce one decision instance with target cost $x\%$ smaller and one with target cost $x\%$ larger than $C^{*}$. We were able to obtain $80\%$ accuracy training with $-2\%,+2\%$ deviations, and the same trained model can generalize for more relaxed deviations with increasing performance. We also show that the model is capable of generalizing for larger problem sizes. Finally, we provide a method for predicting the optimal route cost within $2\%$ deviation from the ground truth. In summary, our work shows that Graph Neural Networks are powerful enough to solve $\mathcal{NP}$-Complete problems which combine symbolic and numeric data.
On the Calibration of Nested Dichotomies for Large Multiclass Tasks
Venue: arXiv cs.LG 2018
Year: 2018

Nested dichotomies are used as a method of transforming a multiclass classification problem into a series of binary problems. A tree structure is induced that recursively splits the set of classes into subsets, and a binary classification model learns to discriminate between the two subsets of classes at each node. In this paper, we demonstrate that these nested dichotomies typically exhibit poor probability calibration, even when the base binary models are well calibrated. We also show that this problem is exacerbated when the binary models are poorly calibrated. We discuss the effectiveness of different calibration strategies and show that accuracy and log-loss can be significantly improved by calibrating both the internal base models and the full nested dichotomy structure, especially when the number of classes is high.
A Game Theoretic Macroscopic Model of Bypassing at Traffic Diverges with Applications to Mixed Autonomy Networks
Venue: arXiv cs.GT 2018
Year: 2018

Vehicle bypassing is known to negatively affect delays at traffic diverges. However, due to the complexities of this phenomenon, accurate and yet simple models of such lane change maneuvers are hard to develop. In this work, we present a macroscopic model for predicting the number of vehicles that bypass at a traffic diverge. We take into account the selfishness of vehicles in selecting their lanes; every vehicle selects lanes such that its own cost is minimized. We discuss how we model the costs experienced by the vehicles. Then, taking into account the selfish behavior of the vehicles, we model the lane choice of vehicles at a traffic diverge as a Wardrop equilibrium. We state and prove the properties of Wardrop equilibrium in our model. We show that there always exists an equilibrium for our model. Moreover, unlike most nonlinear asymmetrical routing games, we prove that the equilibrium is unique under mild assumptions. We discuss how our model can be easily calibrated by running a simple optimization problem. Using our calibrated model, we validate it through simulation studies and demonstrate that our model successfully predicts the aggregate lane change maneuvers that are performed by vehicles for bypassing at a traffic diverge. We further discuss how our model can be employed to obtain the optimal lane choice behavior of the vehicles, where the social or total cost of vehicles is minimized. Finally, we demonstrate how our model can be utilized in scenarios where a central authority can dictate the lane choice and trajectory of certain vehicles so as to increase the overall vehicle mobility at a traffic diverge. Examples of such scenarios include the case when both human driven and autonomous vehicles coexist in the network. We show how certain decisions of the central authority can affect the total delays in such scenarios via an example.
Generating Distractors for Reading Comprehension Questions from Real Examinations
Venue: arXiv cs.CL 2018
Year: 2018

We investigate the task of distractor generation for multiple choice reading comprehension questions from examinations. In contrast to all previous works, we do not aim at preparing words or short phrases distractors, instead, we endeavor to generate longer and semantic-rich distractors which are closer to distractors in real reading comprehension from examinations. Taking a reading comprehension article, a pair of question and its correct option as input, our goal is to generate several distractors which are somehow related to the answer, consistent with the semantic context of the question and have some trace in the article. We propose a hierarchical encoder-decoder framework with static and dynamic attention mechanisms to tackle this task. Specifically, the dynamic attention can combine sentence-level and word-level attention varying at each recurrent time step to generate a more readable sequence. The static attention is to modulate the dynamic attention not to focus on question irrelevant sentences or sentences which contribute to the correct option. Our proposed framework outperforms several strong baselines on the first prepared distractor generation dataset of real reading comprehension questions. For human evaluation, compared with those distractors generated by baselines, our generated distractors are more functional to confuse the annotators.
Attentive Semantic Role Labeling with Boundary Indicator
Venue: arXiv cs.CL 2018
Year: 2018

The goal of semantic role labeling (SRL) is to discover the predicate-argument structure of a sentence, which plays a critical role in deep processing of natural language. This paper introduces simple yet effective auxiliary tags for dependency-based SRL to enhance a syntax-agnostic model with multi-hop self-attention. Our syntax-agnostic model achieves competitive performance with state-of-the-art models on the CoNLL-2009 benchmarks both for English and Chinese.
Multi-label Classification of User Reactions in Online News
Venue: arXiv cs.LG 2018
Year: 2018

The increase in the number of Internet users and the strong interaction brought by Web 2.0 made the Opinion Mining an important task in the area of natural language processing. Although several methods are capable of performing this task, few use multi-label classification, where there is a group of true labels for each example. This type of classification is useful for situations where the opinions are analyzed from the perspective of the reader, this happens because each person can have different interpretations and opinions on the same subject. This paper discuss the efficiency of problem transformation methods combined with different classification algorithms for the task of multi-label classification of reactions in news texts. To do that, extensive tests were carried out on two news corpora written in Brazilian Portuguese annotated with reactions. A new corpus called BFRC-PT is presented. In the tests performed, the highest number of correct predictions was obtained with the Classifier Chains method combined with the Random Forest algorithm. When considering the class distribution, the best results were obtained with the Binary Relevance method combined with the LSTM and Random Forest algorithms.
A natural language processing and geospatial clustering framework for harvesting local place names from geotagged housing advertisements
Venue: arXiv cs.IR 2018
Year: 2018

Local place names are frequently used by residents living in a geographic region. Such place names may not be recorded in existing gazetteers, due to their vernacular nature, relative insignificance to a gazetteer covering a large area (e.g., the entire world), recent establishment (e.g., the name of a newly-opened shopping center), or other reasons. While not always recorded, local place names play important roles in many applications, from supporting public participation in urban planning to locating victims in disaster response. In this paper, we propose a computational framework for harvesting local place names from geotagged housing advertisements. We make use of those advertisements posted on local-oriented websites, such as Craigslist, where local place names are often mentioned. The proposed framework consists of two stages: natural language processing (NLP) and geospatial clustering. The NLP stage examines the textual content of housing advertisements, and extracts place name candidates. The geospatial stage focuses on the coordinates associated with the extracted place name candidates, and performs multi-scale geospatial clustering to filter out the non-place names. We evaluate our framework by comparing its performance with those of six baselines. We also compare our result with four existing gazetteers to demonstrate the not-yet-recorded local place names discovered by our framework.
Context-Free Transductions with Neural Stacks
Venue: arXiv cs.NE 2018
Year: 2018

This paper analyzes the behavior of stack-augmented recurrent neural network (RNN) models. Due to the architectural similarity between stack RNNs and pushdown transducers, we train stack RNN models on a number of tasks, including string reversal, context-free language modelling, and cumulative XOR evaluation. Examining the behavior of our networks, we show that stack-augmented RNNs can discover intuitive stack-based strategies for solving our tasks. However, stack RNNs are more difficult to train than classical architectures such as LSTMs. Rather than employ stack-based strategies, more complex networks often find approximate solutions by using the stack as unstructured memory.
Resolution and the binary encoding of combinatorial principles
Venue: arXiv cs.CC 2018
Year: 2018

We investigate the size complexity of proofs in $Res(s)$ -- an extension of Resolution working on $s$-DNFs instead of clauses -- for families of contradictions given in the {\em unusual binary} encoding. A motivation of our work is size lower bounds of refutations in Resolution for families of contradictions in the usual unary encoding. Our main interest is the $k$-Clique Principle, whose Resolution complexity is still unknown. Our main result is a $n^{Ω(k)}$ lower bound for the size of refutations of the binary $k$-Clique Principle in $Res(\lfloor \frac{1}{2}\log \log n\rfloor)$. This improves the result of Lauria, Pudlák et al. [24] who proved the lower bound for Resolution, that is $Res(1)$. Our second lower bound proves that in $RES(s)$ for $s\leq \log^{\frac{1}{2-ε}}(n)$, the shortest proofs of the $BinPHP^m_n$, requires size $2^{n^{1-δ}}$, for any $δ>0$. Furthermore we prove that $BinPHP^m_n$ can be refuted in size $2^{Θ(n)}$ in treelike $Res(1)$, contrasting with the unary case, where $PHP^m_n$ requires treelike $RES(1)$ \ refutations of size $2^{Ω(n \log n)}$ [9,16]. Furthermore we study under what conditions the complexity of refutations in Resolution will not increase significantly (more than a polynomial factor) when shifting between the unary encoding and the binary encoding. We show that this is true, from unary to binary, for propositional encodings of principles expressible as a $Π_2$-formula and involving {\em total variable comparisons}. We then show that this is true, from binary to unary, when one considers the \emph{functional unary encoding}. Finally we prove that the binary encoding of the general Ordering principle $OP$ -- with no total ordering constraints -- is polynomially provable in Resolution.
iDriveSense: Dynamic Route Planning Involving Roads Quality Information
Venue: arXiv cs.CY 2018
Year: 2018

Owing to the expeditious growth in the information and communication technologies, smart cities have raised the expectations in terms of efficient functioning and management. One key aspect of residents' daily comfort is assured through affording reliable traffic management and route planning. Comprehensively, the majority of the present trip planning applications and service providers are enabling their trip planning recommendations relying on shortest paths and/or fastest routes. However, such suggestions may discount drivers' preferences with respect to safe and less disturbing trips. Road anomalies such as cracks, potholes, and manholes induce risky driving scenarios and can lead to vehicles damages and costly repairs. Accordingly, in this paper, we propose a crowdsensing based dynamic route planning system. Leveraging both the vehicle motion sensors and the inertial sensors within the smart devices, road surface types and anomalies have been detected and categorized. In addition, the monitored events are geo-referenced utilizing GPS receivers on both vehicles and smart devices. Consequently, road segments assessments are conducted using fuzzy system models based on aspects such as the number of anomalies and their severity levels in each road segment. Afterward, another fuzzy model is adopted to recommend the best trip routes based on the road segments quality in each potential route. Extensive road experiments are held to build and show the potential of the proposed system.
Personalizing Fairness-aware Re-ranking
Venue: arXiv cs.IR 2018
Year: 2018

Personalized recommendation brings about novel challenges in ensuring fairness, especially in scenarios in which users are not the only stakeholders involved in the recommender system. For example, the system may want to ensure that items from different providers have a fair chance of being recommended. To solve this problem, we propose a Fairness-Aware Re-ranking algorithm (FAR) to balance the ranking quality and provider-side fairness. We iteratively generate the ranking list by trading off between accuracy and the coverage of the providers. Although fair treatment of providers is desirable, users may differ in their receptivity to the addition of this type of diversity. Therefore, personalized user tolerance towards provider diversification is incorporated. Experiments are conducted on both synthetic and real-world data. The results show that our proposed re-ranking algorithm can significantly promote fairness with a slight sacrifice in accuracy and can do so while being attentive to individual user differences.