OpenRaiser/Intern-Atlas huggingface dataset:
Interestingness a Unifying Paradigm Bipolar Function Composition
Venue: arXiv cs.IR 2014
Year: 2014

Interestingness is an important criterion by which we judge knowledge discovery. But, interestingness has escaped all attempts to capture its intuitive meaning into a concise and comprehensive form. A unifying paradigm is formulated by function composition. We claim that composition is bipolar, i.e. composition of exactly two functions, whose two semantic poles are relevance and unexpectedness. The paradigm generality is demonstrated by case studies of new interestingness functions, examples of known functions that fit the framework, and counter-examples for which the paradigm points out to the lacking pole.
Efficient Algorithms and Error Analysis for the Modified Nystrom Method
Venue: arXiv cs.LG 2014
Year: 2014

Many kernel methods suffer from high time and space complexities and are thus prohibitive in big-data applications. To tackle the computational challenge, the Nyström method has been extensively used to reduce time and space complexities by sacrificing some accuracy. The Nyström method speedups computation by constructing an approximation of the kernel matrix using only a few columns of the matrix. Recently, a variant of the Nyström method called the modified Nyström method has demonstrated significant improvement over the standard Nyström method in approximation accuracy, both theoretically and empirically. In this paper, we propose two algorithms that make the modified Nyström method practical. First, we devise a simple column selection algorithm with a provable error bound. Our algorithm is more efficient and easier to implement than and nearly as accurate as the state-of-the-art algorithm. Second, with the selected columns at hand, we propose an algorithm that computes the approximation in lower time complexity than the approach in the previous work. Furthermore, we prove that the modified Nyström method is exact under certain conditions, and we establish a lower error bound for the modified Nyström method.
Modal Independence Logic
Venue: arXiv cs.LO 2014
Year: 2014

This paper introduces modal independence logic MIL, a modal logic that can explicitly talk about independence among propositional variables. Formulas of MIL are not evaluated in worlds but in sets of worlds, so called teams. In this vein, MIL can be seen as a variant of Väänänen's modal dependence logic MDL. We show that MIL embeds MDL and is strictly more expressive. However, on singleton teams, MIL is shown to be not more expressive than usual modal logic, but MIL is exponentially more succinct. Making use of a new form of bisimulation, we extend these expressivity results to modal logics extended by various generalized dependence atoms. We demonstrate the expressive power of MIL by giving a specification of the anonymity requirement of the dining cryptographers protocol in MIL. We also study complexity issues of MIL and show that, though it is more expressive, its satisfiability and model checking problem have the same complexity as for MDL.
A Recursive Method for Enumeration of Costas Arrays
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we propose a recursive method for finding Costas arrays that relies on a particular formation of Costas arrays from similar patterns of smaller size. By using such an idea, the proposed algorithm is able to dramatically reduce the computational burden (when compared to the exhaustive search), and at the same time, still can find all possible Costas arrays of given size. Similar to exhaustive search, the proposed method can be conveniently implemented in parallel computing. The efficiency of the method is discussed based on theoretical and numerical results.
Household Electricity Demand Forecasting -- Benchmarking State-of-the-Art Methods
Venue: arXiv cs.LG 2014
Year: 2014

The increasing use of renewable energy sources with variable output, such as solar photovoltaic and wind power generation, calls for Smart Grids that effectively manage flexible loads and energy storage. The ability to forecast consumption at different locations in distribution systems will be a key capability of Smart Grids. The goal of this paper is to benchmark state-of-the-art methods for forecasting electricity demand on the household level across different granularities and time scales in an explorative way, thereby revealing potential shortcomings and find promising directions for future research in this area. We apply a number of forecasting methods including ARIMA, neural networks, and exponential smoothening using several strategies for training data selection, in particular day type and sliding window based strategies. We consider forecasting horizons ranging between 15 minutes and 24 hours. Our evaluation is based on two data sets containing the power usage of individual appliances at second time granularity collected over the course of several months. The results indicate that forecasting accuracy varies significantly depending on the choice of forecasting methods/strategy and the parameter configuration. Measured by the Mean Absolute Percentage Error (MAPE), the considered state-of-the-art forecasting methods rarely beat corresponding persistence forecasts. Overall, we observed MAPEs in the range between 5 and >100%. The average MAPE for the first data set was ~30%, while it was ~85% for the other data set. These results show big room for improvement. Based on the identified trends and experiences from our experiments, we contribute a detailed discussion of promising future research.
Sparse Model Uncertainties in Compressed Sensing with Application to Convolutions and Sporadic Communication
Venue: arXiv cs.IT 2014
Year: 2014

The success of the compressed sensing paradigm has shown that a substantial reduction in sampling and storage complexity can be achieved in certain linear and non-adaptive estimation problems. It is therefore an advisable strategy for noncoherent information retrieval in, for example, sporadic blind and semi-blind communication and sampling problems. But, the conventional model is not practical here since the compressible signals have to be estimated from samples taken solely on the output of an un-calibrated system which is unknown during measurement but often compressible. Conventionally, one has either to operate at suboptimal sampling rates or the recovery performance substantially suffers from the dominance of model mismatch. In this work we discuss such type of estimation problems and we focus on bilinear inverse problems. We link this problem to the recovery of low-rank and sparse matrices and establish stable low-dimensional embeddings of the uncalibrated receive signals whereby addressing also efficient communication-oriented methods like universal random demodulation. Exemplary, we investigate in more detail sparse convolutions serving as a basic communication channel model. In using some recent results from additive combinatorics we show that such type of signals can be efficiently low-rate sampled by semi-blind methods. Finally, we present a further application of these results in the field of phase retrieval from intensity Fourier measurements.
Followers Are Not Enough: A Question-Oriented Approach to Community Detection in Online Social Networks
Venue: arXiv cs.SI 2014
Year: 2014

Community detection in online social networks is typically based on the analysis of the explicit connections between users, such as "friends" on Facebook and "followers" on Twitter. But online users often have hundreds or even thousands of such connections, and many of these connections do not correspond to real friendships or more generally to accounts that users interact with. We claim that community detection in online social networks should be question-oriented and rely on additional information beyond the simple structure of the network. The concept of 'community' is very general, and different questions such as "whom do we interact with?" and "with whom do we share similar interests?" can lead to the discovery of different social groups. In this paper we focus on three types of communities beyond structural communities: activity-based, topic-based, and interaction-based. We analyze a Twitter dataset using three different weightings of the structural network meant to highlight these three community types, and then infer the communities associated with these weightings. We show that the communities obtained in the three weighted cases are highly different from each other, and from the communities obtained by considering only the unweighted structural network. Our results confirm that asking a precise question is an unavoidable first step in community detection in online social networks, and that different questions can lead to different insights about the network under study.
Active Deformable Part Models
Venue: arXiv cs.CV 2014
Year: 2014

This paper presents an active approach for part-based object detection, which optimizes the order of part filter evaluations and the time at which to stop and make a prediction. Statistics, describing the part responses, are learned from training data and are used to formalize the part scheduling problem as an offline optimization. Dynamic programming is applied to obtain a policy, which balances the number of part evaluations with the classification accuracy. During inference, the policy is used as a look-up table to choose the part order and the stopping time based on the observed filter responses. The method is faster than cascade detection with deformable part models (which does not optimize the part order) with negligible loss in accuracy when evaluated on the PASCAL VOC 2007 and 2010 datasets.
Inter-rater reliability and convergent validity of F1000Prime peer review
Venue: arXiv cs.DL 2014
Year: 2014

Peer review is the backbone of modern science. F1000Prime is a post-publication peer review system of the biomedical literature (papers from medical and biological journals). This study is concerned with the inter-rater reliability and convergent validity of the peer recommendations formulated in the F1000Prime peer review system. The study is based on around 100,000 papers with recommendations from Faculty members. Even if intersubjectivity plays a fundamental role in science, the analyses of the reliability of the F1000Prime peer review system show a rather low level of agreement between Faculty members. This result is in agreement with most other studies which have been published on the journal peer review system. Logistic regression models are used to investigate the convergent validity of the F1000Prime peer review system. As the results show, the proportion of highly cited papers among those selected by the Faculty members is significantly higher than expected. In addition, better recommendation scores are also connected with better performance of the papers.
Partition Information and its Transmission over Boolean Multi-Access Channels
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we propose a novel partition reservation system to study the partition information and its transmission over a noise-free Boolean multi-access channel. The objective of transmission is not message restoration, but to partition active users into distinct groups so that they can, subsequently, transmit their messages without collision. We first calculate (by mutual information) the amount of information needed for the partitioning without channel effects, and then propose two different coding schemes to obtain achievable transmission rates over the channel. The first one is the brute force method, where the codebook design is based on centralized source coding; the second method uses random coding where the codebook is generated randomly and optimal Bayesian decoding is employed to reconstruct the partition. Both methods shed light on the internal structure of the partition problem. A novel hypergraph formulation is proposed for the random coding scheme, which intuitively describes the information in terms of a strong coloring of a hypergraph induced by a sequence of channel operations and interactions between active users. An extended Fibonacci structure is found for a simple, but non-trivial, case with two active users. A comparison between these methods and group testing is conducted to demonstrate the uniqueness of our problem.
Theory and Application of Shapelets to the Analysis of Surface Self-assembly Imaging
Venue: arXiv cs.CV 2014
Year: 2014

A method for quantitative analysis of local pattern strength and defects in surface self-assembly imaging is presented and applied to images of stripe and hexagonal ordered domains. The presented method uses "shapelet" functions which were originally developed for quantitative analysis of images of galaxies ($\propto 10^{20}\mathrm{m}$). In this work, they are used instead to quantify the presence of translational order in surface self-assembled films ($\propto 10^{-9}\mathrm{m}$) through reformulation into "steerable" filters. The resulting method is both computationally efficient (with respect to the number of filter evaluations), robust to variation in pattern feature shape, and, unlike previous approaches, is applicable to a wide variety of pattern types. An application of the method is presented which uses a nearest-neighbour analysis to distinguish between uniform (defect-free) and non-uniform (strained, defect-containing) regions within imaged self-assembled domains, both with striped and hexagonal patterns.
Adaptive $h$-refinement for reduced-order models
Venue: arXiv cs.NA 2014
Year: 2014

This work presents a method to adaptively refine reduced-order models \emph{a posteriori} without requiring additional full-order-model solves. The technique is analogous to mesh-adaptive $h$-refinement: it enriches the reduced-basis space online by `splitting' a given basis vector into several vectors with disjoint support. The splitting scheme is defined by a tree structure constructed offline via recursive $k$-means clustering of the state variables using snapshot data. The method identifies the vectors to split online using a dual-weighted-residual approach that aims to reduce error in an output quantity of interest. The resulting method generates a hierarchy of subspaces online without requiring large-scale operations or full-order-model solves. Further, it enables the reduced-order model to satisfy \emph{any prescribed error tolerance} regardless of its original fidelity, as a completely refined reduced-order model is mathematically equivalent to the original full-order model. Experiments on a parameterized inviscid Burgers equation highlight the ability of the method to capture phenomena (e.g., moving shocks) not contained in the span of the original reduced basis.
A Comparative Study of Modern Inference Techniques for Structured Discrete Energy Minimization Problems
Venue: arXiv cs.CV 2014
Year: 2014

Szeliski et al. published an influential study in 2006 on energy minimization methods for Markov Random Fields (MRF). This study provided valuable insights in choosing the best optimization technique for certain classes of problems. While these insights remain generally useful today, the phenomenal success of random field models means that the kinds of inference problems that have to be solved changed significantly. Specifically, the models today often include higher order interactions, flexible connectivity structures, large la\-bel-spaces of different cardinalities, or learned energy tables. To reflect these changes, we provide a modernized and enlarged study. We present an empirical comparison of 32 state-of-the-art optimization techniques on a corpus of 2,453 energy minimization instances from diverse applications in computer vision. To ensure reproducibility, we evaluate all methods in the OpenGM 2 framework and report extensive results regarding runtime and solution quality. Key insights from our study agree with the results of Szeliski et al. for the types of models they studied. However, on new and challenging types of models our findings disagree and suggest that polyhedral methods and integer programming solvers are competitive in terms of runtime and solution quality over a large range of model types.
Towards a Fair Allocation of Rewards in Multi-Level Marketing
Venue: arXiv cs.GT 2014
Year: 2014

An increasing number of businesses and organisations rely on existing users for finding new users or spreading a message. One of the widely used "refer-a-friend" mechanisms offers an equal reward to both the referrer and the invitee. This mechanism provides incentives for direct referrals and is fair to the invitee. On the other hand, multi-level marketing and recent social mobilisation experiments focus on mechanisms that incentivise both direct and indirect referrals. Such mechanisms share the reward for inviting a new member among the ancestors, usually in geometrically decreasing shares. A new member receives nothing at the time of joining. We study fairness in multi-level marketing mechanisms. We show how characteristic function games can be used to model referral marketing, show how the canonical fairness concept of the Shapley value can be applied to this setting, and establish the complexity of finding the Shapley value in each class, and provide a comparison of the Shapley value-based mechanism to existing referral mechanisms.
On Affine Logic and Łukasiewicz Logic
Venue: arXiv cs.LO 2014
Year: 2014

The multi-valued logic of Łukasiewicz is a substructural logic that has been widely studied and has many interesting properties. It is classical, in the sense that it admits the axiom schema of double negation, [DNE]. However, our understanding of Łukasiewicz logic can be improved by separating its classical and intuitionistic aspects. The intuitionistic aspect of Łukasiewicz logic is captured in an axiom schema, [CWC], which asserts the commutativity of a weak form of conjunction. This is equivalent to a very restricted form of contraction. We show how Łukasiewicz Logic can be viewed both as an extension of classical affine logic with [CWC], or as an extension of what we call \emph{intuitionistic} Łukasiewicz logic with [DNE], intuitionistic Łukasiewicz logic being the extension of intuitionistic affine logic by the schema [CWC]. At first glance, intuitionistic affine logic seems very weak, but, in fact, [CWC] is surprisingly powerful, implying results such as intuitionistic analogues of De Morgan's laws. However the proofs can be very intricate. We present these results using derived connectives to clarify and motivate the proofs and give several applications. We give an analysis of the applicability to these logics of the well-known methods that use negation to translate classical logic into intuitionistic logic. The usual proofs of correctness for these translations make much use of contraction. Nonetheless, we show that all the usual negative translations are already correct for intuitionistic Łukasiewicz logic, where only the limited amount of contraction given by [CWC] is allowed. This is in contrast with affine logic for which we show, by appeal to results on semantics proved in a companion paper, that both the Gentzen and the Glivenko translations fail.
Nanowire Volatile RAM as an Alternative to SRAM
Venue: arXiv cs.ET 2014
Year: 2014

Maintaining benefits of CMOS technology scaling is becoming challenging due to increased manufacturing complexities and unwanted passive power dissipations. This is particularly challenging in SRAM, where manufacturing precision and leakage power control are critical issues. To alleviate some of these challenges a novel non-volatile memory alternative to SRAM was proposed called nanowire volatile RAM (NWRAM). Due to NWRAMs regular grid based layout and innovative circuit style, manufacturing complexity is reduced and at the same time considerable benefits are attained in terms of performance and leakage power reduction. In this paper, we elaborate more on NWRAM circuit aspects and manufacturability, and quantify benefits at 16nm technology node through simulation against state-of-the-art 6T-SRAM and gridded 8T-SRAM designs. Our results show the 10T-NWRAM to be 2x faster and 35x better in terms of leakage when compared to high performance gridded 8T-SRAM design.
Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties
Venue: arXiv cs.DM 2014
Year: 2014

The primary problem in property testing is to decide whether a given function satisfies a certain property, or is far from any function satisfying it. This crucially requires a notion of distance between functions. The most prevalent notion is the Hamming distance over the {\em uniform} distribution on the domain. This restriction to uniformity is more a matter of convenience than of necessity, and it is important to investigate distances induced by more general distributions. In this paper, we make significant strides in this direction. We give simple and optimal testers for {\em bounded derivative properties} over {\em arbitrary product distributions}. Bounded derivative properties include fundamental properties such as monotonicity and Lipschitz continuity. Our results subsume almost all known results (upper and lower bounds) on monotonicity and Lipschitz testing. We prove an intimate connection between bounded derivative property testing and binary search trees (BSTs). We exhibit a tester whose query complexity is the sum of expected depths of optimal BSTs for each marginal. Furthermore, we show this sum-of-depths is also a lower bound. A fundamental technical contribution of this work is an {\em optimal dimension reduction theorem} for all bounded derivative properties, which relates the distance of a function from the property to the distance of restrictions of the function to random lines. Such a theorem has been elusive even for monotonicity for the past 15 years, and our theorem is an exponential improvement to the previous best known result.
Randomized Broadcast in Radio Networks with Collision Detection
Venue: arXiv cs.DS 2014
Year: 2014

We present a randomized distributed algorithm that in radio networks with collision detection broadcasts a single message in $O(D + \log^6 n)$ rounds, with high probability. This time complexity is most interesting because of its optimal additive dependence on the network diameter $D$. It improves over the currently best known $O(D\log\frac{n}{D}\,+\,\log^2 n)$ algorithms, due to Czumaj and Rytter [FOCS 2003], and Kowalski and Pelc [PODC 2003]. These algorithms where designed for the model without collision detection and are optimal in that model. However, as explicitly stated by Peleg in his 2007 survey on broadcast in radio networks, it had remained an open question whether the bound can be improved with collision detection. We also study distributed algorithms for broadcasting $k$ messages from a single source to all nodes. This problem is a natural and important generalization of the single-message broadcast problem, but is in fact considerably more challenging and less understood. We show the following results: If the network topology is known to all nodes, then a $k$-message broadcast can be performed in $O(D + k\log n + \log^2 n)$ rounds, with high probability. If the topology is not known, but collision detection is available, then a $k$-message broadcast can be performed in $O(D + k\log n + \log^6 n)$ rounds, with high probability. The first bound is optimal and the second is optimal modulo the additive $O(\log^6 n)$ term.