OpenRaiser/Intern-Atlas huggingface dataset:
Derivation of the Asymptotic Eigenvalue Distribution for Causal 2D-AR Models under Upscaling
Venue: arXiv cs.CR 2017
Year: 2017

This technical report describes the derivation of the asymptotic eigenvalue distribution for causal 2D-AR models under an upscaling scenario. Specifically, it tackles the analytical derivation of the asymptotic eigenvalue distribution of the sample autocorrelation matrix corresponding to genuine and upscaled images. It also includes the pseudocode of the derived approaches for resampling detection and resampling factor estimation that are based on this analysis.
Sorting sums of binary decision summands
Venue: arXiv cs.DS 2017
Year: 2017

A sum where each of the $N$ summands can be independently chosen from two choices yields $2^N$ possible summation outcomes. There is an $\mathcal{O}(K^2)$-algorithm that finds the $K$ smallest/largest of these sums by evading the enumeration of all sums.
Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering
Venue: arXiv cs.DS 2017
Year: 2017

We design the first online algorithm with poly-logarithmic competitive ratio for the edge-weighted degree-bounded Steiner forest(EW-DB-SF) problem and its generalized variant. We obtain our result by demonstrating a new generic approach for solving mixed packing/covering integer programs in the online paradigm. In EW-DB-SF we are given an edge-weighted graph with a degree bound for every vertex. Given a root vertex in advance we receive a sequence of terminal vertices in an online manner. Upon the arrival of a terminal we need to augment our solution subgraph to connect the new terminal to the root. The goal is to minimize the total weight of the solution while respecting the degree bounds on the vertices. In the offline setting edge-weighted degree-bounded Steiner tree (EW-DB-ST) and its many variations have been extensively studied since early eighties. Unfortunately the recent advancements in the online network design problems are inherently difficult to adapt for degree-bounded problems. In contrast in this paper we obtain our result by using structural properties of the optimal solution, and reducing the EW-DB-SF problem to an exponential-size mixed packing/covering integer program in which every variable appears only once in covering constraints. We then design a generic integral algorithm for solving this restricted family of IPs. We demonstrate a new technique for solving mixed packing/covering integer programs. Define the covering frequency k of a program as the maximum number of covering constraints in which a variable can participate. Let m denote the number of packing constraints. We design an online deterministic integral algorithm with competitive ratio of O(k log m) for the mixed packing/covering integer programs. We believe this technique can be used as an interesting alternative for the standard primal-dual techniques in solving online problems.
Piggybacking Codes for Network Coding: The High/Low SNR Regime
Venue: arXiv cs.IT 2017
Year: 2017

We propose a piggybacking scheme for network coding where strong source inputs piggyback the weaker ones, a scheme necessary and sufficient to achieve the cut-set upper bound at high/low-snr regime, a new asymptotically optimal operational regime for the multihop Amplify and Forward (AF) networks.
Semi-supervised classification for dynamic Android malware detection
Venue: arXiv cs.CR 2017
Year: 2017

A growing number of threats to Android phones creates challenges for malware detection. Manually labeling the samples into benign or different malicious families requires tremendous human efforts, while it is comparably easy and cheap to obtain a large amount of unlabeled APKs from various sources. Moreover, the fast-paced evolution of Android malware continuously generates derivative malware families. These families often contain new signatures, which can escape detection when using static analysis. These practical challenges can also cause traditional supervised machine learning algorithms to degrade in performance. In this paper, we propose a framework that uses model-based semi-supervised (MBSS) classification scheme on the dynamic Android API call logs. The semi-supervised approach efficiently uses the labeled and unlabeled APKs to estimate a finite mixture model of Gaussian distributions via conditional expectation-maximization and efficiently detects malwares during out-of-sample testing. We compare MBSS with the popular malware detection classifiers such as support vector machine (SVM), $k$-nearest neighbor (kNN) and linear discriminant analysis (LDA). Under the ideal classification setting, MBSS has competitive performance with 98\% accuracy and very low false positive rate for in-sample classification. For out-of-sample testing, the out-of-sample test data exhibit similar behavior of retrieving phone information and sending to the network, compared with in-sample training set. When this similarity is strong, MBSS and SVM with linear kernel maintain 90\% detection rate while $k$NN and LDA suffer great performance degradation. When this similarity is slightly weaker, all classifiers degrade in performance, but MBSS still performs significantly better than other classifiers.
SAFS: A Deep Feature Selection Approach for Precision Medicine
Venue: arXiv cs.LG 2017
Year: 2017

In this paper, we propose a new deep feature selection method based on deep architecture. Our method uses stacked auto-encoders for feature representation in higher-level abstraction. We developed and applied a novel feature learning approach to a specific precision medicine problem, which focuses on assessing and prioritizing risk factors for hypertension (HTN) in a vulnerable demographic subgroup (African-American). Our approach is to use deep learning to identify significant risk factors affecting left ventricular mass indexed to body surface area (LVMI) as an indicator of heart damage risk. The results show that our feature learning and representation approach leads to better results in comparison with others.
Subspace Designs based on Algebraic Function Fields
Venue: arXiv cs.CC 2017
Year: 2017

Subspace designs are a (large) collection of high-dimensional subspaces $\{H_i\}$ of $\F_q^m$ such that for any low-dimensional subspace $W$, only a small number of subspaces from the collection have non-trivial intersection with $W$; more precisely, the sum of dimensions of $W \cap H_i$ is at most some parameter $L$. The notion was put forth by Guruswami and Xing (STOC'13) with applications to list decoding variants of Reed-Solomon and algebraic-geometric codes, and later also used for explicit rank-metric codes with optimal list decoding radius. Guruswami and Kopparty (FOCS'13, Combinatorica'16) gave an explicit construction of subspace designs with near-optimal parameters. This construction was based on polynomials and has close connections to folded Reed-Solomon codes, and required large field size (specifically $q \ge m$). Forbes and Guruswami (RANDOM'15) used this construction to give explicit constant degree "dimension expanders" over large fields, and noted that subspace designs are a powerful tool in linear-algebraic pseudorandomness. Here, we construct subspace designs over any field, at the expense of a modest worsening of the bound $L$ on total intersection dimension. Our approach is based on a (non-trivial) extension of the polynomial-based construction to algebraic function fields, and instantiating the approach with cyclotomic function fields. Plugging in our new subspace designs in the construction of Forbes and Guruswami yields dimension expanders over $\F^n$ for any field $\F$, with logarithmic degree and expansion guarantee for subspaces of dimension $Ω(n/(\log \log n))$.
Improving DL-MU-MIMO Performance in IEEE 802.11ac Networks through Decoupled Scheduling
Venue: arXiv cs.NI 2017
Year: 2017

The IEEE 802.11ac standard introduces new downlink multi-user MIMO (DL-MU-MIMO) transmissions to up to four users in order to increase spatial reuse in wireless local area networks (WLANs). We argue that even better WLAN per- formance can be achieved by slightly modifying the DL-MU-MIMO scheduling. To this end we propose a new queuing mechanism based on the decoupling of EDCA and DL-MU-MIMO scheduling (DEMS) to avoid head-of-line blocking. We show that DEMS outperforms traditional 802.11ac scheduling based on first in, first out transmission queues. The improvement is shown in terms throughput achieved with: (a) more efficient channel usage, (b) increased probability of transmission of high priority traffic, and (c) decreased competition between frames destined to distinct users.
Reinforcement Learning with External Knowledge and Two-Stage Q-functions for Predicting Popular Reddit Threads
Venue: arXiv cs.CL 2017
Year: 2017

This paper addresses the problem of predicting popularity of comments in an online discussion forum using reinforcement learning, particularly addressing two challenges that arise from having natural language state and action spaces. First, the state representation, which characterizes the history of comments tracked in a discussion at a particular point, is augmented to incorporate the global context represented by discussions on world events available in an external knowledge source. Second, a two-stage Q-learning framework is introduced, making it feasible to search the combinatorial action space while also accounting for redundancy among sub-actions. We experiment with five Reddit communities, showing that the two methods improve over previous reported results on this task.
Modelling information manufacturing systems
Venue: arXiv cs.SE 2017
Year: 2017

The manufacture of an information product (IP) is akin to the manufacture of a physical product. Current approaches to model such information manufacturing systems (IMS), lack the ability to systematically represent the dynamic changes involved in manufacturing (or creating) an IP. They also have limitations to consistently include aspects of process and information management at an organizational level. This paper aims to address these limitations and presents a modelling approach, the IASDO model. Our work also represents a framework to evaluate the quality of the meta-models for IMS modelling which enable us to compare the IASDO model with current approaches.
k-Majority Digraphs and the Hardness of Voting with a Constant Number of Voters
Venue: arXiv cs.GT 2017
Year: 2017

Many hardness results in computational social choice make use of the fact that every directed graph may be induced as the pairwise majority relation of some preference profile. However, this fact requires a number of voters that is almost linear in the number of alternatives. It is therefore unclear whether these results remain intact when the number of voters is bounded, as is, for example, typically the case in search engine aggregation settings. In this paper, we provide a systematic study of majority digraphs for a constant number of voters resulting in analytical, experimental, and complexity-theoretic insights. First, we characterize the set of digraphs that can be induced by two and three voters, respectively, and give sufficient conditions for larger numbers of voters. Second, we present a surprisingly efficient implementation via SAT solving for computing the minimal number of voters that is required to induce a given digraph and experimentally evaluate how many voters are required to induce the majority digraphs of real-world and generated preference profiles. Finally, we leverage our sufficient conditions to show that the winner determination problem of various well-known voting rules remains hard even when there is only a small constant number of voters. In particular, we show that Kemeny's rule is hard to evaluate for 7 voters, while previous methods could only establish such a result for constant even numbers of voters.
Settling the query complexity of non-adaptive junta testing
Venue: arXiv cs.CC 2017
Year: 2017

We prove that any non-adaptive algorithm that tests whether an unknown Boolean function $f: \{0, 1\}^n\to \{0, 1\}$ is a $k$-junta or $ε$-far from every $k$-junta must make $\widetildeΩ(k^{3/2} / ε)$ many queries for a wide range of parameters $k$ and $ε$. Our result dramatically improves previous lower bounds from [BGSMdW13, STW15], and is essentially optimal given Blais's non-adaptive junta tester from [Blais08], which makes $\widetilde{O}(k^{3/2})/ε$ queries. Combined with the adaptive tester of [Blais09] which makes $O(k\log k + k /ε)$ queries, our result shows that adaptivity enables polynomial savings in query complexity for junta testing.
Rate-Splitting to Mitigate Residual Transceiver Hardware Impairments in Massive MIMO Systems
Venue: arXiv cs.IT 2017
Year: 2017

Rate-Splitting (RS) has recently been shown to provide significant performance benefits in various multi-user transmission scenarios. In parallel, the huge degrees-of-freedom provided by the appealing massive Multiple-Input Multiple-Output (MIMO) necessitate the employment of inexpensive hardware, being more prone to hardware imperfections, in order to be a cost-efficient technology. Hence, in this work, we focus on a realistic massive Multiple-Input Single-Output (MISO) Broadcast Channel (BC) hampered by the inevitable hardware impairments. We consider a general experimentally validated model of hardware impairments, accounting for the presence of \textit{multiplicative distortion} due to phase noise, \textit{additive distortion noise} and \textit{thermal noise amplification}. Under both scenarios with perfect and imperfect channel state information at the transmitter (CSIT), we analyze the potential robustness of RS to each separate hardware imperfection. We analytically assess the sum-rate degradation due to hardware imperfections. Interestingly, in the case of imperfect CSIT, we demonstrate that RS is a robust strategy for multiuser MIMO in the presence of phase and amplified thermal noise, since its sum-rate does not saturate at high signal-to-noise ratio (SNR), contrary to conventional techniques. On the other hand, the additive impairments always lead to a sum-rate saturation at high SNR, even after the application of RS. However, RS still enhances the performance. Furthermore, as the number of users increases, the gains provided by RS decrease not only in ideal conditions, but in practical conditions with RTHIs as well.
SwellShark: A Generative Model for Biomedical Named Entity Recognition without Labeled Data
Venue: arXiv cs.CL 2017
Year: 2017

We present SwellShark, a framework for building biomedical named entity recognition (NER) systems quickly and without hand-labeled data. Our approach views biomedical resources like lexicons as function primitives for autogenerating weak supervision. We then use a generative model to unify and denoise this supervision and construct large-scale, probabilistically labeled datasets for training high-accuracy NER taggers. In three biomedical NER tasks, SwellShark achieves competitive scores with state-of-the-art supervised benchmarks using no hand-labeled training data. In a drug name extraction task using patient medical records, one domain expert using SwellShark achieved within 5.1% of a crowdsourced annotation approach -- which originally utilized 20 teams over the course of several weeks -- in 24 hours.
Massive MIMO Downlink 1-Bit Precoding with Linear Programming for PSK Signaling
Venue: arXiv cs.IT 2017
Year: 2017

Quantized massive multiple-input-multiple-output (MIMO) systems are gaining more interest due to their power efficiency. We present a new precoding technique to mitigate the multi-user interference and the quantization distortions in a downlink multi-user (MU) multiple-input-single-output (MISO) system with 1-bit quantization at the transmitter. This work is restricted to PSK modulation schemes. The transmit signal vector is optimized for every desired received vector taking into account the 1-bit quantization. The optimization is based on maximizing the safety margin to the decision thresholds of the PSK modulation. Simulation results show a significant gain in terms of the uncoded bit-error-ratio (BER) compared to the existing linear precoding techniques.
A Theory of Nonlinear Signal-Noise Interactions in Wavelength Division Multiplexed Coherent Systems
Venue: arXiv cs.IT 2017
Year: 2017

A general theory of nonlinear signal-noise interactions for wavelength division multiplexed fiber-optic coherent transmission systems is presented. This theory is based on the regular perturbation treatment of the nonlinear Schrodinger equation, which governs the wave propagation in the optical fiber, and is exact up to the first order in the fiber nonlinear coefficient. It takes into account all cross-channel nonlinear four-wave mixing contributions to the total variance of nonlinear distortions, dependency on modulation format, erbium-doped fiber and and backward Raman amplification schemes, heterogeneous spans, and chromatic dispersion to all orders; moreover, it is computationally efficient, being 2-3 orders of magnitude faster than the available alternative treatments in the literature. This theory is used to estimate the impact of signal-noise interaction on uncompensated, as well as on nonlinearity-compensated systems with ideal multi-channel digital-backpropagation.
LiftUpp: Support to develop learner performance
Venue: arXiv cs.CY 2017
Year: 2017

Various motivations exist to move away from the simple assessment of knowledge towards the more complex assessment and development of competence. However, to accommodate such a change, high demands are put on the supporting e-infrastructure in terms of intelligently collecting and analysing data. In this paper, we discuss these challenges and how they are being addressed by LiftUpp, a system that is now used in 70% of UK dental schools, and is finding wider applications in physiotherapy, medicine and veterinary science. We describe how data is collected for workplace-based development in dentistry using a dedicated iPad app, which enables an integrated approach to linking and assessing work flows, skills and learning outcomes. Furthermore, we detail how the various forms of collected data can be fused, visualized and integrated with conventional forms of assessment. This enables curriculum integration, improved real-time student feedback, support for administration, and informed instructional planning. Together these facets contribute to better support for the development of learners' competence in situated learning setting, as well as an improved experience. Finally, we discuss several directions for future research on intelligent teaching systems that are afforded by using the design present within LiftUpp.
Symmetry in Software Synthesis
Venue: arXiv cs.DC 2017
Year: 2017

With the surge of multi- and manycores, much research has focused on algorithms for mapping and scheduling on these complex platforms. Large classes of these algorithms face scalability problems. This is why diverse methods are commonly used for reducing the search space. While most such approaches leverage the inherent symmetry of architectures and applications, they do it in a problem-specific and intuitive way. However, intuitive approaches become impractical with growing hardware complexity, like Network-on-Chip interconnect or heterogeneous cores. In this paper, we present a formal framework that can determine the inherent symmetry of architectures and applications algorithmically and leverage these for problems in software synthesis. Our approach is based on the mathematical theory of groups and a generalization called inverse semigroups. We evaluate our approach in two state-of-the-art mapping frameworks. Even for the platforms with a handful of cores of today and moderate-size benchmarks, our approach consistently yields reductions of the overall execution time of algorithms, accelerating them by a factor up to 10 in our experiments, or improving the quality of the results.
Distant Supervision for Topic Classification of Tweets in Curated Streams
Venue: arXiv cs.IR 2017
Year: 2017

We tackle the challenge of topic classification of tweets in the context of analyzing a large collection of curated streams by news outlets and other organizations to deliver relevant content to users. Our approach is novel in applying distant supervision based on semi-automatically identifying curated streams that are topically focused (for example, on politics, entertainment, or sports). These streams provide a source of labeled data to train topic classifiers that can then be applied to categorize tweets from more topically-diffuse streams. Experiments on both noisy labels and human ground-truth judgments demonstrate that our approach yields good topic classifiers essentially "for free", and that topic classifiers trained in this manner are able to dynamically adjust for topic drift as news on Twitter evolves.
Content-Based Video-Music Retrieval Using Soft Intra-Modal Structure Constraint
Venue: arXiv cs.CV 2017
Year: 2017

Up to now, only limited research has been conducted on cross-modal retrieval of suitable music for a specified video or vice versa. Moreover, much of the existing research relies on metadata such as keywords, tags, or associated description that must be individually produced and attached posterior. This paper introduces a new content-based, cross-modal retrieval method for video and music that is implemented through deep neural networks. We train the network via inter-modal ranking loss such that videos and music with similar semantics end up close together in the embedding space. However, if only the inter-modal ranking constraint is used for embedding, modality-specific characteristics can be lost. To address this problem, we propose a novel soft intra-modal structure loss that leverages the relative distance relationship between intra-modal samples before embedding. We also introduce reasonable quantitative and qualitative experimental protocols to solve the lack of standard protocols for less-mature video-music related tasks. Finally, we construct a large-scale 200K video-music pair benchmark. All the datasets and source code can be found in our online repository (https://github.com/csehong/VM-NET).
Numerical Evaluation of Cloud-Side Shuffling Defenses against DDoS Attacks on Proxied Multiserver Systems
Venue: arXiv cs.CR 2017
Year: 2017

We consider a cloud based multiserver system, that may be cloud based, consisting of a set of replica application servers behind a set of proxy (indirection) servers which interact directly with clients over the Internet. We address cloud-side proactive and reactive defenses to combat DDoS attacks that may target this system. DDoS attacks are endemic with some notable attacks occurring just this past fall. Volumetric attacks may target proxies while "low volume" attacks may target replicas. After reviewing existing and proposed defenses, such as changing proxy IP addresses (a "moving target" technique to combat the reconnaissance phase of the botnet) and fission of overloaded servers, we focus on evaluation of defenses based on shuffling client-to-server assignments that can be both proactive and reactive to a DDoS attack. Our evaluations are based on a binomial distribution model that well agrees with simulations and preliminary experiments on a prototype that is also described.