OpenRaiser/Intern-Atlas huggingface dataset:
Survey of Publicly Available State Health Databases
Venue: arXiv cs.CY 2013
Year: 2013

We surveyed every state and the District of Columbia to see what patient specific information states release on hospital visits and how much potentially identifiable information is released in those records. Thirty-three states release hospital discharge data in some form, with varying levels of demographic information and hospital stay details such as hospital name, admission and discharge dates, diagnoses, doctors who attended to the patient, payer, and cost of the stay. We compared the level of demographic and other data to federal standards set by the Health Information Portability and Accountability Act or HIPAA), which states do not have to adhere to for this type of data. We found that states varied widely in whether their data was HIPAA equivalent; while 13 were equivalent (or stricter) with demographic fields only 3 of the 33 states that released data did so in a form that was HIPAA equivalent across all fields.
Effects of Publications in Proceedings on the Measure of the Core Size of Coauthors
Venue: arXiv cs.DL 2013
Year: 2013

Coauthors (CA) of a "lead investigator" (LI) can receive a rank (r) according to their "importance" in having published joint publications with the LI. It is commonly accepted, without any proof, that publications in peer review journals and e.g. conference proceedings do not have the same "value" in a CV. Same for papers contributed to encyclopedia and book chapters. It is here examined whether the relationship between the number (J) of publications of some scientist with her/his coauthors, ranked according to their decreasing importance, i.e. $ J \propto 1/r^α $, as found by Ausloos, still holds if the overall publication list is broken into such specific types of publications. Several authors, with different careers, but mainly having worked in the field of statistical mechanics, are studied here to sort out answers to the questions. The exponent $α$ turns out to be weakly scientist dependent, only if the maximum value of J and r is large and is $\sim +1$ then. The $m_A$ core value, i.e. the core number of CAs, for proceedings only is about half of the total one, i.e. when all publications are counted. Contributions to the numerical values from both encyclopedia and book chapters are marginal. The role of a time span on $m_A$ is also examined in two cases in relation to career activity considerations. It can considered that the findings serve as a contrasting point of view on how to quantify an individual (publication) career as recently done by Petersen et al., here emphasizing the collaboration size and evolution, rather than a citation count, moreover specifying the type of publication. Through the various $m_A$'s one can distinguish different behavior patterns of a scientist publication with CAs.
Copula Mixed-Membership Stochastic Blockmodel for Intra-Subgroup Correlations
Venue: arXiv cs.LG 2013
Year: 2013

The \emph{Mixed-Membership Stochastic Blockmodel (MMSB)} is a popular framework for modeling social network relationships. It can fully exploit each individual node's participation (or membership) in a social structure. Despite its powerful representations, this model makes an assumption that the distributions of relational membership indicators between two nodes are independent. Under many social network settings, however, it is possible that certain known subgroups of people may have high or low correlations in terms of their membership categories towards each other, and such prior information should be incorporated into the model. To this end, we introduce a \emph{Copula Mixed-Membership Stochastic Blockmodel (cMMSB)} where an individual Copula function is employed to jointly model the membership pairs of those nodes within the subgroup of interest. The model enables the use of various Copula functions to suit the scenario, while maintaining the membership's marginal distribution, as needed, for modeling membership indicators with other nodes outside of the subgroup of interest. We describe the proposed model and its inference algorithm in detail for both the finite and infinite cases. In the experiment section, we compare our algorithms with other popular models in terms of link prediction, using both synthetic and real world data.
On the Impact of Relay-side Channel State Information on Opportunistic Relaying
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, outage performance of network topology-aware distributed opportunistic relay selection strategies is studied with focus on the impact of different levels of channel state information (CSI) available at relays. Specifically, two scenarios with (a) exact instantaneous and (b) only statistical CSI are compared with explicit account for both small-scale Rayleigh fading and path loss due to random inter-node distances. Analytical results, matching closely to simulations, suggest that although similar diversity order can be achieved in both cases, the lack of precise CSI to support relay selection translates into significant increase in the power required to achieve the same level of QoS. In addition, when only statistical CSI is available, achieving the same diversity order is associated with a clear performance degradation at low SNR due to splitting of system resources between multiple relays.
Recurrent Convolutional Neural Networks for Scene Parsing
Venue: arXiv cs.CV 2013
Year: 2013

Scene parsing is a technique that consist on giving a label to all pixels in an image according to the class they belong to. To ensure a good visual coherence and a high class accuracy, it is essential for a scene parser to capture image long range dependencies. In a feed-forward architecture, this can be simply achieved by considering a sufficiently large input context patch, around each pixel to be labeled. We propose an approach consisting of a recurrent convolutional neural network which allows us to consider a large input context, while limiting the capacity of the model. Contrary to most standard approaches, our method does not rely on any segmentation methods, nor any task-specific features. The system is trained in an end-to-end manner over raw pixels, and models complex spatial dependencies with low inference cost. As the context size increases with the built-in recurrence, the system identifies and corrects its own errors. Our approach yields state-of-the-art performance on both the Stanford Background Dataset and the SIFT Flow Dataset, while remaining very fast at test time.
Mapping the File Systems Genome: rationales, technique, results and applications
Venue: arXiv cs.CR 2013
Year: 2013

This paper provides evidence of a feature of Hard-Disk Drives (HDDs), that we call File System Genome. Such a feature is originated by the areas where (on the HDD) the file blocks are placed by the operating system during the installation procedure. It appears from our study that the File System Genome is a distinctive and unique feature of each indi- vidual HDD. In particular, our extensive set of experiments shows that the installation of the same operating system on two identical hardware configurations generates two different File System Genomes. Further, the application of sound information theory tools, such as min entropy, show that the differences between two File System Genome are considerably relevant. The results provided in this paper constitute the scientific basis for a number of applications in various fields of information technology, such as forensic identification and security. Finally, this work also paves the way for the application of the highlighted technique to other classes of mass-storage devices (e.g. SSDs, Flash memories).
Slimy hairs: Hair sensors made with slime mould
Venue: arXiv cs.ET 2013
Year: 2013

Slime mould Physarum polycephalum is a large single cell visible by unaided eye. We design a slime mould implementation of a tactile hair, where the slime mould responds to repeated deflection of hair by an immediate high-amplitude spike and a prolonged increase in amplitude and width of its oscillation impulses. We demonstrate that signal-to-noise ratio of the Physarum tactile hair sensor averages near six for the immediate response and two for the prolonged response.
The effect of baroque music on the PassPoints graphical password
Venue: arXiv cs.CR 2013
Year: 2013

Graphical passwords have been demonstrated to be the possible alternatives to traditional alphanumeric passwords. However, they still tend to follow predictable patterns that are easier to attack. The crux of the problem is users' memory limitations. Users are the weakest link in password authentication mechanism. It shows that baroque music has positive effects on human memorizing and learning. We introduce baroque music to the PassPoints graphical password scheme and conduct a laboratory study in this paper. Results shown that there is no statistic difference between the music group and the control group without music in short-term recall experiments, both had high recall success rates. But in long-term recall, the music group performed significantly better. We also found that the music group tended to set significantly more complicated passwords, which are usually more resistant to dictionary and other guess attacks. But compared with the control group, the music group took more time to log in both in short-term and long-term tests. Besides, it appears that background music does not work in terms of hotspots.
3-color Bounded Patterned Self-assembly
Venue: arXiv cs.CC 2013
Year: 2013

Patterned self-assembly tile set synthesis PATS is the problem of finding a minimal tile set which uniquely self-assembles into a given pattern. Czeizler and Popa proved the NP-completeness of PATS and Seki showed that the PATS problem is already NP-complete for patterns with 60 colors. In search for the minimal number of colors such that PATS remains NP-complete, we introduce multiple bound PATS (mbPATS) where we allow bounds for the numbers of tile types of each color. We show that mbPATS is NP-complete for patterns with just three colors and, as a byproduct of this result, we also obtain a novel proof for the NP-completeness of PATS which is more concise than the previous proofs.
Feature Learning by Multidimensional Scaling and its Applications in Object Recognition
Venue: arXiv cs.CV 2013
Year: 2013

We present the MDS feature learning framework, in which multidimensional scaling (MDS) is applied on high-level pairwise image distances to learn fixed-length vector representations of images. The aspects of the images that are captured by the learned features, which we call MDS features, completely depend on what kind of image distance measurement is employed. With properly selected semantics-sensitive image distances, the MDS features provide rich semantic information about the images that is not captured by other feature extraction techniques. In our work, we introduce the iterated Levenberg-Marquardt algorithm for solving MDS, and study the MDS feature learning with IMage Euclidean Distance (IMED) and Spatial Pyramid Matching (SPM) distance. We present experiments on both synthetic data and real images --- the publicly accessible UIUC car image dataset. The MDS features based on SPM distance achieve exceptional performance for the car recognition task.
Matching objects across the textured-smooth continuum
Venue: arXiv cs.CV 2013
Year: 2013

The problem of 3D object recognition is of immense practical importance, with the last decade witnessing a number of breakthroughs in the state of the art. Most of the previous work has focused on the matching of textured objects using local appearance descriptors extracted around salient image points. The recently proposed bag of boundaries method was the first to address directly the problem of matching smooth objects using boundary features. However, no previous work has attempted to achieve a holistic treatment of the problem by jointly using textural and shape features which is what we describe herein. Due to the complementarity of the two modalities, we fuse the corresponding matching scores and learn their relative weighting in a data specific manner by optimizing discriminative performance on synthetically distorted data. For the textural description of an object we adopt a representation in the form of a histogram of SIFT based visual words. Similarly the apparent shape of an object is represented by a histogram of discretized features capturing local shape. On a large public database of a diverse set of objects, the proposed method is shown to outperform significantly both purely textural and purely shape based approaches for matching across viewpoint variation.
EFSMT: A Logical Framework for Cyber-Physical Systems
Venue: arXiv cs.LO 2013
Year: 2013

The design of cyber-physical systems is challenging in that it includes the analysis and synthesis of distributed and embedded real-time systems for controlling, often in a nonlinear way, the environment. We address this challenge with EFSMT, the exists-forall quantified first-order fragment of propositional combinations over constraints (including nonlinear arithmetic), as the logical framework and foundation for analyzing and synthesizing cyber-physical systems. We demonstrate the expressiveness of EFSMT by reducing a number of pivotal verification and synthesis problems to EFSMT. Exemplary problems in this paper include synthesis for robust control via BIBO stability, Lyapunov coefficient finding for nonlinear control systems, distributed priority synthesis for orchestrating system components, and synthesis for hybrid control systems. We are also proposing an algorithm for solving EFSMT problems based on the interplay between two SMT solvers for respectively solving universally and existentially quantified problems. This algorithms builds on commonly used techniques in modern SMT solvers, and generalizes them to quantifier reasoning by counterexample-guided constraint strengthening. The EFSMT solver uses Bernstein polynomials for solving nonlinear arithmetic constraints.
Hyperparameter Optimization and Boosting for Classifying Facial Expressions: How good can a "Null" Model be?
Venue: arXiv cs.CV 2013
Year: 2013

One of the goals of the ICML workshop on representation and learning is to establish benchmark scores for a new data set of labeled facial expressions. This paper presents the performance of a "Null" model consisting of convolutions with random weights, PCA, pooling, normalization, and a linear readout. Our approach focused on hyperparameter optimization rather than novel model components. On the Facial Expression Recognition Challenge held by the Kaggle website, our hyperparameter optimization approach achieved a score of 60% accuracy on the test data. This paper also introduces a new ensemble construction variant that combines hyperparameter optimization with the construction of ensembles. This algorithm constructed an ensemble of four models that scored 65.5% accuracy. These scores rank 12th and 5th respectively among the 56 challenge participants. It is worth noting that our approach was developed prior to the release of the data set, and applied without modification; our strong competition performance suggests that the TPE hyperparameter optimization algorithm and domain expertise encoded in our Null model can generalize to new image classification data sets.
An Information Theoretic Study of Timing Side Channels in Two-user Schedulers
Venue: arXiv cs.IT 2013
Year: 2013

Timing side channels in two-user schedulers are studied. When two users share a scheduler, one user may learn the other user's behavior from patterns of service timings. We measure the information leakage of the resulting timing side channel in schedulers serving a legitimate user and a malicious attacker, using a privacy metric defined as the Shannon equivocation of the user's job density. We show that the commonly used first-come-first-serve (FCFS) scheduler provides no privacy as the attacker is able to to learn the user's job pattern completely. Furthermore, we introduce an scheduling policy, accumulate-and-serve scheduler, which services jobs from the user and attacker in batches after buffering them. The information leakage in this scheduler is mitigated at the price of service delays, and the maximum privacy is achievable when large delays are added.
Exact and fixed-parameter algorithms for metro-line crossing minimization problems
Venue: arXiv cs.DS 2013
Year: 2013

A metro-line crossing minimization problem is to draw multiple lines on an underlying graph that models stations and rail tracks so that the number of crossings of lines becomes minimum. It has several variations by adding restrictions on how lines are drawn. Among those, there is one with a restriction that line terminals have to be drawn at a verge of a station, and it is known to be NP-hard even when underlying graphs are paths. This paper studies the problem in this setting, and propose new exact algorithms. We first show that a problem to decide if lines can be drawn without crossings is solved in polynomial time, and propose a fast exponential algorithm to solve a crossing minimization problem. We then propose a fixed-parameter algorithm with respect to the multiplicity of lines, which implies that the problem is FPT.
Outlying Property Detection with Numerical Attributes
Venue: arXiv cs.LG 2013
Year: 2013

The outlying property detection problem is the problem of discovering the properties distinguishing a given object, known in advance to be an outlier in a database, from the other database objects. In this paper, we analyze the problem within a context where numerical attributes are taken into account, which represents a relevant case left open in the literature. We introduce a measure to quantify the degree the outlierness of an object, which is associated with the relative likelihood of the value, compared to the to the relative likelihood of other objects in the database. As a major contribution, we present an efficient algorithm to compute the outlierness relative to significant subsets of the data. The latter subsets are characterized in a "rule-based" fashion, and hence the basis for the underlying explanation of the outlierness.
A Differential Feedback Scheme Exploiting the Temporal and Spectral Correlation
Venue: arXiv cs.IT 2013
Year: 2013

Channel state information (CSI) provided by limited feedback channel can be utilized to increase the system throughput. However, in multiple input multiple output (MIMO) systems, the signaling overhead realizing this CSI feedback can be quite large, while the capacity of the uplink feedback channel is typically limited. Hence, it is crucial to reduce the amount of feedback bits. Prior work on limited feedback compression commonly adopted the block fading channel model where only temporal or spectral correlation in wireless channel is considered. In this paper, we propose a differential feedback scheme with full use of the temporal and spectral correlations to reduce the feedback load. Then, the minimal differential feedback rate over MIMO doubly selective fading channel is investigated. Finally, the analysis is verified by simulations.
Online Alternating Direction Method (longer version)
Venue: arXiv cs.LG 2013
Year: 2013

Online optimization has emerged as powerful tool in large scale optimization. In this pa- per, we introduce efficient online optimization algorithms based on the alternating direction method (ADM), which can solve online convex optimization under linear constraints where the objective could be non-smooth. We introduce new proof techniques for ADM in the batch setting, which yields a O(1/T) convergence rate for ADM and forms the basis for regret anal- ysis in the online setting. We consider two scenarios in the online setting, based on whether an additional Bregman divergence is needed or not. In both settings, we establish regret bounds for both the objective function as well as constraints violation for general and strongly convex functions. We also consider inexact ADM updates where certain terms are linearized to yield efficient updates and show the stochastic convergence rates. In addition, we briefly discuss that online ADM can be used as projection- free online learning algorithm in some scenarios. Preliminary results are presented to illustrate the performance of the proposed algorithms.
Approximation Algorithms for Movement Repairmen
Venue: arXiv cs.DS 2013
Year: 2013

In the {\em Movement Repairmen (MR)} problem we are given a metric space $(V, d)$ along with a set $R$ of $k$ repairmen $r_1, r_2, ..., r_k$ with their start depots $s_1, s_2, ..., s_k \in V$ and speeds $v_1, v_2, ..., v_k \geq 0$ respectively and a set $C$ of $m$ clients $c_1, c_2, ..., c_m$ having start locations $s'_1, s'_2, ..., s'_m \in V$ and speeds $v'_1, v'_2, ..., v'_m \geq 0$ respectively. If $t$ is the earliest time a client $c_j$ is collocated with any repairman (say, $r_i$) at a node $u$, we say that the client is served by $r_i$ at $u$ and that its latency is $t$. The objective in the (\smr{}) problem is to plan the movements for all repairmen and clients to minimize the sum (average) of the clients latencies. The motivation for this problem comes, for example, from Amazon Locker Delivery \cite{amazon} and USPS gopost \cite{gopost}. We give the first $O(\log n)$-approximation algorithm for the \smr{} problem.
UDC in Action
Venue: arXiv cs.DL 2013
Year: 2013

The UDC (Universal Decimal Classification) is not only a classification language with a long history; it also presents a complex cognitive system worthy of the attention of complexity theory. The elements of the UDC: classes, auxiliaries, and operations are combined into symbolic strings, which in essence represent a complex networks of concepts. This network forms a backbone of ordering of knowledge and at the same time allows expression of different perspectives on various products of human knowledge production. In this paper we look at UDC strings derived from the holdings of libraries. In particular we analyse the subject headings of holdings of the university library in Leuven, and an extraction of UDC numbers from the OCLC WorldCat. Comparing those sets with the Master Reference File, we look into the length of strings, the occurrence of different auxiliary signs, and the resulting connections between UDC classes. We apply methods and representations from complexity theory. Mapping out basic statistics on UDC classes as used in libraries from a point of view of complexity theory bears different benefits. Deploying its structure could serve as an overview and basic information for users among the nature and focus of specific collections. A closer view into combined UDC numbers reveals the complex nature of the UDC as an example for a knowledge ordering system, which deserves future exploration from a complexity theoretical perspective.
TwitterCrowds: Techniques for Exploring Topic and Sentiment in Microblogging Data
Venue: arXiv cs.SI 2013
Year: 2013

Analysts and social scientists in the humanities and industry require techniques to help visualize large quantities of microblogging data. Methods for the automated analysis of large scale social media data (on the order of tens of millions of tweets) are widely available, but few visualization techniques exist to support interactive exploration of the results. In this paper, we present extended descriptions of ThemeCrowds and SentireCrowds, two tag-based visualization techniques for this data. We subsequently introduce a new list equivalent for both of these techniques and present a number of case studies showing them in operation. Finally, we present a formal user study to evaluate the effectiveness of these list interface equivalents when comparing them to ThemeCrowds and SentireCrowds. We find that discovering topics associated with areas of strong positive or negative sentiment is faster when using a list interface. In terms of user preference, multilevel tag clouds were found to be more enjoyable to use. Despite both interfaces being usable for all tested tasks, we have evidence to support that list interfaces can be more efficient for tasks when an appropriate ordering is known beforehand.