OpenRaiser/Intern-Atlas huggingface dataset:
Farsighted Collusion in Stable Marriage Problem
Venue: arXiv cs.GT 2019
Year: 2019

The Stable Marriage Problem, as proposed by Gale and Shapley, considers producing a bipartite matching between two equally sized sets of boys (proposers) and respectively girls (acceptors), each member having a total preference order over the other set, such that the outcome is stable. In this paper we consider the Game directly induced by this problem and analyze the case when proposers collude. We present a linear time method for determining the unique optimal collusion matching which is farsightedly stable, under the following assumptions: (i) the sole utility in the Game is the rank of the match in own preference list (in particular, proposers are indifferent as to how other proposers fare); (ii) proposers make proposals iff farsightedly such plays would strictly improve their own outcome (thus proposers cooperate by refraining from making proposals which can only harm others, but not strictly help them; also, they cannot make concessions to others which harm themselves). We argue that this optimal outcome is actually stronger than a Strong Nash Equilibrium - no alternative feasible coalition exists which can offer at least one member a strictly better outcome under these assumptions.We also show why some prior results pertaining to collusion of proposers do not always yield a realistic outcome. The results in this paper are an independent rediscovery of results by Jun Wako (2010), derived in a simpler fashion and phrased such that less jargon is employed.
An Immersive Virtual Reality Serious Game to Enhance Earthquake Behavioral Responses and Post-earthquake Evacuation Preparedness in Buildings
Venue: arXiv cs.CY 2019
Year: 2019

Enhancing the earthquake behavioral responses and post-earthquake evacuation preparedness of building occupants is beneficial to increasing their chances of survival and reducing casualties after the main shock of an earthquake. Traditionally, training approaches such as seminars, posters, videos or drills are applied to enhance preparedness. However, they are not highly engaging and have limited sensory capabilities to mimic life-threatening scenarios for the purpose of training potential participants. Immersive Virtual Reality (IVR) and Serious Games (SG) as innovative digital technologies can be used to create training tools to overcome these limitations. In this study, we propose an IVR SG-based training system to improve earthquake behavioral responses and post-earthquake evacuation preparedness. Auckland City Hospital was chosen as a case study to test our IVR SG training system. A set of learning outcomes based on best evacuation practice has been identified and embedded into several training scenarios of the IVR SG. Hospital staff (healthcare and administrative professionals) and visitors were recruited as participants to be exposed to these training scenarios. Participants' preparedness has been measured along two dimensions: 1) Knowledge about best evacuation practice; 2) Self-efficacy in dealing with earthquake emergencies. Assessment results showed that there was a significant knowledge and self-efficacy increase after the training. And participants acknowledged that it was easy and engaging to learn best evacuation practice knowledge through the IVR SG training system.
Capacity Games with Supply Function Competition
Venue: arXiv cs.GT 2019
Year: 2019

This paper studies a setting in which multiple suppliers compete for a buyer's procurement business. The buyer faces uncertain demand and there is a requirement to reserve capacity in advance of knowing the demand. Each supplier has costs that are two dimensional, with some costs incurred before demand is realized in order to reserve capacity and some costs incurred after demand is realized at the time of delivery. A distinctive feature of our model is that the marginal costs may not be constants, and this naturally leads us to a supply function competition framework in which each supplier offers a schedule of prices and quantities. We treat this problem as an example of a general class of capacity games and show that, when the optimal supply chain profit is submodular, in equilibrium the buyer makes a reservation choice that maximizes the overall supply chain profit, each supplier makes a profit equal to their marginal contribution to the supply chain, and the buyer takes the remaining profit. We further prove that this submodularity property holds under two commonly studied settings: (1) there are only two suppliers; and (2) in the case of more than two suppliers, the marginal two-dimension costs of each supplier are non-decreasing and constant, respectively.
Disentangling Dynamics and Returns: Value Function Decomposition with Future Prediction
Venue: arXiv cs.LG 2019
Year: 2019

Value functions are crucial for model-free Reinforcement Learning (RL) to obtain a policy implicitly or guide the policy updates. Value estimation heavily depends on the stochasticity of environmental dynamics and the quality of reward signals. In this paper, we propose a two-step understanding of value estimation from the perspective of future prediction, through decomposing the value function into a reward-independent future dynamics part and a policy-independent trajectory return part. We then derive a practical deep RL algorithm from the above decomposition, consisting of a convolutional trajectory representation model, a conditional variational dynamics model to predict the expected representation of future trajectory and a convex trajectory return model that maps a trajectory representation to its return. Our algorithm is evaluated in MuJoCo continuous control tasks and shows superior results under both common settings and delayed reward settings.
Performance of Network-Assisted Full-Duplex for Cell-Free Massive MIMO
Venue: arXiv cs.IT 2019
Year: 2019

Network assisted full-duplex (NAFD) is a spatial-division duplex technique for future wireless networks with cell-free massive multiple-input multiple-output (CF massive MIMO) network, where a large number of remote antenna units (RAUs), either using half-duplex or full-duplex, jointly support truly flexible duplex including time-division duplex, frequency-division duplex and full duplex on demand of uplink and downlink traffic by using network MIMO methods. With NAFD, bi-directional data rates of the wireless network could be increased and end-to-end delay could be reduced. In this paper, the spectral efficiency of NAFD communications in CF massive MIMO network with imperfect channel state information (CSI) is investigated under spatial correlated channels. Based on large dimensional random matrix theory, the deterministic equivalents for the uplink sum-rate with minimum-mean-square-error (MMSE) receiver as well as the downlink sum-rate with zero-forcing (ZF) and regularized zero-forcing (RZF) beamforming are derived. Numerical results show that under various environmental settings, the deterministic equivalents are accurate in both a large-scale system and system with a finite number of antennas. It is also shown that with the downlink-to-uplink interference cancellation, the uplink spectral efficiency of CF massive MIMO with NAFD could be improved. The spectral efficiencies of NAFD with different duplex configurations such as in-band full-duplex, and half-duplex are compared. With the same total numbers of transmit and receive antennas, NAFD with half-duplex RAUs offers a higher spectral efficiency. To alleviate the uplink-to-downlink interference, a novel genetic algorithm based user scheduling strategy (GAS) is proposed. Simulation results show that the achievable downlink sum-rate by using the GAS is greatly improved compared to that by using the random user scheduling.
Audio2Face: Generating Speech/Face Animation from Single Audio with Attention-Based Bidirectional LSTM Networks
Venue: arXiv cs.LG 2019
Year: 2019

We propose an end to end deep learning approach for generating real-time facial animation from just audio. Specifically, our deep architecture employs deep bidirectional long short-term memory network and attention mechanism to discover the latent representations of time-varying contextual information within the speech and recognize the significance of different information contributed to certain face status. Therefore, our model is able to drive different levels of facial movements at inference and automatically keep up with the corresponding pitch and latent speaking style in the input audio, with no assumption or further human intervention. Evaluation results show that our method could not only generate accurate lip movements from audio, but also successfully regress the speaker's time-varying facial movements.
Learning Occlusion-Aware View Synthesis for Light Fields
Venue: arXiv cs.CV 2019
Year: 2019

In this work, we present a novel learning-based approach to synthesize new views of a light field image. In particular, given the four corner views of a light field, the presented method estimates any in-between view. We use three sequential convolutional neural networks for feature extraction, scene geometry estimation and view selection. Compared to state-of-the-art approaches, in order to handle occlusions we propose to estimate a different disparity map per view. Jointly with the view selection network, this strategy shows to be the most important to have proper reconstructions near object boundaries. Ablation studies and comparison against the state of the art on Lytro light fields show the superior performance of the proposed method. Furthermore, the method is adapted and tested on light fields with wide baselines acquired with a camera array and, in spite of having to deal with large occluded areas, the proposed approach yields very promising results.
Counting Causal Paths in Big Times Series Data on Networks
Venue: arXiv cs.SI 2019
Year: 2019

Graph or network representations are an important foundation for data mining and machine learning tasks in relational data. Many tools of network analysis, like centrality measures, information ranking, or cluster detection rest on the assumption that links capture direct influence, and that paths represent possible indirect influence. This assumption is invalidated in time-stamped network data capturing, e.g., dynamic social networks, biological sequences or financial transactions. In such data, for two time-stamped links (A,B) and (B,C) the chronological ordering and timing determines whether a causal path from node A via B to C exists. A number of works has shown that for that reason network analysis cannot be directly applied to time-stamped network data. Existing methods to address this issue require statistics on causal paths, which is computationally challenging for big data sets. Addressing this problem, we develop an efficient algorithm to count causal paths in time-stamped network data. Applying it to empirical data, we show that our method is more efficient than a baseline method implemented in an OpenSource data analytics package. Our method works efficiently for different values of the maximum time difference between consecutive links of a causal path and supports streaming scenarios. With it, we are closing a gap that hinders an efficient analysis of big time series data on complex networks.
Social Cards Probably Provide For Better Understanding Of Web Archive Collections
Venue: arXiv cs.DL 2019
Year: 2019

Used by a variety of researchers, web archive collections have become invaluable sources of evidence. If a researcher is presented with a web archive collection that they did not create, how do they know what is inside so that they can use it for their own research? Search engine results and social media links are represented as surrogates, small easily digestible summaries of the underlying page. Search engines and social media have a different focus, and hence produce different surrogates than web archives. Search engine surrogates help a user answer the question "Will this link meet my information need?" Social media surrogates help a user decide "Should I click on this?" Our use case is subtly different. We hypothesize that groups of surrogates together are useful for summarizing a collection. We want to help users answer the question of "What does the underlying collection contain?" But which surrogate should we use? With Mechanical Turk participants, we evaluate six different surrogate types against each other. We find that the type of surrogate does not influence the time to complete the task we presented the participants. Of particular interest are social cards, surrogates typically found on social media, and browser thumbnails, screen captures of web pages rendered in a browser. At $p=0.0569$, and $p=0.0770$, respectively, we find that social cards and social cards paired side-by-side with browser thumbnails probably provide better collection understanding than the surrogates currently used by the popular Archive-It web archiving platform. We measure user interactions with each surrogate and find that users interact with social cards less than other types. The results of this study have implications for our web archive summarization work, live web curation platforms, social media, and more.
Multi-Modal Graph Interaction for Multi-Graph Convolution Network in Urban Spatiotemporal Forecasting
Venue: arXiv cs.LG 2019
Year: 2019

Graph convolution network based approaches have been recently used to model region-wise relationships in region-level prediction problems in urban computing. Each relationship represents a kind of spatial dependency, like region-wise distance or functional similarity. To incorporate multiple relationships into spatial feature extraction, we define the problem as a multi-modal machine learning problem on multi-graph convolution networks. Leveraging the advantage of multi-modal machine learning, we propose to develop modality interaction mechanisms for this problem, in order to reduce generalization error by reinforcing the learning of multimodal coordinated representations. In this work, we propose two interaction techniques for handling features in lower layers and higher layers respectively. In lower layers, we propose grouped GCN to combine the graph connectivity from different modalities for more complete spatial feature extraction. In higher layers, we adapt multi-linear relationship networks to GCN by exploring the dimension transformation and freezing part of the covariance structure. The adapted approach, called multi-linear relationship GCN, learns more generalized features to overcome the train-test divergence induced by time shifting. We evaluated our model on ridehailing demand forecasting problem using two real-world datasets. The proposed technique outperforms state-of-the art baselines in terms of prediction accuracy, training efficiency, interpretability and model robustness.
Equivalent and Approximate Transformations of Deep Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

Two networks are equivalent if they produce the same output for any given input. In this paper, we study the possibility of transforming a deep neural network to another network with a different number of units or layers, which can be either equivalent, a local exact approximation, or a global linear approximation of the original network. On the practical side, we show that certain rectified linear units (ReLUs) can be safely removed from a network if they are always active or inactive for any valid input. If we only need an equivalent network for a smaller domain, then more units can be removed and some layers collapsed. On the theoretical side, we constructively show that for any feed-forward ReLU network, there exists a global linear approximation to a 2-hidden-layer shallow network with a fixed number of units. This result is a balance between the increasing number of units for arbitrary approximation with a single layer and the known upper bound of $\lceil log(n_0+1)\rceil +1$ layers for exact representation, where $n_0$ is the input dimension. While the transformed network may require an exponential number of units to capture the activation patterns of the original network, we show that it can be made substantially smaller by only accounting for the patterns that define linear regions. Based on experiments with ReLU networks on the MNIST dataset, we found that $l_1$-regularization and adversarial training reduces the number of linear regions significantly as the number of stable units increases due to weight sparsity. Therefore, we can also intentionally train ReLU networks to allow for effective loss-less compression and approximation.
XLDA: Cross-Lingual Data Augmentation for Natural Language Inference and Question Answering
Venue: arXiv cs.CL 2019
Year: 2019

While natural language processing systems often focus on a single language, multilingual transfer learning has the potential to improve performance, especially for low-resource languages. We introduce XLDA, cross-lingual data augmentation, a method that replaces a segment of the input text with its translation in another language. XLDA enhances performance of all 14 tested languages of the cross-lingual natural language inference (XNLI) benchmark. With improvements of up to $4.8\%$, training with XLDA achieves state-of-the-art performance for Greek, Turkish, and Urdu. XLDA is in contrast to, and performs markedly better than, a more naive approach that aggregates examples in various languages in a way that each example is solely in one language. On the SQuAD question answering task, we see that XLDA provides a $1.0\%$ performance increase on the English evaluation set. Comprehensive experiments suggest that most languages are effective as cross-lingual augmentors, that XLDA is robust to a wide range of translation quality, and that XLDA is even more effective for randomly initialized models than for pretrained models.
Infusing domain knowledge in AI-based "black box" models for better explainability with application in bankruptcy prediction
Venue: arXiv cs.AI 2019
Year: 2019

Although "black box" models such as Artificial Neural Networks, Support Vector Machines, and Ensemble Approaches continue to show superior performance in many disciplines, their adoption in the sensitive disciplines (e.g., finance, healthcare) is questionable due to the lack of interpretability and explainability of the model. In fact, future adoption of "black box" models is difficult because of the recent rule of "right of explanation" by the European Union where a user can ask for an explanation behind an algorithmic decision, and the newly proposed bill by the US government, the "Algorithmic Accountability Act", which would require companies to assess their machine learning systems for bias and discrimination and take corrective measures. Top Bankruptcy Prediction Models are A.I.-based and are in need of better explainability -the extent to which the internal working mechanisms of an AI system can be explained in human terms. Although explainable artificial intelligence is an emerging field of research, infusing domain knowledge for better explainability might be a possible solution. In this work, we demonstrate a way to collect and infuse domain knowledge into a "black box" model for bankruptcy prediction. Our understanding from the experiments reveals that infused domain knowledge makes the output from the black box model more interpretable and explainable.
A New Algorithm for Decremental Single-Source Shortest Paths with Applications to Vertex-Capacitated Flow and Cut Problems
Venue: arXiv cs.DS 2019
Year: 2019

We study the vertex-decremental Single-Source Shortest Paths (SSSP) problem: given an undirected graph $G=(V,E)$ with lengths $\ell(e)\geq 1$ on its edges and a source vertex $s$, we need to support (approximate) shortest-path queries in $G$, as $G$ undergoes vertex deletions. In a shortest-path query, given a vertex $v$, we need to return a path connecting $s$ to $v$, whose length is at most $(1+ε)$ times the length of the shortest such path, where $ε$ is a given accuracy parameter. The problem has many applications, for example to flow and cut problems in vertex-capacitated graphs. Our main result is a randomized algorithm for vertex-decremental SSSP with total expected update time $O(n^{2+o(1)}\log L)$, that responds to each shortest-path query in $O(n\log L)$ time in expectation, returning a $(1+ε)$-approximate shortest path. The algorithm works against an adaptive adversary. The main technical ingredient of our algorithm is an $\tilde O(|E(G)|+ n^{1+o(1)})$-time algorithm to compute a \emph{core decomposition} of a given dense graph $G$, which allows us to compute short paths between pairs of query vertices in $G$ efficiently. We believe that this core decomposition algorithm may be of independent interest. We use our result for vertex-decremental SSSP to obtain $(1+ε)$-approximation algorithms for maximum $s$-$t$ flow and minimum $s$-$t$ cut in vertex-capacitated graphs, in expected time $n^{2+o(1)}$, and an $O(\log^4n)$-approximation algorithm for the vertex version of the sparsest cut problem with expected running time $n^{2+o(1)}$. These results improve upon the previous best known results for these problems in the regime where $m= ω(n^{1.5 + o(1)})$.
A Knowledge Graph-based Approach for Exploring the U.S. Opioid Epidemic
Venue: arXiv cs.CY 2019
Year: 2019

The United States is in the midst of an opioid epidemic with recent estimates indicating that more than 130 people die every day due to drug overdose. The over-prescription and addiction to opioid painkillers, heroin, and synthetic opioids, has led to a public health crisis and created a huge social and economic burden. Statistical learning methods that use data from multiple clinical centers across the US to detect opioid over-prescribing trends and predict possible opioid misuse are required. However, the semantic heterogeneity in the representation of clinical data across different centers makes the development and evaluation of such methods difficult and non-trivial. We create the Opioid Drug Knowledge Graph (ODKG) -- a network of opioid-related drugs, active ingredients, formulations, combinations, and brand names. We use the ODKG to normalize drug strings in a clinical data warehouse consisting of patient data from over 400 healthcare facilities in 42 different states. We showcase the use of ODKG to generate summary statistics of opioid prescription trends across US regions. These methods and resources can aid the development of advanced and scalable models to monitor the opioid epidemic and to detect illicit opioid misuse behavior. Our work is relevant to policymakers and pain researchers who wish to systematically assess factors that contribute to opioid over-prescribing and iatrogenic opioid addiction in the US.
On a scalable problem transformation method for multi-label learning
Venue: arXiv cs.IR 2019
Year: 2019

Binary relevance is a simple approach to solve multi-label learning problems where an independent binary classifier is built per each label. A common challenge with this in real-world applications is that the label space can be very large, making it difficult to use binary relevance to larger scale problems. In this paper, we propose a scalable alternative to this, via transforming the multi-label problem into a single binary classification. We experiment with a few variations of our method and show that our method achieves higher precision than binary relevance and faster execution times on a top-K recommender system task.