OpenRaiser/Intern-Atlas huggingface dataset:
Equivalent Effect Function and Fast Intrinsic Mode Decomposition
Venue: arXiv cs.NA 2011
Year: 2011

The Equivalent Effect Function (EEF) is defined as having the identical integral values on the control points of the original time series data; the EEF can be obtained from the derivative of the spline function passing through the integral values on the control points. By choosing control points with different criteria, the EEF can be used to find the intrinsic mode function(IMF, fluctuation) and the residue (trend); to fit the curve of the original data function; and to take samples on original data with equivalent effect. As examples of application, results of trend and fluctuation on real stock historical data are calculated on different time scales. A new approach to extend the EEF to 2D intrinsic mode decomposition is introduced to resolve the inter slice non continuity problem, some photo image decomposition examples are presented.
Random Matrix Model for Nakagami-Hoyt Fading
Venue: arXiv cs.IT 2011
Year: 2011

Random matrix model for the Nakagami-q (Hoyt) fading in multiple-input multiple-output (MIMO) communication channels with arbitrary number of transmitting and receiving antennas is considered. The joint probability density for the eigenvalues of H†H (or HH†), where H is the channel matrix, is shown to correspond to the Laguerre crossover ensemble of random matrices and is given in terms of a Pfaffian. Exact expression for the marginal density of eigenvalues is obtained as a series consisting of associated Laguerre polynomials. This is used to study the effect of fading on the Shannon channel capacity. Exact expressions for higher order density correlation functions are also given which can be used to study the distribution of channel capacity.
Quadratic Goldreich-Levin Theorems
Venue: arXiv cs.DS 2011
Year: 2011

Decomposition theorems in classical Fourier analysis enable us to express a bounded function in terms of few linear phases with large Fourier coefficients plus a part that is pseudorandom with respect to linear phases. The Goldreich-Levin algorithm can be viewed as an algorithmic analogue of such a decomposition as it gives a way to efficiently find the linear phases associated with large Fourier coefficients. In the study of "quadratic Fourier analysis", higher-degree analogues of such decompositions have been developed in which the pseudorandomness property is stronger but the structured part correspondingly weaker. For example, it has previously been shown that it is possible to express a bounded function as a sum of a few quadratic phases plus a part that is small in the $U^3$ norm, defined by Gowers for the purpose of counting arithmetic progressions of length 4. We give a polynomial time algorithm for computing such a decomposition. A key part of the algorithm is a local self-correction procedure for Reed-Muller codes of order 2 (over $\F_2^n$) for a function at distance $1/2-ε$ from a codeword. Given a function $f:\F_2^n \to \{-1,1\}$ at fractional Hamming distance $1/2-ε$ from a quadratic phase (which is a codeword of Reed-Muller code of order 2), we give an algorithm that runs in time polynomial in $n$ and finds a codeword at distance at most $1/2-η$ for $η= η(ε)$. This is an algorithmic analogue of Samorodnitsky's result, which gave a tester for the above problem. To our knowledge, it represents the first instance of a correction procedure for any class of codes, beyond the list-decoding radius. In the process, we give algorithmic versions of results from additive combinatorics used in Samorodnitsky's proof and a refined version of the inverse theorem for the Gowers $U^3$ norm over $\F_2^n$.
Performance of MC-MC CDMA Systems with Nonlinear Models of HPA
Venue: arXiv cs.IT 2011
Year: 2011

A new wireless communication system denoted as Multi-Code Multi-Carrier CDMA (MC-MC CDMA), which is the combination of Multi-Code CDMA and Multi-Carrier CDMA, is analyzed in this paper. This system can satisfy multi-rate services using multi-code schemes and muti-carrier services used for high rate transmission. The system is evaluated using Traveling Wave Tube Amplifier (TWTA). This type of amplifiers continue to offer the best microwave high power amplifiers (HPA) performance in terms of power efficiency, size and cost, but lag behind Solid State Power Amplifiers (SSPA's) in linearity. This paper presents a technique for improving TWTA linearity. The use of predistorter (PD) linearization technique is described to provide TWTA performance comparable or superior to conventional SSPA's. The characteristics of the PD scheme is derived based on the extension of Saleh's model for HPA.
b-Bit Minwise Hashing for Large-Scale Linear SVM
Venue: arXiv cs.LG 2011
Year: 2011

In this paper, we propose to (seamlessly) integrate b-bit minwise hashing with linear SVM to substantially improve the training (and testing) efficiency using much smaller memory, with essentially no loss of accuracy. Theoretically, we prove that the resemblance matrix, the minwise hashing matrix, and the b-bit minwise hashing matrix are all positive definite matrices (kernels). Interestingly, our proof for the positive definiteness of the b-bit minwise hashing kernel naturally suggests a simple strategy to integrate b-bit hashing with linear SVM. Our technique is particularly useful when the data can not fit in memory, which is an increasingly critical issue in large-scale machine learning. Our preliminary experimental results on a publicly available webspam dataset (350K samples and 16 million dimensions) verified the effectiveness of our algorithm. For example, the training time was reduced to merely a few seconds. In addition, our technique can be easily extended to many other linear and nonlinear machine learning applications such as logistic regression.
Service Level Agreement for the QoS Guaranteed Mobile IPTV Services over Mobile WiMAX Networks
Venue: arXiv cs.MM 2011
Year: 2011

While mobile IPTV services are supported through the mobile WiMAX networks, there must need some guaranteed bandwidth for the IPTV services especially if IPTV and non-IPTV services are simultaneously supported by the mobile WiMAX networks. The quality of an IPTV service definitely depends on the allocated bandwidth for that channel. However, due to the high quality IPTV services and to support of huge non-IPTV traffic over mobile WiMAX networks, it is not possible to guarantee the sufficient amount of the limited mobile WiMAX bandwidth for the mobile IPTV services every time. A Service Level Agreement (SLA) between the mobile IPTV service provider and mobile WiMAX network operator to reserve sufficient bandwidth for the IPTV calls can increase the satisfaction level of the mobile IPTV users. In this paper, we propose a SLA negotiation procedure for mobile IPTV users over mobile WiMAX networks. The Bandwidth Broker controls the allocated bandwidth for IPTV and non-IPTV users. The proposed dynamically reserved bandwidth for the IPTV services increases the IPTV user's satisfaction level. The simulation results state that, our proposed scheme is able to provide better user satisfaction level for the IPTV users.
Assessing Vaccination Sentiments with Online Social Media: Implications for Infectious Disease Dynamics and Control
Venue: arXiv cs.SI 2011
Year: 2011

There is great interest in the dynamics of health behaviors in social networks and how they affect collective public health outcomes, but measuring population health behaviors over time and space requires substantial resources. Here, we use publicly available data from 101,853 users of online social media collected over a time period of almost six months to measure the spatio-temporal sentiment towards a new vaccine. We validated our approach by identifying a strong correlation between sentiments expressed online and CDC- estimated vaccination rates by region. Analysis of the network of opinionated users showed that information flows more often between users who share the same sentiments - and less often between users who do not share the same sentiments - than expected by chance alone. We also found that most communities are dominated by either positive or negative sentiments towards the novel vaccine. Simulations of infectious disease transmission show that if clusters of negative vaccine sentiments lead to clusters of unprotected individuals, the likelihood of disease outbreaks are greatly increased. Online social media provide unprecedented access to data allowing for inexpensive and efficient tools to identify target areas for intervention efforts and to evaluate their effectiveness.
PAC-Bayesian Analysis of the Exploration-Exploitation Trade-off
Venue: arXiv cs.LG 2011
Year: 2011

We develop a coherent framework for integrative simultaneous analysis of the exploration-exploitation and model order selection trade-offs. We improve over our preceding results on the same subject (Seldin et al., 2011) by combining PAC-Bayesian analysis with Bernstein-type inequality for martingales. Such a combination is also of independent interest for studies of multiple simultaneously evolving martingales.
On the Finiteness Problem for Automaton (Semi)groups
Venue: arXiv cs.FL 2011
Year: 2011

This paper addresses a decision problem highlighted by Grigorchuk, Nekrashevich, and Sushchanskii, namely the finiteness problem for automaton (semi)groups. For semigroups, we give an effective sufficient but not necessary condition for finiteness and, for groups, an effective necessary but not sufficient condition. The efficiency of the new criteria is demonstrated by testing all Mealy automata with small stateset and alphabet. Finally, for groups, we provide a necessary and sufficient condition that does not directly lead to a decision procedure.
Compressive Identification of Linear Operators
Venue: arXiv cs.IT 2011
Year: 2011

We consider the problem of identifying a linear deterministic operator from an input-output measurement. For the large class of continuous (and hence bounded) operators, under additional mild restrictions, we show that stable identifiability is possible if the total support area of the operator's spreading function satisfies D <= 1/2. This result holds for arbitrary (possibly fragmented) support regions of the spreading function, does not impose limitations on the total extent of the support region, and, most importantly, does not require the support region of the spreading function to be known prior to identification. Furthermore, we prove that asking for identifiability of only almost all operators, stable identifiability is possible if D <= 1. This result is surprising as it says that there is no penalty for not knowing the support region of the spreading function prior to identification.
On the correlation between bibliometric indicators and peer review: Reply to Opthof and Leydesdorff
Venue: arXiv cs.DL 2011
Year: 2011

Opthof and Leydesdorff [arXiv:1102.2569] reanalyze data reported by Van Raan [arXiv:physics/0511206] and conclude that there is no significant correlation between on the one hand average citation scores measured using the CPP/FCSm indicator and on the other hand the quality judgment of peers. We point out that Opthof and Leydesdorff draw their conclusions based on a very limited amount of data. We also criticize the statistical methodology used by Opthof and Leydesdorff. Using a larger amount of data and a more appropriate statistical methodology, we do find a significant correlation between the CPP/FCSm indicator and peer judgment.
Adaptive Parallel Iterative Deepening Search
Venue: arXiv cs.AI 2011
Year: 2011

Many of the artificial intelligence techniques developed to date rely on heuristic search through large spaces. Unfortunately, the size of these spaces and the corresponding computational effort reduce the applicability of otherwise novel and effective algorithms. A number of parallel and distributed approaches to search have considerably improved the performance of the search process. Our goal is to develop an architecture that automatically selects parallel search strategies for optimal performance on a variety of search problems. In this paper we describe one such architecture realized in the Eureka system, which combines the benefits of many different approaches to parallel heuristic search. Through empirical and theoretical analyses we observe that features of the problem space directly affect the choice of optimal parallel search strategy. We then employ machine learning techniques to select the optimal parallel search strategy for a given problem space. When a new search task is input to the system, Eureka uses features describing the search space and the chosen architecture to automatically select the appropriate search strategy. Eureka has been tested on a MIMD parallel processor, a distributed network of workstations, and a single workstation using multithreading. Results generated from fifteen puzzle problems, robot arm motion problems, artificial search spaces, and planning problems indicate that Eureka outperforms any of the tested strategies used exclusively for all problem instances and is able to greatly reduce the search time for these applications.
The Automatic Inference of State Invariants in TIM
Venue: arXiv cs.AI 2011
Year: 2011

As planning is applied to larger and richer domains the effort involved in constructing domain descriptions increases and becomes a significant burden on the human application designer. If general planners are to be applied successfully to large and complex domains it is necessary to provide the domain designer with some assistance in building correctly encoded domains. One way of doing this is to provide domain-independent techniques for extracting, from a domain description, knowledge that is implicit in that description and that can assist domain designers in debugging domain descriptions. This knowledge can also be exploited to improve the performance of planners: several researchers have explored the potential of state invariants in speeding up the performance of domain-independent planners. In this paper we describe a process by which state invariants can be extracted from the automatically inferred type structure of a domain. These techniques are being developed for exploitation by STAN, a Graphplan based planner that employs state analysis techniques to enhance its performance.
Efficient Implementation of the Plan Graph in STAN
Venue: arXiv cs.AI 2011
Year: 2011

STAN is a Graphplan-based planner, so-called because it uses a variety of STate ANalysis techniques to enhance its performance. STAN competed in the AIPS-98 planning competition where it compared well with the other competitors in terms of speed, finding solutions fastest to many of the problems posed. Although the domain analysis techniques STAN exploits are an important factor in its overall performance, we believe that the speed at which STAN solved the competition problems is largely due to the implementation of its plan graph. The implementation is based on two insights: that many of the graph construction operations can be implemented as bit-level logical operations on bit vectors, and that the graph should not be explicitly constructed beyond the fix point. This paper describes the implementation of STAN's plan graph and provides experimental results which demonstrate the circumstances under which advantages can be obtained from using this implementation.
Constructing Conditional Plans by a Theorem-Prover
Venue: arXiv cs.AI 2011
Year: 2011

The research on conditional planning rejects the assumptions that there is no uncertainty or incompleteness of knowledge with respect to the state and changes of the system the plans operate on. Without these assumptions the sequences of operations that achieve the goals depend on the initial state and the outcomes of nondeterministic changes in the system. This setting raises the questions of how to represent the plans and how to perform plan search. The answers are quite different from those in the simpler classical framework. In this paper, we approach conditional planning from a new viewpoint that is motivated by the use of satisfiability algorithms in classical planning. Translating conditional planning to formulae in the propositional logic is not feasible because of inherent computational limitations. Instead, we translate conditional planning to quantified Boolean formulae. We discuss three formalizations of conditional planning as quantified Boolean formulae, and present experimental results obtained with a theorem-prover.
Smoothing and Modeling of Video Transmission Rates over a QoS Network with Limited Bandwidth Connections
Venue: arXiv cs.NI 2011
Year: 2011

Transmission of video over a limited bandwidth network is challenging due to the natural variability of video, and link characteristics. Video smoothing techniques can be used to facilitate more effective transmission and to preserve better quality. In this paper we develop a semi-optimal video smoothing approach to manage the transmission of MPEG-4 and H.264 video while mapping it to be more suitable for a QoS based network. The proposed technique utilizes a smoothing buffer with pre-defined thresholds to smooth the transmission rates while assuming minimal information about the video to be transmitted. The results obtained showed a significant improvements in transmission rate variability while guaranteeing no buffer overflows or underflows. In addition, a queuing model is developed for the used smoothing algorithm for H.264 video streams with optimized encoding and packetization, utilizing the available H.264 macroblock ordering option.
A risk profile for information fusion algorithms
Venue: arXiv cs.IT 2011
Year: 2011

E.T. Jaynes, originator of the maximum entropy interpretation of statistical mechanics, emphasized that there is an inevitable trade-off between the conflicting requirements of robustness and accuracy for any inferencing algorithm. This is because robustness requires discarding of information in order to reduce the sensitivity to outliers. The principal of nonlinear statistical coupling, which is an interpretation of the Tsallis entropy generalization, can be used to quantify this trade-off. The coupled-surprisal, -ln_k (p)=-(p^k-1)/k, is a generalization of Shannon surprisal or the logarithmic scoring rule, given a forecast p of a true event by an inferencing algorithm. The coupling parameter k=1-q, where q is the Tsallis entropy index, is the degree of nonlinear coupling between statistical states. Positive (negative) values of nonlinear coupling decrease (increase) the surprisal information metric and thereby biases the risk in favor of decisive (robust) algorithms relative to the Shannon surprisal (k=0). We show that translating the average coupled-surprisal to an effective probability is equivalent to using the generalized mean of the true event probabilities as a scoring rule. The metric is used to assess the robustness, accuracy, and decisiveness of a fusion algorithm. We use a two-parameter fusion algorithm to combine input probabilities from N sources. The generalized mean parameter 'alpha' varies the degree of smoothing and raising to a power N^beta with beta between 0 and 1 provides a model of correlation.
Packing Chromatic Number of Distance Graphs
Venue: arXiv cs.DM 2011
Year: 2011

The packing chromatic number $χ_ρ(G)$ of a graph $G$ is the smallest integer $k$ such that vertices of $G$ can be partitioned into disjoint classes $X_1, ..., X_k$ where vertices in $X_i$ have pairwise distance greater than $i$. We study the packing chromatic number of infinite distance graphs $G(Z, D)$, i.e. graphs with the set $Z$ of integers as vertex set and in which two distinct vertices $i, j \in Z$ are adjacent if and only if $|i - j| \in D$. In this paper we focus on distance graphs with $D = \{1, t\}$. We improve some results of Togni who initiated the study. It is shown that $χ_ρ(G(Z, D)) \leq 35$ for sufficiently large odd $t$ and $χ_ρ(G(Z, D)) \leq 56$ for sufficiently large even $t$. We also give a lower bound 12 for $t \geq 9$ and tighten several gaps for $χ_ρ(G(Z, D))$ with small $t$.
Towards High-Performance Network Application Identification With Aggregate-Flow Cache
Venue: arXiv cs.NI 2011
Year: 2011

Classifying network traffic according to their application-layer protocols is an important task in modern networks for traffic management and network security. Existing payload-based or statistical methods of application identification cannot meet the demand of both high performance and accurate identification at the same time. We propose an application identification framework that classifies traffic at aggregate-flow level leveraging aggregate-flow cache. A detailed traffic classifier designed based on this framework is illustrated to improve the throughput of payload-based identification methods. We further optimize the classifier by proposing an efficient design of aggregate-flow cache. The cache design employs a frequency-based, recency-aware replacement algorithm based on the analysis of temporal locality of aggregate-flow cache. Experiments on real-world traces show that our traffic classifier with aggregate-flow cache can reduce up to 95% workload of backend identification engine. The proposed cache replacement algorithm outperforms well-known replacement algorithms, and achieves 90% of the optimal performance using only 15% of memory. The throughput of a payload-based identification system, L7-filter [1], is increased by up to 5.1 times by using our traffic classifier design.
A Philosophical Treatise of Universal Induction
Venue: arXiv cs.LG 2011
Year: 2011

Understanding inductive reasoning is a problem that has engaged mankind for thousands of years. This problem is relevant to a wide range of fields and is integral to the philosophy of science. It has been tackled by many great minds ranging from philosophers to scientists to mathematicians, and more recently computer scientists. In this article we argue the case for Solomonoff Induction, a formal inductive framework which combines algorithmic information theory with the Bayesian framework. Although it achieves excellent theoretical results and is based on solid philosophical foundations, the requisite technical knowledge necessary for understanding this framework has caused it to remain largely unknown and unappreciated in the wider scientific community. The main contribution of this article is to convey Solomonoff induction and its related concepts in a generally accessible form with the aim of bridging this current technical gap. In the process we examine the major historical contributions that have led to the formulation of Solomonoff Induction as well as criticisms of Solomonoff and induction in general. In particular we examine how Solomonoff induction addresses many issues that have plagued other inductive systems, such as the black ravens paradox and the confirmation problem, and compare this approach with other recent approaches.
Orthogonal Matching Pursuit: A Brownian Motion Analysis
Venue: arXiv cs.IT 2011
Year: 2011

A well-known analysis of Tropp and Gilbert shows that orthogonal matching pursuit (OMP) can recover a k-sparse n-dimensional real vector from 4 k log(n) noise-free linear measurements obtained through a random Gaussian measurement matrix with a probability that approaches one as n approaches infinity. This work strengthens this result by showing that a lower number of measurements, 2 k log(n - k), is in fact sufficient for asymptotic recovery. More generally, when the sparsity level satisfies kmin <= k <= kmax but is unknown, 2 kmax log(n - kmin) measurements is sufficient. Furthermore, this number of measurements is also sufficient for detection of the sparsity pattern (support) of the vector with measurement errors provided the signal-to-noise ratio (SNR) scales to infinity. The scaling 2 k log(n - k) exactly matches the number of measurements required by the more complex lasso method for signal recovery with a similar SNR scaling.