OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic recommender system : using cluster-based biases to improve the accuracy of the predictions
Venue: arXiv cs.LG 2012
Year: 2012

It is today accepted that matrix factorization models allow a high quality of rating prediction in recommender systems. However, a major drawback of matrix factorization is its static nature that results in a progressive declining of the accuracy of the predictions after each factorization. This is due to the fact that the new obtained ratings are not taken into account until a new factorization is computed, which can not be done very often because of the high cost of matrix factorization. In this paper, aiming at improving the accuracy of recommender systems, we propose a cluster-based matrix factorization technique that enables online integration of new ratings. Thus, we significantly enhance the obtained predictions between two matrix factorizations. We use finer-grained user biases by clustering similar items into groups, and allocating in these groups a bias to each user. The experiments we did on large datasets demonstrated the efficiency of our approach.
Evaluating Classifiers Without Expert Labels
Venue: arXiv cs.LG 2012
Year: 2012

This paper considers the challenge of evaluating a set of classifiers, as done in shared task evaluations like the KDD Cup or NIST TREC, without expert labels. While expert labels provide the traditional cornerstone for evaluating statistical learners, limited or expensive access to experts represents a practical bottleneck. Instead, we seek methodology for estimating performance of the classifiers which is more scalable than expert labeling yet preserves high correlation with evaluation based on expert labels. We consider both: 1) using only labels automatically generated by the classifiers (blind evaluation); and 2) using labels obtained via crowdsourcing. While crowdsourcing methods are lauded for scalability, using such data for evaluation raises serious concerns given the prevalence of label noise. In regard to blind evaluation, two broad strategies are investigated: combine & score and score & combine methods infer a single pseudo-gold label set by aggregating classifier labels; classifiers are then evaluated based on this single pseudo-gold label set. On the other hand, score & combine methods: 1) sample multiple label sets from classifier outputs, 2) evaluate classifiers on each label set, and 3) average classifier performance across label sets. When additional crowd labels are also collected, we investigate two alternative avenues for exploiting them: 1) direct evaluation of classifiers; or 2) supervision of combine & score methods. To assess generality of our techniques, classifier performance is measured using four common classification metrics, with statistical significance tests. Finally, we measure both score and rank correlations between estimated classifier performance vs. actual performance according to expert judgments. Rigorous evaluation of classifiers from the TREC 2011 Crowdsourcing Track shows reliable evaluation can be achieved without reliance on expert labels.
Extremes of Error Exponents
Venue: arXiv cs.IT 2012
Year: 2012

This paper determines the range of feasible values of standard error exponents for binary-input memoryless symmetric channels of fixed capacity $C$ and shows that extremes are attained by the binary symmetric and the binary erasure channel. The proof technique also provides analogous extremes for other quantities related to Gallager's $E_0$ function, such as the cutoff rate, the Bhattacharyya parameter, and the channel dispersion.
Multiscale Markov Decision Problems: Compression, Solution, and Transfer Learning
Venue: arXiv cs.AI 2012
Year: 2012

Many problems in sequential decision making and stochastic control often have natural multiscale structure: sub-tasks are assembled together to accomplish complex goals. Systematically inferring and leveraging hierarchical structure, particularly beyond a single level of abstraction, has remained a longstanding challenge. We describe a fast multiscale procedure for repeatedly compressing, or homogenizing, Markov decision processes (MDPs), wherein a hierarchy of sub-problems at different scales is automatically determined. Coarsened MDPs are themselves independent, deterministic MDPs, and may be solved using existing algorithms. The multiscale representation delivered by this procedure decouples sub-tasks from each other and can lead to substantial improvements in convergence rates both locally within sub-problems and globally across sub-problems, yielding significant computational savings. A second fundamental aspect of this work is that these multiscale decompositions yield new transfer opportunities across different problems, where solutions of sub-tasks at different levels of the hierarchy may be amenable to transfer to new problems. Localized transfer of policies and potential operators at arbitrary scales is emphasized. Finally, we demonstrate compression and transfer in a collection of illustrative domains, including examples involving discrete and continuous statespaces.
Throughput Analysis of Primary and Secondary Networks in a Shared IEEE 802.11 System
Venue: arXiv cs.NI 2012
Year: 2012

In this paper, we analyze the coexistence of a primary and a secondary (cognitive) network when both networks use the IEEE 802.11 based distributed coordination function for medium access control. Specifically, we consider the problem of channel capture by a secondary network that uses spectrum sensing to determine the availability of the channel, and its impact on the primary throughput. We integrate the notion of transmission slots in Bianchi's Markov model with the physical time slots, to derive the transmission probability of the secondary network as a function of its scan duration. This is used to obtain analytical expressions for the throughput achievable by the primary and secondary networks. Our analysis considers both saturated and unsaturated networks. By performing a numerical search, the secondary network parameters are selected to maximize its throughput for a given level of protection of the primary network throughput. The theoretical expressions are validated using extensive simulations carried out in the Network Simulator 2. Our results provide critical insights into the performance and robustness of different schemes for medium access by the secondary network. In particular, we find that the channel captures by the secondary network does not significantly impact the primary throughput, and that simply increasing the secondary contention window size is only marginally inferior to silent-period based methods in terms of its throughput performance.
Toward Turing's A-type Unorganised Machines in an Unconventional Substrate: a Dynamic Representation in Compartmentalised Excitable Chemical Media
Venue: arXiv cs.ET 2012
Year: 2012

Turing presented a general representation scheme by which to achieve artificial intelligence - unorganised machines. Significantly, these were a form of discrete dynamical system and yet such representations remain relatively unexplored. Further, at the same time as also suggesting that natural evolution may provide inspiration for search mechanisms to design machines, he noted that mechanisms inspired by the social aspects of learning may prove useful. This paper presents initial results from consideration of using Turing's dynamical representation within an unconventional substrate - networks of Belousov-Zhabotinsky vesicles - designed by an imitation-based, i.e., cultural, approach. Turing's representation scheme is also extended to include a fuller set of Boolean functions at the nodes of the recurrent networks.
Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent One-Way and Two-Way Deterministic Automata
Venue: arXiv cs.FL 2012
Year: 2012

We investigate the conversion of one-way nondeterministic finite automata and context-free grammars into Parikh equivalent one-way and two-way deterministic finite automata, from a descriptional complexity point of view. We prove that for each one-way nondeterministic automaton with $n$ states there exist Parikh equivalent one-way and two-way deterministic automata with $e^{O(\sqrt{n \ln n})}$ and $p(n)$ states, respectively, where $p(n)$ is a polynomial. Furthermore, these costs are tight. In contrast, if all the words accepted by the given automaton contain at least two different letters, then a Parikh equivalent one-way deterministic automaton with a polynomial number of states can be found. Concerning context-free grammars, we prove that for each grammar in Chomsky normal form with h variables there exist Parikh equivalent one-way and two-way deterministic automata with $2^{O(h^2)}$ and $2^{O(h)}$ states, respectively. Even these bounds are tight.
Structure and Dynamics of Information Pathways in Online Media
Venue: arXiv cs.SI 2012
Year: 2012

Diffusion of information, spread of rumors and infectious diseases are all instances of stochastic processes that occur over the edges of an underlying network. Many times networks over which contagions spread are unobserved, and such networks are often dynamic and change over time. In this paper, we investigate the problem of inferring dynamic networks based on information diffusion data. We assume there is an unobserved dynamic network that changes over time, while we observe the results of a dynamic process spreading over the edges of the network. The task then is to infer the edges and the dynamics of the underlying network. We develop an on-line algorithm that relies on stochastic convex optimization to efficiently solve the dynamic network inference problem. We apply our algorithm to information diffusion among 3.3 million mainstream media and blog sites and experiment with more than 179 million different pieces of information spreading over the network in a one year period. We study the evolution of information pathways in the online media space and find interesting insights. Information pathways for general recurrent topics are more stable across time than for on-going news events. Clusters of news media sites and blogs often emerge and vanish in matter of days for on-going news events. Major social movements and events involving civil population, such as the Libyan's civil war or Syria's uprise, lead to an increased amount of information pathways among blogs as well as in the overall increase in the network centrality of blogs and social media sites.
A Novel Distance-Based Approach to Constrained Rank Aggregation
Venue: arXiv cs.GT 2012
Year: 2012

We consider a classical problem in choice theory -- vote aggregation -- using novel distance measures between permutations that arise in several practical applications. The distance measures are derived through an axiomatic approach, taking into account various issues arising in voting with side constraints. The side constraints of interest include non-uniform relevance of the top and the bottom of rankings (or equivalently, eliminating negative outliers in votes) and similarities between candidates (or equivalently, introducing diversity in the voting process). The proposed distance functions may be seen as weighted versions of the Kendall $τ$ distance and weighted versions of the Cayley distance. In addition to proposing the distance measures and providing the theoretical underpinnings for their applications, we also consider algorithmic aspects associated with distance-based aggregation processes. We focus on two methods. One method is based on approximating weighted distance measures by a generalized version of Spearman's footrule distance, and it has provable constant approximation guarantees. The second class of algorithms is based on a non-uniform Markov chain method inspired by PageRank, for which currently only heuristic guarantees are known. We illustrate the performance of the proposed algorithms for a number of distance measures for which the optimal solution may be easily computed.
Split Scheduling with Uniform Setup Times
Venue: arXiv cs.DS 2012
Year: 2012

We study a scheduling problem in which jobs may be split into parts, where the parts of a split job may be processed simultaneously on more than one machine. Each part of a job requires a setup time, however, on the machine where the job part is processed. During setup a machine cannot process or set up any other job. We concentrate on the basic case in which setup times are job-, machine-, and sequence-independent. Problems of this kind were encountered when modelling practical problems in planning disaster relief operations. Our main algorithmic result is a polynomial-time algorithm for minimising total completion time on two parallel identical machines. We argue why the same problem with three machines is not an easy extension of the two-machine case, leaving the complexity of this case as a tantalising open problem. We give a constant-factor approximation algorithm for the general case with any number of machines and a polynomial-time approximation scheme for a fixed number of machines. For the version with objective minimising weighted total completion time we prove NP-hardness. Finally, we conclude with an overview of the state of the art for other split scheduling problems with job-, machine-, and sequence-independent setup times.
Controlling Home Appliances Remotely through Voice Command
Venue: arXiv cs.OH 2012
Year: 2012

Controlling appliances is a main part of automation. The main object of Home automation is to provide a wireless communication link of home appliances to the remote user. The main objective of this work is to make such a system which controls the home appliances remotely. This paper discusses two methods of controlling home appliances one is via voice to text SMS and other is to use the mobile as a remote control, this system will provide a benefit to the elderly and disable people and also to those who are unaware of typing an SMS.
Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
Venue: arXiv cs.LG 2012
Year: 2012

Stochastic Gradient Descent (SGD) is one of the simplest and most popular stochastic optimization methods. While it has already been theoretically studied for decades, the classical analysis usually required non-trivial smoothness assumptions, which do not apply to many modern applications of SGD with non-smooth objective functions such as support vector machines. In this paper, we investigate the performance of SGD without such smoothness assumptions, as well as a running average scheme to convert the SGD iterates to a solution with optimal optimization accuracy. In this framework, we prove that after T rounds, the suboptimality of the last SGD iterate scales as O(log(T)/\sqrt{T}) for non-smooth convex objective functions, and O(log(T)/T) in the non-smooth strongly convex case. To the best of our knowledge, these are the first bounds of this kind, and almost match the minimax-optimal rates obtainable by appropriate averaging schemes. We also propose a new and simple averaging scheme, which not only attains optimal rates, but can also be easily computed on-the-fly (in contrast, the suffix averaging scheme proposed in Rakhlin et al. (2011) is not as simple to implement). Finally, we provide some experimental illustrations.
Self Authentication of image through Daubechies Transform technique (SADT)
Venue: arXiv cs.CR 2012
Year: 2012

In this paper a 4 x 4 Daubechies transform based authentication technique termed as SADT has been proposed to authenticate gray scale images. The cover image is transformed into the frequency domain using 4 x 4 mask in a row major order using Daubechies transform technique, resulting four frequency subbands AF, HF, VF and DF. One byte of every band in a mask is embedding with two or four bits of secret information. Experimental results are computed and compared with the existing authentication techniques like Li s method [5], SCDFT [6], Region-Based method [7] and other similar techniques based on Mean Square Error (MSE), Peak Signal to Noise Ratio (PSNR) and Image Fidelity (IF), which shows better performance in SADT.
Condensés de textes par des méthodes numériques
Venue: arXiv cs.IR 2012
Year: 2012

Since information in electronic form is already a standard, and that the variety and the quantity of information become increasingly large, the methods of summarizing or automatic condensation of texts is a critical phase of the analysis of texts. This article describes CORTEX a system based on numerical methods, which allows obtaining a condensation of a text, which is independent of the topic and of the length of the text. The structure of the system enables it to find the abstracts in French or Spanish in very short times.
Joint Secured and Robust Technique for OFDM Systems
Venue: arXiv cs.IT 2012
Year: 2012

This work presents a novel technique for joint secured and robust transmission of orthogonal frequency division multiplexing (OFDM) based communication systems. The proposed system is implemented by developing a new OFDM symbol structure based on symmetric key cryptography. At the receiver side, data detection becomes infeasible without the knowledge of the secret key. For an intruder who tries to detect the data without the knowledge of the key, the signal will be a noise-like signal. In addition to the system security, theoretical and simulation results demonstrated that the proposed system provides time and frequency diversity, which makes the system highly robust against severe frequency-selective fading as well as other impairments such as impulsive noise and multiple access interference. For particular frequency-selective fading channels, the bit error rate (BER) improvements was about 15 dB at BER of 10E-4.
The Dynamic Controllability of Conditional STNs with Uncertainty
Venue: arXiv cs.AI 2012
Year: 2012

Recent attempts to automate business processes and medical-treatment processes have uncovered the need for a formal framework that can accommodate not only temporal constraints, but also observations and actions with uncontrollable durations. To meet this need, this paper defines a Conditional Simple Temporal Network with Uncertainty (CSTNU) that combines the simple temporal constraints from a Simple Temporal Network (STN) with the conditional nodes from a Conditional Simple Temporal Problem (CSTP) and the contingent links from a Simple Temporal Network with Uncertainty (STNU). A notion of dynamic controllability for a CSTNU is defined that generalizes the dynamic consistency of a CTP and the dynamic controllability of an STNU. The paper also presents some sound constraint-propagation rules for dynamic controllability that are expected to form the backbone of a dynamic-controllability-checking algorithm for CSTNUs.
An Image Steganography Scheme using Randomized Algorithm and Context-Free Grammar
Venue: arXiv cs.CR 2012
Year: 2012

Currently, cryptography is in wide use as it is being exploited in various domains from data confidentiality to data integrity and message authentication. Basically, cryptography shuffles data so that they become unreadable by unauthorized parties. However, clearly visible encrypted messages, no matter how unbreakable, will arouse suspicions. A better approach would be to hide the very existence of the message using steganography. Fundamentally, steganography conceals secret data into innocent-looking mediums called carriers which can then travel from the sender to the receiver safe and unnoticed. This paper proposes a novel steganography scheme for hiding digital data into uncompressed image files using a randomized algorithm and a context-free grammar. Besides, the proposed scheme uses two mediums to deliver the secret data: a carrier image into which the secret data are hidden into random pixels, and a well-structured English text that encodes the location of the random carrier pixels. The English text is generated at runtime using a context-free grammar coupled with a lexicon of English words. The proposed scheme is stealthy, and hard to be noticed, detected, and recovered. Experiments conducted showed how the covering and the uncovering processes of the proposed scheme work. As future work, a semantic analyzer is to be developed so as to make the English text medium semantically correct, and consequently safer to be transmitted without drawing any attention.
Low Rank Mechanism for Optimizing Batch Queries under Differential Privacy
Venue: arXiv cs.DB 2012
Year: 2012

Differential privacy is a promising privacy-preserving paradigm for statistical query processing over sensitive data. It works by injecting random noise into each query result, such that it is provably hard for the adversary to infer the presence or absence of any individual record from the published noisy results. The main objective in differentially private query processing is to maximize the accuracy of the query results, while satisfying the privacy guarantees. Previous work, notably \cite{LHR+10}, has suggested that with an appropriate strategy, processing a batch of correlated queries as a whole achieves considerably higher accuracy than answering them individually. However, to our knowledge there is currently no practical solution to find such a strategy for an arbitrary query batch; existing methods either return strategies of poor quality (often worse than naive methods) or require prohibitively expensive computations for even moderately large domains. Motivated by this, we propose the \emph{Low-Rank Mechanism} (LRM), the first practical differentially private technique for answering batch queries with high accuracy, based on a \emph{low rank approximation} of the workload matrix. We prove that the accuracy provided by LRM is close to the theoretical lower bound for any mechanism to answer a batch of queries under differential privacy. Extensive experiments using real data demonstrate that LRM consistently outperforms state-of-the-art query processing solutions under differential privacy, by large margins.
Tree Projections and Structural Decomposition Methods: Minimality and Game-Theoretic Characterization
Venue: arXiv cs.DM 2012
Year: 2012

Tree projections provide a mathematical framework that encompasses all the various (purely) structural decomposition methods that have been proposed in the literature to single out classes of nearly-acyclic (hyper)graphs, such as the tree decomposition method, which is the most powerful decomposition method on graphs, and the (generalized) hypertree decomposition method, which is its natural counterpart on arbitrary hypergraphs. The paper analyzes this framework, by focusing in particular on "minimal" tree projections, that is, on tree projections without useless redundancies. First, it is shown that minimal tree projections enjoy a number of properties that are usually required for normal form decompositions in various structural decomposition methods. In particular, they enjoy the same kind of connection properties as (minimal) tree decompositions of graphs, with the result being tight in the light of the negative answer that is provided to the open question about whether they enjoy a slightly stronger notion of connection property, defined to speed-up the computation of hypertree decompositions. Second, it is shown that tree projections admit a natural game-theoretic characterization in terms of the Captain and Robber game. In this game, as for the Robber and Cops game characterizing tree decompositions, the existence of winning strategies implies the existence of monotone ones. As a special case, the Captain and Robber game can be used to characterize the generalized hypertree decomposition method, where such a game-theoretic characterization was missing and asked for. Besides their theoretical interest, these results have immediate algorithmic applications both for the general setting and for structural decomposition methods that can be recast in terms of tree projections.