OpenRaiser/Intern-Atlas huggingface dataset:
Power of $d$ Choices with Simple Tabulation
Venue: arXiv cs.DS 2018
Year: 2018

Suppose that we are to place $m$ balls into $n$ bins sequentially using the $d$-choice paradigm: For each ball we are given a choice of $d$ bins, according to $d$ hash functions $h_1,\dots,h_d$ and we place the ball in the least loaded of these bins breaking ties arbitrarily. Our interest is in the number of balls in the fullest bin after all $m$ balls have been placed. Azar et al. [STOC'94] proved that when $m=O(n)$ and when the hash functions are fully random the maximum load is at most $\frac{\lg \lg n }{\lg d}+O(1)$ whp (i.e. with probability $1-O(n^{-γ})$ for any choice of $γ$). In this paper we suppose that the $h_1,\dots,h_d$ are simple tabulation hash functions. Generalising a result by Dahlgaard et al [SODA'16] we show that for an arbitrary constant $d\geq 2$ the maximum load is $O(\lg \lg n)$ whp, and that expected maximum load is at most $\frac{\lg \lg n}{\lg d}+O(1)$. We further show that by using a simple tie-breaking algorithm introduced by Vöcking [J.ACM'03] the expected maximum load drops to $\frac{\lg \lg n}{d\lg φ_d}+O(1)$ where $φ_d$ is the rate of growth of the $d$-ary Fibonacci numbers. Both of these expected bounds match those of the fully random setting. The analysis by Dahlgaard et al. relies on a proof by Pătraşcu and Thorup [J.ACM'11] concerning the use of simple tabulation for cuckoo hashing. We need here a generalisation to $d>2$ hash functions, but the original proof is an 8-page tour de force of ad-hoc arguments that do not appear to generalise. Our main technical contribution is a shorter, simpler and more accessible proof of the result by Pătraşcu and Thorup, where the relevant parts generalise nicely to the analysis of $d$ choices.
Enriching a Linear/Non-linear Lambda Calculus: A Programming Language for String Diagrams
Venue: arXiv cs.LO 2018
Year: 2018

Linear/non-linear (LNL) models, as described by Benton, soundly model a LNL term calculus and LNL logic closely related to intuitionistic linear logic. Every such model induces a canonical enrichment that we show soundly models a LNL lambda calculus for string diagrams, introduced by Rios and Selinger (with primary application in quantum computing). Our abstract treatment of this language leads to simpler concrete models compared to those presented so far. We also extend the language with general recursion and prove soundness. Finally, we present an adequacy result for the diagram-free fragment of the language which corresponds to a modified version of Benton and Wadler's adjoint calculus with recursion.
Capturing Capacity and Profit Gains with Base Station Sharing in mmWave Cellular Networks
Venue: arXiv cs.IT 2018
Year: 2018

Due to the greater path loss, shadowing, and increased effect of blockage in millimeter wave cellular networks, base station sharing among network service providers has the potential to significantly improve overall network capacity. However, a service provider may find that despite the technical gains, sharing actually reduces its profits because it makes price competition between service providers tougher. In this work, a weighted scheduling algorithm is described, which gives greater control over how the airtime resource is allocated within a shared cell. It is shown that, under certain market conditions, there exist scheduling weights such that base station sharing is more profitable than not sharing for both service providers in a duopoly market, while still achieving almost as much network capacity as in a conventional base station sharing scenario. Thus, both technical and economic benefits of base station sharing may be realized simultaneously.
Prospects for Theranostics in Neurosurgical Imaging: Empowering Confocal Laser Endomicroscopy Diagnostics via Deep Learning
Venue: arXiv cs.CV 2018
Year: 2018

Confocal laser endomicroscopy (CLE) is an advanced optical fluorescence imaging technology that has the potential to increase intraoperative precision, extend resection, and tailor surgery for malignant invasive brain tumors because of its subcellular dimension resolution. Despite its promising diagnostic potential, interpreting the gray tone fluorescence images can be difficult for untrained users. In this review, we provide a detailed description of bioinformatical analysis methodology of CLE images that begins to assist the neurosurgeon and pathologist to rapidly connect on-the-fly intraoperative imaging, pathology, and surgical observation into a conclusionary system within the concept of theranostics. We present an overview and discuss deep learning models for automatic detection of the diagnostic CLE images and discuss various training regimes and ensemble modeling effect on the power of deep learning predictive models. Two major approaches reviewed in this paper include the models that can automatically classify CLE images into diagnostic/nondiagnostic, glioma/nonglioma, tumor/injury/normal categories and models that can localize histological features on the CLE images using weakly supervised methods. We also briefly review advances in the deep learning approaches used for CLE image analysis in other organs. Significant advances in speed and precision of automated diagnostic frame selection would augment the diagnostic potential of CLE, improve operative workflow and integration into brain tumor surgery. Such technology and bioinformatics analytics lend themselves to improved precision, personalization, and theranostics in brain tumor treatment.
Optimal-margin evolutionary classifier
Venue: arXiv cs.NE 2018
Year: 2018

We introduce a novel approach for discriminative classification using evolutionary algorithms. We first propose an algorithm to optimize the total loss value using a modified 0-1 loss function in a one-dimensional space for classification. We then extend this algorithm for multi-dimensional classification using an evolutionary algorithm. The proposed evolutionary algorithm aims to find a hyperplane which best classifies instances while minimizes the classification risk. We test particle swarm optimization, evolutionary strategy, and covariance matrix adaptation evolutionary strategy for optimization purpose. Finally, we compare our results with well-established and state-of-the-art classification algorithms, for both binary and multi-class classification, on 19 benchmark classification problems, with and without noise and outliers. Results show that the performance of the proposed algorithm is significantly (t-test) better than all other methods in almost all problems tested. We also show that the proposed algorithm is significantly more robust against noise and outliers comparing to other methods. The running time of the algorithm is within a reasonable range for the solution of real-world classification problems.
Recommending Outfits from Personal Closet
Venue: arXiv cs.CV 2018
Year: 2018

We consider grading a fashion outfit for recommendation, where we assume that users have a closet of items and we aim at producing a score for an arbitrary combination of items in the closet. The challenge in outfit grading is that the input to the system is a bag of item pictures that are unordered and vary in size. We build a deep neural network-based system that can take variable-length items and predict a score. We collect a large number of outfits from a popular fashion sharing website, Polyvore, and evaluate the performance of our grading system. We compare our model with a random-choice baseline, both on the traditional classification evaluation and on people's judgment using a crowdsourcing platform. With over 84% in classification accuracy and 91% matching ratio to human annotators, our model can reliably grade the quality of an outfit. We also build an outfit recommender on top of our grader to demonstrate the practical application of our model for a personal closet assistant.
A security approach based on honeypots: Protecting Online Social network from malicious profiles
Venue: arXiv cs.CR 2018
Year: 2018

In the recent years, the fast development and the exponential utilization of social networks have prompted an expansion of social Computing. In social networks users are interconnected by edges or links, where Facebook, twitter, LinkedIn are most popular social networks websites. Due to the growing popularity of these sites they serve as a target for cyber criminality and attacks. It is mostly based on how users are using these sites like Twitter and others. Attackers can easily access and gather personal and sensitive users information. Users are less aware and least concerned about the security setting. And they easily become victim of identity breach. To detect malicious users or fake profiles different techniques have been proposed like our approach which is based on the use of social honeypots to discover malicious profiles in it. Inspired by security researchers who used honeypots to observe and analyze malicious activity in the networks, this method uses social honeypots to trap malicious users. The two key elements of the approach are: (1) The deployment of social honeypots for harvesting information of malicious profiles. (2) Analysis of the characteristics of these malicious profiles and those of deployed honeypots for creating classifiers that allow to filter the existing profiles and monitor the new profiles.
Quantifier Elimination for Reasoning in Economics
Venue: arXiv cs.SC 2018
Year: 2018

We consider the use of Quantifier Elimination (QE) technology for automated reasoning in economics. QE dates back to Tarski's work in the 1940s with software to perform it dating to the 1970s. There is a great body of work considering its application in science and engineering but we show here how it can also find application in the social sciences. We explain how many suggested theorems in economics could either be proven, or even have their hypotheses shown to be inconsistent, automatically; and describe the application of this in both economics education and research. We describe a bank of QE examples gathered from economics literature and note the structure of these are, on average, quite different to those occurring in the computer algebra literature. This leads us to suggest a new incremental QE approach based on result memorization of commonly occurring generic QE results.
Adaptive pooling operators for weakly labeled sound event detection
Venue: arXiv cs.SD 2018
Year: 2018

Sound event detection (SED) methods are tasked with labeling segments of audio recordings by the presence of active sound sources. SED is typically posed as a supervised machine learning problem, requiring strong annotations for the presence or absence of each sound source at every time instant within the recording. However, strong annotations of this type are both labor- and cost-intensive for human annotators to produce, which limits the practical scalability of SED methods. In this work, we treat SED as a multiple instance learning (MIL) problem, where training labels are static over a short excerpt, indicating the presence or absence of sound sources but not their temporal locality. The models, however, must still produce temporally dynamic predictions, which must be aggregated (pooled) when comparing against static labels during training. To facilitate this aggregation, we develop a family of adaptive pooling operators---referred to as auto-pool---which smoothly interpolate between common pooling operators, such as min-, max-, or average-pooling, and automatically adapt to the characteristics of the sound sources in question. We evaluate the proposed pooling operators on three datasets, and demonstrate that in each case, the proposed methods outperform non-adaptive pooling operators for static prediction, and nearly match the performance of models trained with strong, dynamic annotations. The proposed method is evaluated in conjunction with convolutional neural networks, but can be readily applied to any differentiable model for time-series label prediction.
A General Analytical Approximation to Impulse Response of 3-D Microfluidic Channels in Molecular Communication
Venue: arXiv cs.ET 2018
Year: 2018

In this paper, the impulse response for a 3-D microfluidic channel in the presence of Poiseuille flow is obtained by solving the diffusion equation in radial coordinates. Using the radial distribution, the axial distribution is then approximated accordingly. Since Poiseuille flow velocity changes with radial position, molecules have different axial properties for different radial distributions. We, therefore, present a piecewise function for the axial distribution of the molecules in the channel considering this radial distribution. Finally, we lay evidence for our theoretical derivations for impulse response of the microfluidic channel and radial distribution of molecules through comparing them using various Monte Carlo simulations.
Machine Learning pipeline for discovering neuroimaging-based biomarkers in neurology and psychiatry
Venue: arXiv cs.CV 2018
Year: 2018

We consider a problem of diagnostic pattern recognition/classification from neuroimaging data. We propose a common data analysis pipeline for neuroimaging-based diagnostic classification problems using various ML algorithms and processing toolboxes for brain imaging. We illustrate the pipeline application by discovering new biomarkers for diagnostics of epilepsy and depression based on clinical and MRI/fMRI data for patients and healthy volunteers.
fMRI: preprocessing, classification and pattern recognition
Venue: arXiv cs.CV 2018
Year: 2018

As machine learning continues to gain momentum in the neuroscience community, we witness the emergence of novel applications such as diagnostics, characterization, and treatment outcome prediction for psychiatric and neurological disorders, for instance, epilepsy and depression. Systematic research into these mental disorders increasingly involves drawing clinical conclusions on the basis of data-driven approaches; to this end, structural and functional neuroimaging serve as key source modalities. Identification of informative neuroimaging markers requires establishing a comprehensive preparation pipeline for data which may be severely corrupted by artifactual signal fluctuations. In this work, we review a large body of literature to provide ample evidence for the advantages of pattern recognition approaches in clinical applications, overview advanced graph-based pattern recognition approaches, and propose a noise-aware neuroimaging data processing pipeline. To demonstrate the effectiveness of our approach, we provide results from a pilot study, which show a significant improvement in classification accuracy, indicating a promising research direction.
Beam Training and Data Transmission Optimization in Millimeter-Wave Vehicular Networks
Venue: arXiv cs.IT 2018
Year: 2018

Future vehicular communication networks call for new solutions to support their capacity demands, by leveraging the potential of the millimeter-wave (mm-wave) spectrum. Mobility, in particular, poses severe challenges in their design, and as such shall be accounted for. A key question in mm-wave vehicular networks is how to optimize the trade-off between directive Data Transmission (DT) and directional Beam Training (BT), which enables it. In this paper, learning tools are investigated to optimize this trade-off. In the proposed scenario, a Base Station (BS) uses BT to establish a mm-wave directive link towards a Mobile User (MU) moving along a road. To control the BT/DT trade-off, a Partially Observable (PO) Markov Decision Process (MDP) is formulated, where the system state corresponds to the position of the MU within the road link. The goal is to maximize the number of bits delivered by the BS to the MU over the communication session, under a power constraint. The resulting optimal policies reveal that adaptive BT/DT procedures significantly outperform common-sense heuristic schemes, and that specific mobility features, such as user position estimates, can be effectively used to enhance the overall system performance and optimize the available system resources.
The Capacity of Private Information Retrieval with Eavesdroppers
Venue: arXiv cs.IT 2018
Year: 2018

We consider the problem of private information retrieval (PIR) with colluding servers and eavesdroppers (abbreviated as ETPIR). The ETPIR problem is comprised of $K$ messages, $N$ servers where each server stores all $K$ messages, a user who wants to retrieve one of the $K$ messages without revealing the desired message index to any set of $T$ colluding servers, and an eavesdropper who can listen to the queries and answers of any $E$ servers but is prevented from learning any information about the messages. The information theoretic capacity of ETPIR is defined to be the maximum number of desired message symbols retrieved privately per information symbol downloaded. We show that the capacity of ETPIR is $C = \left( 1- \frac{E}{N} \right) \left(1 + \frac{T-E}{N-E} + \cdots + \left( \frac{T-E}{N-E} \right)^{K-1} \right)^{-1}$ when $E < T$, and $C = \left( 1 - \frac{E}{N} \right)$ when $E \geq T$. To achieve the capacity, the servers need to share a common random variable (independent of the messages), and its size must be at least $\frac{E}{N} \cdot \frac{1}{C}$ symbols per message symbol. Otherwise, with less amount of shared common randomness, ETPIR is not feasible and the capacity reduces to zero. An interesting observation is that the ETPIR capacity expression takes different forms in two regimes. When $E < T$, the capacity equals the inverse of a sum of a geometric series with $K$ terms and decreases with $K$; this form is typical for capacity expressions of PIR. When $E \geq T$, the capacity does not depend on $K$, a typical form for capacity expressions of SPIR (symmetric PIR, which further requires data-privacy, {\it i.e.,} the user learns no information about other undesired messages); the capacity does not depend on $T$ either. In addition, the ETPIR capacity result includes multiple previous PIR and SPIR capacity results as special cases.
Latent Fingerprint Recognition: Role of Texture Template
Venue: arXiv cs.CV 2018
Year: 2018

We propose a texture template approach, consisting of a set of virtual minutiae, to improve the overall latent fingerprint recognition accuracy. To compensate for the lack of sufficient number of minutiae in poor quality latent prints, we generate a set of virtual minutiae. However, due to a large number of these regularly placed virtual minutiae, texture based template matching has a large computational requirement compared to matching true minutiae templates. To improve both the accuracy and efficiency of the texture template matching, we investigate: i) both original and enhanced fingerprint patches for training convolutional neural networks (ConvNets) to improve the distinctiveness of descriptors associated with each virtual minutiae, ii) smaller patches around virtual minutiae and a fast ConvNet architecture to speed up descriptor extraction, iii) reduce the descriptor length, iv) a modified hierarchical graph matching strategy to improve the matching speed, and v) extraction of multiple texture templates to boost the performance. Experiments on NIST SD27 latent database show that the above strategies can improve the matching speed from 11 ms (24 threads) per comparison (between a latent and a reference print) to only 7.7 ms (single thread) per comparison while improving the rank-1 accuracy by 8.9% against 10K gallery.
History-Preserving Bisimulations on Reversible Calculus of Communicating Systems
Venue: arXiv cs.LO 2018
Year: 2018

History-and hereditary history-preserving bisimulation (HPB and HHPB) are equivalences relations for denotational models of concurrency. Finding their counterpart in process algebras is an open problem, with some partial successes: there exists in calculus of communicating systems (CCS) an equivalence based on causal trees that corresponds to HPB. In Reversible CSS (RCCS), there is a bisimulation that corresponds to HHPB, but it considers only processes without auto-concurrency. We propose equivalences on CCS with auto-concurrency that correspond to HPB and HHPB, and their so-called "weak" variants. The equivalences exploit not only reversibility but also the memory mechanism of RCCS.
An Element Sensitive Saliency Model with Position Prior Learning for Web Pages
Venue: arXiv cs.CV 2018
Year: 2018

Understanding human visual attention is important for multimedia applications. Many studies have attempted to learn from eye-tracking data and build computational saliency prediction models. However, limited efforts have been devoted to saliency prediction for Web pages, which are characterized by more diverse content elements and spatial layouts. In this paper, we propose a novel end-to-end deep generative saliency model for Web pages. To capture position biases introduced by page layouts, a Position Prior Learning sub-network is proposed, which models position biases as multivariate Gaussian distribution using variational auto-encoder. To model different elements of a Web page, a Multi Discriminative Region Detection (MDRD) branch and a Text Region Detection(TRD) branch are introduced, which target to extract discriminative localizations and "prominent" text regions likely to correspond to human attention, respectively. We validate the proposed model with FiWI, a public Web-page dataset, and shows that the proposed model outperforms the state-of-art models for Web-page saliency prediction.
SaC2Vec: Information Network Representation with Structure and Content
Venue: arXiv cs.SI 2018
Year: 2018

Network representation learning (also known as information network embedding) has been the central piece of research in social and information network analysis for the last couple of years. An information network can be viewed as a linked structure of a set of entities. A set of linked web pages and documents, a set of users in a social network are common examples of information network. Network embedding learns low dimensional representations of the nodes, which can further be used for downstream network mining applications such as community detection or node clustering. Information network representation techniques traditionally use only the link structure of the network. But in real world networks, nodes come with additional content such as textual descriptions or associated images. This content is semantically correlated with the network structure and hence using the content along with the topological structure of the network can facilitate the overall network representation. In this paper, we propose Sac2Vec, a network representation technique that exploits both the structure and content. We convert the network into a multi-layered graph and use random walk and language modeling technique to generate the embedding of the nodes. Our approach is simple and computationally fast, yet able to use the content as a complement to structure and vice-versa. We also generalize the approach for networks having multiple types of content in each node. Experimental evaluations on four real world publicly available datasets show the merit of our approach compared to state-of-the-art algorithms in the domain.
Event Forecasting with Pattern Markov Chains
Venue: arXiv cs.DB 2018
Year: 2018

We present a system for online probabilistic event forecasting. We assume that a user is interested in detecting and forecasting event patterns, given in the form of regular expressions. Our system can consume streams of events and forecast when the pattern is expected to be fully matched. As more events are consumed, the system revises its forecasts to reflect possible changes in the state of the pattern. The framework of Pattern Markov Chains is used in order to learn a probabilistic model for the pattern, with which forecasts with guaranteed precision may be produced, in the form of intervals within which a full match is expected. Experimental results from real-world datasets are shown and the quality of the produced forecasts is explored, using both precision scores and two other metrics: spread, which refers to the "focusing resolution" of a forecast (interval length), and distance, which captures how early a forecast is reported.