OpenRaiser/Intern-Atlas huggingface dataset:
Mediated Experts for Deep Convolutional Networks
Venue: arXiv cs.LG 2015
Year: 2015

We present a new supervised architecture termed Mediated Mixture-of-Experts (MMoE) that allows us to improve classification accuracy of Deep Convolutional Networks (DCN). Our architecture achieves this with the help of expert networks: A network is trained on a disjoint subset of a given dataset and then run in parallel to other experts during deployment. A mediator is employed if experts contradict each other. This allows our framework to naturally support incremental learning, as adding new classes requires (re-)training of the new expert only. We also propose two measures to control computational complexity: An early-stopping mechanism halts experts that have low confidence in their prediction. The system allows to trade-off accuracy and complexity without further retraining. We also suggest to share low-level convolutional layers between experts in an effort to avoid computation of a near-duplicate feature set. We evaluate our system on a popular dataset and report improved accuracy compared to a single model of same configuration.
On Sketching Quadratic Forms
Venue: arXiv cs.DS 2015
Year: 2015

We undertake a systematic study of sketching a quadratic form: given an $n \times n$ matrix $A$, create a succinct sketch $\textbf{sk}(A)$ which can produce (without further access to $A$) a multiplicative $(1+ε)$-approximation to $x^T A x$ for any desired query $x \in \mathbb{R}^n$. While a general matrix does not admit non-trivial sketches, positive semi-definite (PSD) matrices admit sketches of size $Θ(ε^{-2} n)$, via the Johnson-Lindenstrauss lemma, achieving the "for each" guarantee, namely, for each query $x$, with a constant probability the sketch succeeds. (For the stronger "for all" guarantee, where the sketch succeeds for all $x$'s simultaneously, again there are no non-trivial sketches.) We design significantly better sketches for the important subclass of graph Laplacian matrices, which we also extend to symmetric diagonally dominant matrices. A sequence of work culminating in that of Batson, Spielman, and Srivastava (SIAM Review, 2014), shows that by choosing and reweighting $O(ε^{-2} n)$ edges in a graph, one achieves the "for all" guarantee. Our main results advance this front. $\bullet$ For the "for all" guarantee, we prove that Batson et al.'s bound is optimal even when we restrict to "cut queries" $x\in \{0,1\}^n$. In contrast, previous lower bounds showed the bound only for {\em spectral-sparsifiers}. $\bullet$ For the "for each" guarantee, we design a sketch of size $\tilde O(ε^{-1} n)$ bits for "cut queries" $x\in \{0,1\}^n$. We prove a nearly-matching lower bound of $Ω(ε^{-1} n)$ bits. For general queries $x \in \mathbb{R}^n$, we construct sketches of size $\tilde{O}(ε^{-1.6} n)$ bits.
Gaussian Mixture Embeddings for Multiple Word Prototypes
Venue: arXiv cs.CL 2015
Year: 2015

Recently, word representation has been increasingly focused on for its excellent properties in representing the word semantics. Previous works mainly suffer from the problem of polysemy phenomenon. To address this problem, most of previous models represent words as multiple distributed vectors. However, it cannot reflect the rich relations between words by representing words as points in the embedded space. In this paper, we propose the Gaussian mixture skip-gram (GMSG) model to learn the Gaussian mixture embeddings for words based on skip-gram framework. Each word can be regarded as a gaussian mixture distribution in the embedded space, and each gaussian component represents a word sense. Since the number of senses varies from word to word, we further propose the Dynamic GMSG (D-GMSG) model by adaptively increasing the sense number of words during training. Experiments on four benchmarks show the effectiveness of our proposed model.
Semi-dynamic Green Resource Management in Downlink Heterogeneous Networks by Group Sparse Power Control
Venue: arXiv cs.IT 2015
Year: 2015

This paper addresses the energy-saving problem for the downlink of heterogeneous networks, which aims at minimizing the total base stations (BSs) power consumption while each user's rate requirement is supported. The basic idea of this work is to make use of the flexibility and scalability of the system such that more benefits can be gained by efficient resource management. This motivates us to propose a flexible BS power consumption model, which can control system resources, such as antennas, frequency carriers and transmit power allocation in an energy efficient manner rather than the "on/off" binary sleep mode for BSs. To denote these power-saving modes, we employ the group sparsity of the transmit power vector instead of the {0, 1} variables. Based on this power model, a semi-dynamic green resource management mechanism is proposed, which can jointly solve a series of resource management problems, including BS association, frequency carriers (FCs) assignment, and the transmit power allocation, by group sparse power control based on the large scale fading values. In particular, the successive convex approximation (SCA)-based algorithm is applied to solve a stationary solution to the original non-convex problem. Simulation results also verify the proposed BS power model and the green resource management mechanism.
Good, Better, Best: Choosing Word Embedding Context
Venue: arXiv cs.CL 2015
Year: 2015

We propose two methods of learning vector representations of words and phrases that each combine sentence context with structural features extracted from dependency trees. Using several variations of neural network classifier, we show that these combined methods lead to improved performance when used as input features for supervised term-matching.
QINL: Query-integrated Languages
Venue: arXiv cs.PL 2015
Year: 2015

We describe an alternative solution to the impedance-mismatch problem between programming and query languages: rather than embed queries in a programming language, as done in LINQ systems, we embed programs in a query language, and dub the result QINL.
Comment on Two schemes for Secure Outsourcing of Linear Programming
Venue: arXiv cs.CR 2015
Year: 2015

Recently, Wang et al. [IEEE INFOCOM 2011, 820-828], and Nie et al. [IEEE AINA 2014, 591-596] have proposed two schemes for secure outsourcing of large-scale linear programming (LP). They did not consider the standard form: minimize c^{T}x, subject to Ax=b, x>0. Instead, they studied a peculiar form: minimize c^{T}x, subject to Ax = b, Bx>0, where B is a non-singular matrix. In this note, we stress that the proposed peculiar form is unsolvable and meaningless. The two schemes have confused the functional inequality constraints Bx>0 with the nonnegativity constraints x>0 in the linear programming model. But the condition x>0 is indispensable to the simplex method. Therefore, both two schemes failed.
ExpressionBot: An Emotive Lifelike Robotic Face for Face-to-Face Communication
Venue: arXiv cs.RO 2015
Year: 2015

This article proposes an emotive lifelike robotic face, called ExpressionBot, that is designed to support verbal and non-verbal communication between the robot and humans, with the goal of closely modeling the dynamics of natural face-to-face communication. The proposed robotic head consists of two major components: 1) a hardware component that contains a small projector, a fish-eye lens, a custom-designed mask and a neck system with 3 degrees of freedom; 2) a facial animation system, projected onto the robotic mask, that is capable of presenting facial expressions, realistic eye movement, and accurate visual speech. We present three studies that compare Human-Robot Interaction with Human-Computer Interaction with a screen-based model of the avatar. The studies indicate that the robotic face is well accepted by users, with some advantages in recognition of facial expression and mutual eye gaze contact.
Stochastic Duty Cycling for Heterogenous Energy Harvesting Networks
Venue: arXiv cs.NI 2015
Year: 2015

In recent years, there have been several kinds of energy harvesting networks containing some tiny devices, such as ambient backscatter, ring and renewable sensor networks. During energy harvesting, such networks suffer from the energy heterogeneity, dynamics and prediction hardness because the access to natural resources is often spatiotemporal different and timely changing among the devices. Meanwhile, the charging efficiency is quite low especially when the power of the harvested energy is weak. It results in the energy waste to store the harvested energy indirectly. These features bring challenging and interesting issues on efficient allocation of the harvested energy. This paper studies the \emph{stochastic duty cycling} by considering these features with the objective characterized by maximizing the common active time. We consider two cases: offline and online stochastic duty cycling. For the offline case, we design an optimal solution: offline duty cycling algorithm. For the online case, we design an online duty cycling algorithm, which achieves the approximation ratio with at least $1-e^{-γ^2}$, where $γ$ is the probability able to harvest energy. We also evaluate our algorithms with the experiment on a real energy harvesting network. The experiment results show that the performance of the online algorithm can be very close to the offline algorithm.
Enhanced Transmit Antenna Selection Scheme for Secure Throughput Maximization Without CSI at the Transmitter and its Applications on Smart Grids
Venue: arXiv cs.IT 2015
Year: 2015

This paper addresses the establishment of secure communication links between smart-meters (Alice) and an aggregator (Bob) in the presence of an eavesdropper (Eve). The proposed scenario assumes: (i) MIMOME wiretap channel; (ii) transmit antenna selection at the Alice; (iii) no channel state information at the transmitter; (iv) fixed Wyner codes; and (v) guarantee of secure throughput by both quality of service and secrecy outage constraints. We propose a simple protocol to enhance security via transmit antenna selection, and then assess its performance in closed-form by means of secrecy outage and successful transmission probabilities. We assume these probabilities are our constraints and then maximize the secure throughput, establishing a security-reliability trade-off for the proposed scenario. Our numerical results illustrate the effect of this trade-off on the secure throughput as well as on the number of antennas at Alice, Bob and Eve. Interestingly, a small sacrifice in reliability allows secrecy enhancement in terms of secure bps/Hz. We apply this idea in our smart grid application to exemplify that, although Eve may acquire some samples of the average power demand of a household, it is not enough to properly reconstruct such curve.
Near-Optimal UGC-hardness of Approximating Max k-CSP_R
Venue: arXiv cs.CC 2015
Year: 2015

In this paper, we prove an almost-optimal hardness for Max $k$-CSP$_R$ based on Khot's Unique Games Conjecture (UGC). In Max $k$-CSP$_R$, we are given a set of predicates each of which depends on exactly $k$ variables. Each variable can take any value from $1, 2, \dots, R$. The goal is to find an assignment to variables that maximizes the number of satisfied predicates. Assuming the Unique Games Conjecture, we show that it is NP-hard to approximate Max $k$-CSP$_R$ to within factor $2^{O(k \log k)}(\log R)^{k/2}/R^{k - 1}$ for any $k, R$. To the best of our knowledge, this result improves on all the known hardness of approximation results when $3 \leq k = o(\log R/\log \log R)$. In this case, the previous best hardness result was NP-hardness of approximating within a factor $O(k/R^{k-2})$ by Chan. When $k = 2$, our result matches the best known UGC-hardness result of Khot, Kindler, Mossel and O'Donnell. In addition, by extending an algorithm for Max 2-CSP$_R$ by Kindler, Kolla and Trevisan, we provide an $Ω(\log R/R^{k - 1})$-approximation algorithm for Max $k$-CSP$_R$. This algorithm implies that our inapproximability result is tight up to a factor of $2^{O(k \log k)}(\log R)^{k/2 - 1}$. In comparison, when $3 \leq k$ is a constant, the previously known gap was $O(R)$, which is significantly larger than our gap of $O(\text{polylog } R)$. Finally, we show that we can replace the Unique Games Conjecture assumption with Khot's $d$-to-1 Conjecture and still get asymptotically the same hardness of approximation.
Exponential Natural Particle Filter
Venue: arXiv cs.LG 2015
Year: 2015

Particle Filter algorithm (PF) suffers from some problems such as the loss of particle diversity, the need for large number of particles, and the costly selection of the importance density functions. In this paper, a novel Exponential Natural Particle Filter (xNPF) is introduced to solve the above problems. In this approach, a state transitional probability with the use of natural gradient learning is proposed which balances exploration and exploitation more robustly. The results show that xNPF converges much closer to the true target states than the other state of the art particle filter.
Probabilistic Diffusion in Random Network Graphs
Venue: arXiv cs.SI 2015
Year: 2015

In this paper, we consider a random network such that there could be a link between any two nodes in the network with a certain probability (plink). Diffusion is the phenomenon of spreading information throughout the network, starting from one or more initial set of nodes (called the early adopters). Information spreads along the links with a certain probability (pdiff). Diffusion happens in rounds with the first round involving the early adopters. The nodes that receive the information for the first time are said to be covered and become candidates for diffusion in the subsequent round. Diffusion continues until all the nodes in the network have received the information (successful diffusion) or there are no more candidate nodes to spread the information but one or more nodes are yet to receive the information (diffusion failure). On the basis of exhaustive simulations conducted in this paper, we observe that for a given plink and pdiff values, the fraction of successful diffusion attempts does not appreciably change with increase in the number of early adopters; whereas, the average number of rounds per successful diffusion attempt decreases with increase in the number of early adopters. The invariant nature of the fraction of successful diffusion attempts with increase in the number of early adopters for a random network (for fixed plink and pdiff values) is an interesting and noteworthy observation (for further research) and it has not been hitherto reported in the literature.
Hybrid Precoding for Physical Layer Multicasting
Venue: arXiv cs.IT 2015
Year: 2015

This work investigates the problem of downlink transmit precoding for physical layer multicasting with a limited number of radio-frequency (RF) chains. To tackle the RF hardware constraint, we consider a hybrid precoder that is partitioned into a high-dimensional RF precoder and a low-dimensional baseband precoder. Considering a total transmit power constraint over the RF chains, the goal is to maximize the minimum (max-min) received signal-to-noise ratio (SNR) among all users. We propose a low complexity algorithm to compute the RF precoder that achieves near-optimal max-min performance. Moreover, we derive a simple condition under which the hybrid precoding driven by a limited number of RF chains incurs no loss of optimality with respect to the fully digital precoding case. Finally, numerical results validate the effectiveness of the proposed algorithm and theoretical findings.
On Feasibility of 5G-Grade Dedicated RF Charging Technology for Wireless-Powered Wearables
Venue: arXiv cs.NI 2015
Year: 2015

For decades, wireless energy transfer and harvesting remained of focused attention in the research community, but with limited practical applications. Recently, with the development of fifth-generation (5G) mobile technology, the concept of dedicated radio-frequency (RF) charging promises to support the growing market of wearable devices. In this work, we shed light on the potential of wireless RF power transfer by elaborating upon feasible system parameters and architecture, emphasizing the basic trade-offs behind omni-directional and directional out-of-band energy transmission, providing system-level performance evaluation, as well as discussing open challenges on the way to sustainable wireless-powered wearables. The key aspects highlighted in this article include system operation choices, user mobility effects, impact of network and user densities, as well as regulatory issues. Ultimately, our research targets to facilitate the integration of wireless RF charging technology into the emerging 5G ecosystem.
Images Don't Lie: Transferring Deep Visual Semantic Features to Large-Scale Multimodal Learning to Rank
Venue: arXiv cs.CV 2015
Year: 2015

Search is at the heart of modern e-commerce. As a result, the task of ranking search results automatically (learning to rank) is a multibillion dollar machine learning problem. Traditional models optimize over a few hand-constructed features based on the item's text. In this paper, we introduce a multimodal learning to rank model that combines these traditional features with visual semantic features transferred from a deep convolutional neural network. In a large scale experiment using data from the online marketplace Etsy, we verify that moving to a multimodal representation significantly improves ranking quality. We show how image features can capture fine-grained style information not available in a text-only representation. In addition, we show concrete examples of how image information can successfully disentangle pairs of highly different items that are ranked similarly by a text-only model.
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
Venue: arXiv cs.DS 2015
Year: 2015

Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an $n\times n$ matrix $M$ and will receive $n$ column-vectors of size $n$, denoted by $v_1,\ldots,v_n$, one by one. After seeing each vector $v_i$, we have to output the product $Mv_i$ before we can see the next vector. A naive algorithm can solve this problem using $O(n^3)$ time in total, and its running time can be slightly improved to $O(n^3/\log^2 n)$ [Williams SODA'07]. We show that a conjecture that there is no truly subcubic ($O(n^{3-ε})$) time algorithm for this problem can be used to exhibit the underlying polynomial time hardness shared by many dynamic problems. For a number of problems, such as subgraph connectivity, Pagh's problem, $d$-failure connectivity, decremental single-source shortest paths, and decremental transitive closure, this conjecture implies tight hardness results. Thus, proving or disproving this conjecture will be very interesting as it will either imply several tight unconditional lower bounds or break through a common barrier that blocks progress with these problems. This conjecture might also be considered as strong evidence against any further improvement for these problems since refuting it will imply a major breakthrough for combinatorial Boolean matrix multiplication and other long-standing problems if the term "combinatorial algorithms" is interpreted as "non-Strassen-like algorithms" [Ballard et al. SPAA'11]. The conjecture also leads to hardness results for problems that were previously based on diverse problems and conjectures, such as 3SUM, combinatorial Boolean matrix multiplication, triangle detection, and multiphase, thus providing a uniform way to prove polynomial hardness results for dynamic algorithms; some of the new proofs are also simpler or even become trivial. The conjecture also leads to stronger and new, non-trivial, hardness results.
A Model for Web-Intelligence Index to Evaluate the Web Intelligence Capacity of Government Web Sites of Sri Lanka
Venue: arXiv cs.CY 2015
Year: 2015

Web intelligence can be considered as a subset of Artificial Intelligence. It uses existing data in web to produce new data, knowledge and wisdom to support decision making and new predictions for web users. Artificial Intelligence is ever changing and evolving field of computer science and it is extensively used in wide array of web based business applications. Although it is used substantially in web based systems in developed countries, it is not examined whether it is being substantially used in Sri Lanka. Every Sri Lankan citizen depends on Public Service more or less throughout his/ her life time and at least more than 3 times: at birth, marriage and death. So providing most of these services to its citizen, Sri Lankan Government uses more or less of its country web portal. This paper presents a model to evaluate web intelligence capability based on weight to key functionalities with respect to web intelligence. The government websites were checked by the proposed criteria to show the potential of using web intelligent technology to provide website based services. The result indicates that the use of web intelligence techniques openly and publicly to provide web based services through government web portal to its citizens is not satisfactory. It also indicates that lack of using the technologies pertaining to web intelligence in the public service web hinders the most of the advantages that citizen and government can gain from such technological involvement.
Key Exchange Trust Evaluation in Peer-to-Peer Sensor Networks with Unconditionally Secure Key Exchange
Venue: arXiv cs.CR 2015
Year: 2015

As the utilization of sensor networks continue to increase, the importance of security becomes more profound. Many industries depend on sensor networks for critical tasks, and a malicious entity can potentially cause catastrophic damage. We propose a new key exchange trust evaluation for peer-to-peer sensor networks, where part of the network has unconditionally secure key exchange. For a given sensor, the higher the portion of channels with unconditionally secure key exchange the higher the trust value. We give a brief introduction to unconditionally secured key exchange concepts and mention current trust measures in sensor networks. We demonstrate the new key exchange trust measure on a hypothetical sensor network using both wired and wireless communication channels.
Semi-supervised Bootstrapping approach for Named Entity Recognition
Venue: arXiv cs.CL 2015
Year: 2015

The aim of Named Entity Recognition (NER) is to identify references of named entities in unstructured documents, and to classify them into pre-defined semantic categories. NER often aids from added background knowledge in the form of gazetteers. However using such a collection does not deal with name variants and cannot resolve ambiguities associated in identifying the entities in context and associating them with predefined categories. We present a semi-supervised NER approach that starts with identifying named entities with a small set of training data. Using the identified named entities, the word and the context features are used to define the pattern. This pattern of each named entity category is used as a seed pattern to identify the named entities in the test set. Pattern scoring and tuple value score enables the generation of the new patterns to identify the named entity categories. We have evaluated the proposed system for English language with the dataset of tagged (IEER) and untagged (CoNLL 2003) named entity corpus and for Tamil language with the documents from the FIRE corpus and yield an average f-measure of 75% for both the languages.