OpenRaiser/Intern-Atlas huggingface dataset:
Antenna Selection in MIMO Non-orthogonal Multiple Access Systems
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers the joint antenna selection (AS) problem for a classical two-user MIMO non-orthogonal multiple access (NOMA) system, where both the base station (BS) and users (UEs) are equipped with multiple antennas. Specifically, several computationally-efficient AS algorithms are developed for two commonly-used NOMA scenarios: fixed power allocation NOMA (F-NOMA) and cognitive radio-inspired NOMA (CR-NOMA). For the F-NOMA system, two novel AS schemes, namely max-max-max AS (A$^3$-AS) and max-min-max AS (AIA-AS), are proposed to maximize the system sum-rate, without and with the consideration of user fairness, respectively. In the CR-NOMA network, a novel AS algorithm, termed maximum-channel-gain-based AS (MCG-AS), is proposed to maximize the achievable rate of the secondary user, under the condition that the primary user's quality of service requirement is satisfied. The asymptotic closed-form expressions of the average sum-rate for A$^3$-AS and AIA-AS and that of the average rate of the secondary user for MCG-AS are derived, respectively. Numerical results demonstrate that the AIA-AS provides better user-fairness, while the A$^3$-AS achieves a near-optimal sum-rate in F-NOMA systems. For the CR-NOMA scenario, MCG-AS achieves a near-optimal performance in a wide SNR regime. Furthermore, all the proposed AS algorithms yield a significant computational complexity reduction, compared to exhaustive search-based counterparts.
On Natural Deduction for Herbrand Constructive Logics II: Curry-Howard Correspondence for Markov's Principle in First-Order Logic and Arithmetic
Venue: arXiv cs.LO 2017
Year: 2017

Intuitionistic first-order logic extended with a restricted form of Markov's principle is constructive and admits a Curry-Howard correspondence, as shown by Herbelin. We provide a simpler proof of that result and then we study intuitionistic first-order logic extended with unrestricted Markov's principle. Starting from classical natural deduction, we restrict the excluded middle and we obtain a natural deduction system and a parallel Curry-Howard isomorphism for the logic. We show that proof terms for existentially quantified formulas reduce to a list of individual terms representing all possible witnesses. As corollary, we derive that the logic is Herbrand constructive: whenever it proves any existential formula, it proves also an Herbrand disjunction for the formula. Finally, using the techniques just introduced, we also provide a new computational interpretation of Arithmetic with Markov's principle.
Video Propagation Networks
Venue: arXiv cs.CV 2017
Year: 2017

We propose a technique that propagates information forward through video data. The method is conceptually simple and can be applied to tasks that require the propagation of structured information, such as semantic labels, based on video content. We propose a 'Video Propagation Network' that processes video frames in an adaptive manner. The model is applied online: it propagates information forward without the need to access future frames. In particular we combine two components, a temporal bilateral network for dense and video adaptive filtering, followed by a spatial network to refine features and increased flexibility. We present experiments on video object segmentation and semantic video segmentation and show increased performance comparing to the best previous task-specific methods, while having favorable runtime. Additionally we demonstrate our approach on an example regression task of color propagation in a grayscale video.
Optimizing Stochastic Scheduling in Fork-Join Queueing Models: Bounds and Applications
Venue: arXiv cs.PF 2017
Year: 2017

Fork-Join (FJ) queueing models capture the dynamics of system parallelization under synchronization constraints, for example, for applications such as MapReduce, multipath transmission and RAID systems. Arriving jobs are first split into tasks and mapped to servers for execution, such that a job can only leave the system when all of its tasks are executed. In this paper, we provide computable stochastic bounds for the waiting and response time distributions for heterogeneous FJ systems under general parallelization benefit. Our main contribution is a generalized mathematical framework for probabilistic server scheduling strategies that are essentially characterized by a probability distribution over the number of utilized servers, and the optimization thereof. We highlight the trade-off between the scaling benefit due to parallelization and the FJ inherent synchronization penalty. Further, we provide optimal scheduling strategies for arbitrary scaling regimes that map to different levels of parallelization benefit. One notable insight obtained from our results is that different applications with varying parallelization benefits result in different optimal strategies. Finally, we complement our analytical results by applying them to various applications showing the optimality of the proposed scheduling strategies.
Greedy Routing and the Algorithmic Small-World Phenomenom
Venue: arXiv cs.SI 2017
Year: 2017

The algorithmic small-world phenomenon, empirically established by Milgram's letter forwarding experiments from the 60s, was theoretically explained by Kleinberg in 2000. However, from today's perspective his model has several severe shortcomings that limit the applicability to real-world networks. In order to give a more convincing explanation of the algorithmic small-world phenomenon, we study decentralized greedy routing in a more flexible random graph model (geometric inhomogeneous random graphs) which overcomes all previous shortcomings. Apart from exhibiting good properties in theory, it has also been extensively experimentally validated that this model reasonably captures real-world networks. In this model, the greedy routing protocol is purely distributed as each vertex only needs to know information about its direct neighbors. We prove that it succeeds with constant probability, and in case of success almost surely finds an almost shortest path of length θ(loglog n), where our bound is tight including the leading constant. Moreover, we study natural local patching methods which augment greedy routing by backtracking and which do not require any global knowledge. We show that such methods can ensure success probability 1 in an asymptotically tight number of steps. These results also address the question of Krioukov et al. whether there are efficient local routing protocols for the internet graph. There were promising experimental studies, but the question remained unsolved theoretically. Our results give for the first time a rigorous and analytical affirmative answer.
SonoNet: Real-Time Detection and Localisation of Fetal Standard Scan Planes in Freehand Ultrasound
Venue: arXiv cs.CV 2017
Year: 2017

Identifying and interpreting fetal standard scan planes during 2D ultrasound mid-pregnancy examinations are highly complex tasks which require years of training. Apart from guiding the probe to the correct location, it can be equally difficult for a non-expert to identify relevant structures within the image. Automatic image processing can provide tools to help experienced as well as inexperienced operators with these tasks. In this paper, we propose a novel method based on convolutional neural networks which can automatically detect 13 fetal standard views in freehand 2D ultrasound data as well as provide a localisation of the fetal structures via a bounding box. An important contribution is that the network learns to localise the target anatomy using weak supervision based on image-level labels only. The network architecture is designed to operate in real-time while providing optimal output for the localisation task. We present results for real-time annotation, retrospective frame retrieval from saved videos, and localisation on a very large and challenging dataset consisting of images and video recordings of full clinical anomaly screenings. We found that the proposed method achieved an average F1-score of 0.798 in a realistic classification experiment modelling real-time detection, and obtained a 90.09% accuracy for retrospective frame retrieval. Moreover, an accuracy of 77.8% was achieved on the localisation task.
Building Diversified Multiple Trees for Classification in High Dimensional Noisy Biomedical Data
Venue: arXiv cs.LG 2017
Year: 2017

It is common that a trained classification model is applied to the operating data that is deviated from the training data because of noise. This paper demonstrates that an ensemble classifier, Diversified Multiple Tree (DMT), is more robust in classifying noisy data than other widely used ensemble methods. DMT is tested on three real world biomedical data sets from different laboratories in comparison with four benchmark ensemble classifiers. Experimental results show that DMT is significantly more accurate than other benchmark ensemble classifiers on noisy test data. We also discuss a limitation of DMT and its possible variations.
X-ray In-Depth Decomposition: Revealing The Latent Structures
Venue: arXiv cs.CV 2017
Year: 2017

X-ray radiography is the most readily available imaging modality and has a broad range of applications that spans from diagnosis to intra-operative guidance in cardiac, orthopedics, and trauma procedures. Proper interpretation of the hidden and obscured anatomy in X-ray images remains a challenge and often requires high radiation dose and imaging from several perspectives. In this work, we aim at decomposing the conventional X-ray image into d X-ray components of independent, non-overlapped, clipped sub-volumes using deep learning approach. Despite the challenging aspects of modeling such a highly ill-posed problem, exciting and encouraging results are obtained paving the path for further contributions in this direction.
Personalized Image-based User Authentication using Wearable Cameras
Venue: arXiv cs.CR 2017
Year: 2017

Personal devices (e.g. laptops, tablets, and mobile phones) are conventional in daily life and have the ability to store users' private data. The security problems related to these appliances have become a primary concern for both users and researchers. In this paper, we analyse first-person-view videos to develop a personalized user authentication mechanism. Our proposed algorithm generates provisional image-based passwords which benefit a variety of purposes such as unlocking a mobile device or fallback authentication. First, representative frames are extracted from the egocentric videos. Then, they are split into distinguishable segments before a clustering procedure is applied to discard repetitive scenes. The whole process aims to retain memorable images to form the authentication challenges. We integrate eye tracking data to select informative sequences of video frames and suggest a blurriness-based method if an eye-facing camera is not available. To evaluate our system, we perform experiments in different settings including object-interaction activities and traveling contexts. Even though our mechanism produces variable graphical passwords, the log-in effort for the user is comparable with approaches based on static challenges. We verified the authentication challenges in the presence of a random and an informed attacker who is familiar with the environment and observed that the time required and the number of attempts are significantly higher than for the legitimate user, making it possible to detect attacks on the authentication system.
Corralling a Band of Bandit Algorithms
Venue: arXiv cs.LG 2017
Year: 2017

We study the problem of combining multiple bandit algorithms (that is, online learning algorithms with partial feedback) with the goal of creating a master algorithm that performs almost as well as the best base algorithm if it were to be run on its own. The main challenge is that when run with a master, base algorithms unavoidably receive much less feedback and it is thus critical that the master not starve a base algorithm that might perform uncompetitively initially but would eventually outperform others if given enough feedback. We address this difficulty by devising a version of Online Mirror Descent with a special mirror map together with a sophisticated learning rate scheme. We show that this approach manages to achieve a more delicate balance between exploiting and exploring base algorithms than previous works yielding superior regret bounds. Our results are applicable to many settings, such as multi-armed bandits, contextual bandits, and convex bandits. As examples, we present two main applications. The first is to create an algorithm that enjoys worst-case robustness while at the same time performing much better when the environment is relatively easy. The second is to create an algorithm that works simultaneously under different assumptions of the environment, such as different priors or different loss structures.
Syntactic Structures of Regular Languages
Venue: arXiv cs.FL 2017
Year: 2017

We introduce here the notion of syntactic lattice algebra which is an analogy of the syntactic monoid and of the syntactic semiring. We present a unified approach to get those three structures.
Complexity theory for spaces of integrable functions
Venue: arXiv cs.CC 2017
Year: 2017

This paper investigates second-order representations in the sense of Kawamura and Cook for spaces of integrable functions that regularly show up in analysis. It builds upon prior work about the space of continuous functions on the unit interval: Kawamura and Cook introduced a representation inducing the right complexity classes and proved that it is the weakest second-order representation such that evaluation is polynomial-time computable. The first part of this paper provides a similar representation for the space of integrable functions on a bounded subset of Euclidean space: The weakest representation rendering integration over boxes is polynomial-time computable. In contrast to the representation of continuous functions, however, this representation turns out to be discontinuous with respect to both the norm and the weak topology. The second part modifies the representation to be continuous and generalizes it to Lp-spaces. The arising representations are proven to be computably equivalent to the standard representations of these spaces as metric spaces and to still render integration polynomial-time computable. The family is extended to cover Sobolev spaces on the unit interval, where less basic operations like differentiation and some Sobolev embeddings are shown to be polynomial-time computable. Finally as a further justification quantitative versions of the Arzelà-Ascoli and Fréchet-Kolmogorov Theorems are presented and used to argue that these representations fulfill a minimality condition. To provide tight bounds for the Fréchet-Kolmogorov Theorem, a form of exponential time computability of the norm of Lp is proven.
Computational Complexity of Testing Proportional Justified Representation
Venue: arXiv cs.GT 2017
Year: 2017

We consider a committee voting setting in which each voter approves of a subset of candidates and based on the approvals, a target number of candidates are selected. Aziz et al. (2015) proposed two representation axioms called justified representation and extended justified representation. Whereas the former can be tested as well as achieved in polynomial time, the latter property is coNP-complete to test and no polynomial-time algorithm is known to achieve it. Interestingly, S{á}nchez-Fern{á}ndez et~al. (2016) proposed an intermediate property called proportional justified representation that admits a polynomial-time algorithm to achieve. The complexity of testing proportional justified representation has remained an open problem. In this paper, we settle the complexity by proving that testing proportional justified representation is coNP-complete. We complement the complexity result by showing that the problem admits efficient algorithms if any of the following parameters are bounded: (1) number of voters (2) number of candidates (3) maximum number of candidates approved by a voter (4) maximum number of voters approving a given candidate.
Stochastic Runtime Analysis of a Cross Entropy Algorithm for Traveling Salesman Problems
Venue: arXiv cs.DS 2017
Year: 2017

This article analyzes the stochastic runtime of a Cross-Entropy Algorithm on two classes of traveling salesman problems. The algorithm shares main features of the famous Max-Min Ant System with iteration-best reinforcement. For simple instances that have a $\{1,n\}$-valued distance function and a unique optimal solution, we prove a stochastic runtime of $O(n^{6+ε})$ with the vertex-based random solution generation, and a stochastic runtime of $O(n^{3+ε}\ln n)$ with the edge-based random solution generation for an arbitrary $ε\in (0,1)$. These runtimes are very close to the known expected runtime for variants of Max-Min Ant System with best-so-far reinforcement. They are obtained for the stronger notion of stochastic runtime, which means that an optimal solution is obtained in that time with an overwhelming probability, i.e., a probability tending exponentially fast to one with growing problem size. We also inspect more complex instances with $n$ vertices positioned on an $m\times m$ grid. When the $n$ vertices span a convex polygon, we obtain a stochastic runtime of $O(n^{3}m^{5+ε})$ with the vertex-based random solution generation, and a stochastic runtime of $O(n^{2}m^{5+ε})$ for the edge-based random solution generation. When there are $k = O(1)$ many vertices inside a convex polygon spanned by the other $n-k$ vertices, we obtain a stochastic runtime of $O(n^{4}m^{5+ε}+n^{6k-1}m^ε)$ with the vertex-based random solution generation, and a stochastic runtime of $O(n^{3}m^{5+ε}+n^{3k}m^ε)$ with the edge-based random solution generation. These runtimes are better than the expected runtime for the so-called $(μ\!+\!λ)$ EA reported in a recent article, and again obtained for the stronger notion of stochastic runtime.
Nash Equilibrium Seeking with Non-doubly Stochastic Communication Weight Matrix
Venue: arXiv cs.SY 2017
Year: 2017

A distributed Nash equilibrium seeking algorithm is presented for networked games. We assume an incomplete information available to each player about the other players' actions. The players communicate over a strongly connected digraph to send/receive the estimates of the other players' actions to/from the other local players according to a gossip communication protocol. Due to asymmetric information exchange between the players, a non-doubly (row) stochastic weight matrix is defined. We show that, due to the non-doubly stochastic property, the total average of all players' estimates is not preserved for the next iteration which results in having no exact convergence. We present an almost sure convergence proof of the algorithm to a Nash equilibrium of the game. Then, we extend the algorithm for graphical games in which all players' cost functions are only dependent on the local neighboring players over an interference digraph. We design an assumption on the communication digraph such that the players are able to update all the estimates of the players who interfere with their cost functions. It is shown that the communication digraph needs to be a superset of a transitive reduction of the interference digraph. Finally, we verify the efficacy of the algorithm via a simulation on a social media behavioral case.
Certifying Confluence Proofs via Relative Termination and Rule Labeling
Venue: arXiv cs.LO 2017
Year: 2017

The rule labeling heuristic aims to establish confluence of (left-)linear term rewrite systems via decreasing diagrams. We present a formalization of a confluence criterion based on the interplay of relative termination and the rule labeling in the theorem prover Isabelle. Moreover, we report on the integration of this result into the certifier CeTA, facilitating the checking of confluence certificates based on decreasing diagrams. The power of the method is illustrated by an experimental evaluation on a (standard) collection of confluence problems.
Poisson Cluster Process Based Analysis of HetNets with Correlated User and Base Station Locations
Venue: arXiv cs.IT 2017
Year: 2017

This paper develops a new approach to the modeling and analysis of HetNets that accurately incorporates coupling across the locations of users and base stations, which exists due to the deployment of small cell base stations (SBSs) at the places of high user density (termed user hotspots in this paper). Modeling the locations of the geographical centers of user hotspots as a homogeneous Poisson Point Process (PPP), we assume that the users and SBSs are clustered around each user hotspot center independently with two different distributions. The macrocell base station (BS) locations are modeled by an independent PPP. This model is consistent with the user and SBS configurations considered by 3GPP. Using this model, we study the performance of a typical user in terms of coverage probability and throughput for two association policies: i) Policy 1, under which a typical user is served by the open-access BS that provides maximum averaged received power, and ii) Policy 2, under which the typical user is served by the small cell tier if the maximum averaged received power from the open-access SBSs is greater than a certain power threshold; and macro tier otherwise. A key intermediate step in our analysis is the derivation of distance distributions from a typical user to the open-access and closed-access interfering SBSs. Our analysis demonstrates that as the number of SBSs reusing the same resource block increases, coverage probability decreases whereas throughput increases. Therefore, contrary to the usual assumption of orthogonal channelization, it is reasonable to assign the same resource block to multiple SBSs in a given cluster as long as the coverage probability remains acceptable. This approach to HetNet modeling and analysis significantly generalizes the state-of-the-art approaches that are based on modeling the locations of BSs and users by independent PPPs.
A Context-aware Attention Network for Interactive Question Answering
Venue: arXiv cs.CL 2017
Year: 2017

Neural network based sequence-to-sequence models in an encoder-decoder framework have been successfully applied to solve Question Answering (QA) problems, predicting answers from statements and questions. However, almost all previous models have failed to consider detailed context information and unknown states under which systems do not have enough information to answer given questions. These scenarios with incomplete or ambiguous information are very common in the setting of Interactive Question Answering (IQA). To address this challenge, we develop a novel model, employing context-dependent word-level attention for more accurate statement representations and question-guided sentence-level attention for better context modeling. We also generate unique IQA datasets to test our model, which will be made publicly available. Employing these attention mechanisms, our model accurately understands when it can output an answer or when it requires generating a supplementary question for additional input depending on different contexts. When available, user's feedback is encoded and directly applied to update sentence-level attention to infer an answer. Extensive experiments on QA and IQA datasets quantitatively demonstrate the effectiveness of our model with significant improvement over state-of-the-art conventional QA models.