OpenRaiser/Intern-Atlas huggingface dataset:
Universal Induction with Varying Sets of Combinators
Venue: arXiv cs.AI 2013
Year: 2013

Universal induction is a crucial issue in AGI. Its practical applicability can be achieved by the choice of the reference machine or representation of algorithms agreed with the environment. This machine should be updatable for solving subsequent tasks more efficiently. We study this problem on an example of combinatory logic as the very simple Turing-complete reference machine, which enables modifying program representations by introducing different sets of primitive combinators. Genetic programming system is used to search for combinator expressions, which are easily decomposed into sub-expressions being recombined in crossover. Our experiments show that low-complexity induction or prediction tasks can be solved by the developed system (much more efficiently than using brute force); useful combinators can be revealed and included into the representation simplifying more difficult tasks. However, optimal sets of combinators depend on the specific task, so the reference machine should be adaptively chosen in coordination with the search engine.
Towards Detection of Bottlenecks in Modular Systems
Venue: arXiv cs.AI 2013
Year: 2013

The paper describes some basic approaches to detection of bottlenecks in composite (modular) systems. The following basic system bottlenecks detection problems are examined: (1) traditional quality management approaches (Pareto chart based method, multicriteria analysis as selection of Pareto-efficient points, and/or multicriteria ranking), (2) selection of critical system elements (critical components/modules, critical component interconnection), (3) selection of interconnected system components as composite system faults (via clique-based fusion), (4) critical elements (e.g., nodes) in networks, and (5) predictive detection of system bottlenecks (detection of system components based on forecasting of their parameters). Here, heuristic solving schemes are used. Numerical examples illustrate the approaches.
Image Inpainting by Kriging Interpolation Technique
Venue: arXiv cs.CV 2013
Year: 2013

Image inpainting is the art of predicting damaged regions of an image. The manual way of image inpainting is a time consuming. Therefore, there must be an automatic digital method for image inpainting that recovers the image from the damaged regions. In this paper, a novel statistical image inpainting algorithm based on Kriging interpolation technique was proposed. Kriging technique automatically fills the damaged region in an image using the information available from its surrounding regions in such away that it uses the spatial correlation structure of points inside the k-by-k block. Kriging has the ability to face the challenge of keeping the structure and texture information as the size of damaged region heighten. Experimental results showed that, Kriging has a high PSNR value when recovering a variety of test images from scratches and text as damaged regions.
Cellular-Based Statistical Model for Mobile Dispersion
Venue: arXiv cs.IT 2013
Year: 2013

While analyzing mobile systems we often approximate the actual coverage surface and assume an ideal cell shape. In a multi-cellular network, because of its tessellating nature, a hexagon is more preferred than a circular geometry. Despite this reality, perhaps due to the inherent simplicity, only a model for circular based random spreading is available. However, if used, this results an unfair terminal distribution for non-circular contours. Therefore, in this paper we specifically derived an unbiased node density model for a hexagon. We then extended the principle and established stochastic ways to handle sectored cells. Next, based on these mathematical findings, we created a generic modeling tool that can support a complex network with varying position, capacity, size, user density, and sectoring capability. Last, simulation was used to verify the theoretical analysis.
Cell-Level Modeling of IEEE 802.11 WLANs
Venue: arXiv cs.NI 2013
Year: 2013

We develop a scalable \textit{cell-level} analytical model for multi-cell infrastructure IEEE 802.11 WLANs under a so-called Pairwise Binary Dependence (PBD) condition. The PBD condition is a geometric property under which the relative locations of the nodes inside a cell do not matter and the network is free of \textit{hidden nodes}. For the cases of saturated nodes and TCP-controlled long-file downloads, we provide accurate predictions of cell throughputs. Similar to Bonald et al (Sigmetrics, 2008), we model a multi-cell WLAN under short-file downloads as "a network of processor-sharing queues with state-dependent service rates." Whereas the state-dependent service rates proposed by Bonald et al are based only on the \textit{number} of contending neighbors, we employ state-dependent service rates that incorporate the the impact of the overall \textit{topology} of the network. We propose an \textit{effective service rate approximation} technique and obtain good approximations for the \textit{mean flow transfer delay} in each cell. For TCP-controlled downloads where the APs transmit a large fraction of time, we show that the throughputs predicted under the PBD condition are very good approximations in two important scenarios where hidden nodes are indeed present and the PBD condition does not strictly hold.
Slime mould tactile sensor
Venue: arXiv cs.ET 2013
Year: 2013

Slime mould P. polycephalum is a single cells visible by unaided eye. The cells shows a wide spectrum of intelligent behaviour. By interpreting the behaviour in terms of computation one can make a slime mould based computing device. The Physarum computers are capable to solve a range of tasks of computational geometry, optimisation and logic. Physarum computers designed so far lack of localised inputs. Commonly used inputs --- illumination and chemo-attractants and -repellents --- usually act on extended domains of the slime mould's body. Aiming to design massive-parallel tactile inputs for slime mould computers we analyse a temporal dynamic of P. polycephalum's electrical response to tactile stimulation. In experimental laboratory studies we discover how the Physarum responds to application and removal of a local mechanical pressure with electrical potential impulses and changes in its electrical potential oscillation patterns.
KERT: Automatic Extraction and Ranking of Topical Keyphrases from Content-Representative Document Titles
Venue: arXiv cs.LG 2013
Year: 2013

We introduce KERT (Keyphrase Extraction and Ranking by Topic), a framework for topical keyphrase generation and ranking. By shifting from the unigram-centric traditional methods of unsupervised keyphrase extraction to a phrase-centric approach, we are able to directly compare and rank phrases of different lengths. We construct a topical keyphrase ranking function which implements the four criteria that represent high quality topical keyphrases (coverage, purity, phraseness, and completeness). The effectiveness of our approach is demonstrated on two collections of content-representative titles in the domains of Computer Science and Physics.
The Fiat-Shamir Transformation in a Quantum World
Venue: arXiv cs.CR 2013
Year: 2013

The Fiat-Shamir transformation is a famous technique to turn identification schemes into signature schemes. The derived scheme is provably secure in the random-oracle model against classical adversaries. Still, the technique has also been suggested to be used in connection with quantum-immune identification schemes, in order to get quantum-immune signature schemes. However, a recent paper by Boneh et al. (Asiacrypt 2011) has raised the issue that results in the random-oracle model may not be immediately applicable to quantum adversaries, because such adversaries should be allowed to query the random oracle in superposition. It has been unclear if the Fiat-Shamir technique is still secure in this quantum oracle model (QROM). Here, we discuss that giving proofs for the Fiat-Shamir transformation in the QROM is presumably hard. We show that there cannot be black-box extractors, as long as the underlying quantum-immune identification scheme is secure against active adversaries and the first message of the prover is independent of its witness. Most schemes are of this type. We then discuss that for some schemes one may be able to resurrect the Fiat-Shamir result in the QROM by modifying the underlying protocol first. We discuss in particular a version of the Lyubashevsky scheme which is provably secure in the QROM.
Iterative Grassmannian Optimization for Robust Image Alignment
Venue: arXiv cs.CV 2013
Year: 2013

Robust high-dimensional data processing has witnessed an exciting development in recent years, as theoretical results have shown that it is possible using convex programming to optimize data fit to a low-rank component plus a sparse outlier component. This problem is also known as Robust PCA, and it has found application in many areas of computer vision. In image and video processing and face recognition, the opportunity to process massive image databases is emerging as people upload photo and video data online in unprecedented volumes. However, data quality and consistency is not controlled in any way, and the massiveness of the data poses a serious computational challenge. In this paper we present t-GRASTA, or "Transformed GRASTA (Grassmannian Robust Adaptive Subspace Tracking Algorithm)". t-GRASTA iteratively performs incremental gradient descent constrained to the Grassmann manifold of subspaces in order to simultaneously estimate a decomposition of a collection of images into a low-rank subspace, a sparse part of occlusions and foreground objects, and a transformation such as rotation or translation of the image. We show that t-GRASTA is 4 $\times$ faster than state-of-the-art algorithms, has half the memory requirement, and can achieve alignment for face images as well as jittered camera surveillance images.
A data-driven analysis to question epidemic models for citation cascades on the blogosphere
Venue: arXiv cs.SI 2013
Year: 2013

Citation cascades in blog networks are often considered as traces of information spreading on this social medium. In this work, we question this point of view using both a structural and semantic analysis of five months activity of the most representative blogs of the french-speaking community.Statistical measures reveal that our dataset shares many features with those that can be found in the literature, suggesting the existence of an identical underlying process. However, a closer analysis of the post content indicates that the popular epidemic-like descriptions of cascades are misleading in this context.A basic model, taking only into account the behavior of bloggers and their restricted social network, accounts for several important statistical features of the data.These arguments support the idea that citations primary goal may not be information spreading on the blogosphere.
Evolutionary Approach for the Containers Bin-Packing Problem
Venue: arXiv cs.NE 2013
Year: 2013

This paper deals with the resolution of combinatorial optimization problems, particularly those concerning the maritime transport scheduling. We are interested in the management platforms in a river port and more specifically in container organisation operations with a view to minimizing the number of container rehandlings. Subsequently, we rmeet customers delivery deadlines and we reduce ship stoppage time In this paper, we propose a genetic algorithm to solve this problem and we present some experiments and results.
Waveform Design for Secure SISO Transmissions and Multicasting
Venue: arXiv cs.CR 2013
Year: 2013

Wireless physical-layer security is an emerging field of research aiming at preventing eavesdropping in an open wireless medium. In this paper, we propose a novel waveform design approach to minimize the likelihood that a message transmitted between trusted single-antenna nodes is intercepted by an eavesdropper. In particular, with knowledge first of the eavesdropper's channel state information (CSI), we find the optimum waveform and transmit energy that minimize the signal-to-interference-plus-noise ratio (SINR) at the output of the eavesdropper's maximum-SINR linear filter, while at the same time provide the intended receiver with a required pre-specified SINR at the output of its own max-SINR filter. Next, if prior knowledge of the eavesdropper's CSI is unavailable, we design a waveform that maximizes the amount of energy available for generating disturbance to eavesdroppers, termed artificial noise (AN), while the SINR of the intended receiver is maintained at the pre-specified level. The extensions of the secure waveform design problem to multiple intended receivers are also investigated and semidefinite relaxation (SDR) -an approximation technique based on convex optimization- is utilized to solve the arising NP-hard design problems. Extensive simulation studies confirm our analytical performance predictions and illustrate the benefits of the designed waveforms on securing single-input single-output (SISO) transmissions and multicasting.
Iterative Decoding and Turbo Equalization: The Z-Crease Phenomenon
Venue: arXiv cs.IT 2013
Year: 2013

Iterative probabilistic inference, popularly dubbed the soft-iterative paradigm, has found great use in a wide range of communication applications, including turbo decoding and turbo equalization. The classic approach of analyzing the iterative approach inevitably use the statistical and information-theoretical tools that bear ensemble-average flavors. This paper consider the per-block error rate performance, and analyzes it using nonlinear dynamical theory. By modeling the iterative processor as a nonlinear dynamical system, we report a universal "Z-crease phenomenon:" the zig-zag or up-and-down fluctuation -- rather than the monotonic decrease -- of the per-block errors, as the number of iteration increases. Using the turbo decoder as an example, we also report several interesting motion phenomenons which were not previously reported, and which appear to correspond well with the notion of "pseudo codewords" and "stopping/trapping sets." We further propose a heuristic stopping criterion to control Z-crease and identify the best iteration. Our stopping criterion is most useful for controlling the worst-case per-block errors, and helps to significantly reduce the average-iteration numbers.
A Gang of Bandits
Venue: arXiv cs.LG 2013
Year: 2013

Multi-armed bandit problems are receiving a great deal of attention because they adequately formalize the exploration-exploitation trade-offs arising in several industrially relevant applications, such as online advertisement and, more generally, recommendation systems. In many cases, however, these applications have a strong social component, whose integration in the bandit algorithm could lead to a dramatic performance increase. For instance, we may want to serve content to a group of users by taking advantage of an underlying network of social relationships among them. In this paper, we introduce novel algorithmic approaches to the solution of such networked bandit problems. More specifically, we design and analyze a global strategy which allocates a bandit algorithm to each network node (user) and allows it to "share" signals (contexts and payoffs) with the neghboring nodes. We then derive two more scalable variants of this strategy based on different ways of clustering the graph nodes. We experimentally compare the algorithm and its variants to state-of-the-art methods for contextual bandits that do not use the relational information. Our experiments, carried out on synthetic and real-world datasets, show a marked increase in prediction performance obtained by exploiting the network structure.
A Critical Assessment of Cost-Based Nash Methods for Demand Scheduling in Smart Grids
Venue: arXiv cs.GT 2013
Year: 2013

Demand-side management (DSM) is becoming an increasingly important component of the envisioned smart grid. The ability to improve the efficiency of energy use in the power system by altering demand is widely viewed as being not merely promising but in fact essential. However, while the advantages of DSM are clear, arriving at an efficient implementation has so far proven to be less straightforward. There have recently been many proposals put forth in the literature to tackle the demand scheduling aspect of DSM. One particular approach based on a game-theoretic treatment of the day-ahead load-scheduling problem has recently gained tremendous popularity in the DSM literature. In this letter, an assessment of this approach is conducted, and its main result is challenged.
Joint Signal and Channel State Information Compression for the Backhaul of Uplink Network MIMO Systems
Venue: arXiv cs.IT 2013
Year: 2013

In network MIMO cellular systems, subsets of base stations (BSs), or remote radio heads, are connected via backhaul links to central units (CUs) that perform joint encoding in the downlink and joint decoding in the uplink. Focusing on the uplink, an effective solution for the communication between BSs and the corresponding CU on the backhaul links is based on compressing and forwarding the baseband received signal from each BS. In the presence of ergodic fading, communicating the channel state information (CSI) from the BSs to the CU may require a sizable part of the backhaul capacity. In a prior work, this aspect was studied by assuming a Compress-Forward-Estimate (CFE) approach, whereby the BSs compress the training signal and CSI estimation takes place at the CU. In this work, instead, an Estimate-Compress-Forward (ECF) approach is investigated, whereby the BSs perform CSI estimation and forward a compressed version of the CSI to the CU. This choice is motivated by the information theoretic optimality of separate estimation and compression. Various ECF strategies are proposed that perform either separate or joint compression of estimated CSI and received signal. Moreover, the proposed strategies are combined with distributed source coding when considering multiple BSs. "Semi-coherent" strategies are also proposed that do not convey any CSI or training information on the backhaul links. Via numerical results, it is shown that a proper design of ECF strategies based on joint received signal and estimated CSI compression or of semi-coherent schemes leads to substantial performance gains compared to more conventional approaches based on non-coherent transmission or the CFE approach.
Self-Iterating Soft Equalizer
Venue: arXiv cs.IT 2013
Year: 2013

A self-iterating soft equalizer (SISE) consisting of a few relatively weak constituent equalizers is shown to provide robust performance even in severe intersymbol interference (ISI) channels that exhibit deep nulls and valleys within the signal band. Constituent equalizers are allowed to exchange soft information in the absence of interleavers based on the method that are designed to suppress significant correlation among their soft outputs. The resulting SISE works well as a stand-alone equalizer or as the equalizer component of a turbo equalization system. The performance advantages over existing methods are validated with bit-error-rate (BER) simulations and extrinsic information transfer (EXIT) chart analysis. It is shown that in turbo equalizer setting the SISE achieves performance closer to the maximum a posteriori probability equalizer than any other known schemes in very severe ISI channels.
SArF Map: Visualizing Software Architecture from Feature and Layer Viewpoints
Venue: arXiv cs.SE 2013
Year: 2013

To facilitate understanding the architecture of a software system, we developed SArF Map technique that visualizes software architecture from feature and layer viewpoints using a city metaphor. SArF Map visualizes implicit software features using our previous study, SArF dependency-based software clustering algorithm. Since features are high-level abstraction units of software, a generated map can be directly used for high-level decision making such as reuse and also for communications between developers and non-developer stakeholders. In SArF Map, each feature is visualized as a city block, and classes in the feature are laid out as buildings reflecting their software layer. Relevance between features is represented as streets. Dependency links are visualized lucidly. Through open source and industrial case studies, we show that the architecture of the target systems can be easily overviewed and that the quality of their packaging designs can be quickly assessed.
BER Analysis of Decision-Feedback Multiple Symbol Detection in Noncoherent MIMO Ultra-Wideband Systems
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we investigate noncoherent multiple-input multiple-output (MIMO) ultra-wideband (UWB) systems where the signal is encoded by differential space-time block code (DSTBC). DSTBC enables noncoherent MIMO UWB systems to achieve diversity gain. However, the traditional noncoherent symbol-by-symbol differential detection (DD) for DSTBC-UWB suffers from performance degradation compared with the coherent detection. We introduce a noncoherent multiple symbol detection (MSD) scheme to enhance the performance of DSTBC-UWB system. Although the MSD scheme can boost the performance more as the observation window size gets to larger, the complexity of the exhaustive search for MSD also exponentially increases in terms of the window size. To decrease the computational complexity, the concept of decision-feedback (DF) is introduced to MSD for DSTBC-UWB in this paper. The resultant DF-MSD yields reasonable complexity and also solid performance improvement. We provide the bit error rate (BER) analysis for the proposed DF-MSD. Both theoretical analysis and simulation results validate the proposed scheme.
Distributed Bayesian inference for consistent labeling of tracked objects in non-overlapping camera networks
Venue: arXiv cs.CV 2013
Year: 2013

One of the fundamental requirements for visual surveillance using non-overlapping camera networks is the correct labeling of tracked objects on each camera in a consistent way,in the sense that the captured tracklets, or observations in this paper, of the same object at different cameras should be assigned with the same label. In this paper, we formulate this task as a Bayesian inference problem and propose a distributed inference framework in which the posterior distribution of labeling variable corresponding to each observation, conditioned on all history appearance and spatio-temporal evidence made in the whole networks, is calculated based solely on local information processing on each camera and mutual information exchanging between neighboring cameras. In our framework, the number of objects presenting in the monitored region, i.e. the sampling space of labeling variables, does not need to be specified beforehand. Instead, it can be determined automatically on the fly. In addition, we make no assumption about the appearance distribution of a single object, but use similarity scores between appearance pairs, given by advanced object re-identification algorithm, as appearance likelihood for inference. This feature makes our method very flexible and competitive when observing condition undergoes large changes across camera views. To cope with the problem of missing detection, which is critical for distributed inference, we consider an enlarged neighborhood of each camera during inference and use a mixture model to describe the higher order spatio-temporal constraints. The robustness of the algorithm against missing detection is improved at the cost of slightly increased computation and communication burden at each camera node. Finally, we demonstrate the effectiveness of our method through experiments on an indoor Office Building dataset and an outdoor Campus Garden dataset.