results for au:Huang_L in:cs

- Apr 24 2018 cs.CL arXiv:1804.07889v1Image captioning approaches currently generate descriptions which lack specific information, such as named entities that are involved in the images. In this paper we propose a new task which aims to generate informative image captions, given images and hashtags as input. We propose a simple, but effective approach in which we, first, train a CNN-LSTM model to generate a template caption based on the input image. Then we use a knowledge graph based collective inference algorithm to fill in the template with specific named entities retrieved via the hashtags. Experiments on a new benchmark dataset collected from Flickr show that our model generates news-style image descriptions with much richer information. The METEOR score of our model almost triples the score of the baseline image captioning model on our benchmark dataset, from 4.8 to 13.60.
- Batch Normalization (BN) is capable of accelerating the training of deep models by centering and scaling activations within mini-batches. In this work, we propose Decorrelated Batch Normalization (DBN), which not just centers and scales activations but whitens them. We explore multiple whitening techniques, and find that PCA whitening causes a problem we call stochastic axis swapping, which is detrimental to learning. We show that ZCA whitening does not suffer from this problem, permitting successful learning. DBN retains the desirable qualities of BN and further improves BN's optimization efficiency and generalization ability. We design comprehensive experiments to show that DBN can improve the performance of BN on multilayer perceptrons and convolutional neural networks. Furthermore, we consistently improve the accuracy of residual networks on CIFAR-10, CIFAR-100, and ImageNet.
- We construct a multilingual common semantic space based on distributional semantics, where words from multiple languages are projected into a shared space to enable knowledge and resource transfer across languages. Beyond word alignment, we introduce multiple cluster-level alignments and enforce the word clusters to be consistently distributed across multiple languages. We exploit three signals for clustering: (1) neighbor words in the monolingual word embedding space; (2) character-level information; and (3) linguistic properties (e.g., apposition, locative suffix) derived from linguistic structure knowledge bases available for thousands of languages. We introduce a new cluster-consistent correlational neural network to construct the common semantic space by aligning words as well as clusters. Intrinsic evaluation on monolingual and multilingual QVEC tasks shows our approach achieves significantly higher correlation with linguistic features than state-of-the-art multi-lingual embedding learning methods do. Using low-resource language name tagging as a case study for extrinsic evaluation, our approach achieves up to 24.5\% absolute F-score gain over the state of the art.
- Apr 10 2018 cs.DS arXiv:1804.02530v1We study the problem of constructing $\varepsilon$-coresets for the $(k, z)$-clustering problem in a doubling metric $M(X, d)$. An $\varepsilon$-coreset is a weighted subset $S\subseteq X$ with weight function $w : S \rightarrow \mathbb{R}_{\geq 0}$, such that for any $k$-subset $C \in [X]^k$, it holds that $\sum_{x \in S}{w(x) \cdot d^z(x, C)} \in (1 \pm \varepsilon) \cdot \sum_{x \in X}{d^z(x, C)}$. We present an efficient algorithm that constructs an $\varepsilon$-coreset for the $(k, z)$-clustering problem in $M(X, d)$, where the size of the coreset only depends on the parameters $k, z, \varepsilon$ and the doubling dimension $\mathsf{ddim}(M)$. To the best of our knowledge, this is the first efficient $\varepsilon$-coreset construction of size independent of $|X|$ for general clustering problems in doubling metrics. To this end, we establish the first relation between the doubling dimension of $M(X, d)$ and the shattering dimension (or VC-dimension) of the range space induced by the distance $d$. Such a relation was not known before, since one can easily construct instances in which neither one can be bounded by (some function of) the other. Surprisingly, we show that if we allow a small $(1\pm\epsilon)$-distortion of the distance function $d$, and consider the notion of $\tau$-error probabilistic shattering dimension, we can prove an upper bound of $O( \mathsf{ddim}(M)\cdot \log(1/\varepsilon) +\log\log{\frac{1}{\tau}} )$ for the probabilistic shattering dimension for even weighted doubling metrics. We believe this new relation is of independent interest and may find other applications. We also study the robust coresets and centroid sets in doubling metrics. Our robust coreset construction leads to new results in clustering and property testing, and the centroid sets can be used to accelerate the local search algorithms for clustering problems.
- Mar 19 2018 cs.SE arXiv:1803.06075v2Modeling and analysis of nonfunctional requirements is crucial in automotive systems. EAST-ADL is an architectural language dedicated to safety-critical automotive system design. We have previously modified EAST-ADL to include energy constraints and transformed energy-aware timed (ET) behaviors modeled in SIMULINK/STATEFLOW into UPPAAL models amenable to formal verification. Previous work is extended in this paper by including support for SIMULINK DESIGN VERIFIER (SDV), i.e., the ET constraints are translated into proof objective models that can be verified using SDV. Furthermore, probabilistic extension of EAST-ADL constraints is defined and the semantics of the extended constraints is translated into verifiable UPPAAL models with stochastic semantics for formal verification. A set of mapping rules are proposed to facilitate the guarantee of translation. Verification & Validation are performed on the extended timing and energy constraints using SDV and UPPAAL-SMC. Our approach is demonstrated on a cooperative automotive system case study.
- Mar 19 2018 cs.SE arXiv:1803.06103v2The software development for Cyber-Physical Systems (CPS), e.g., autonomous vehicles, requires both functional and non-functional quality assurance to guarantee that the CPS operates safely and effectively. EAST-ADL is a domain specific architectural language dedicated to safety-critical automotive embedded system design. We have previously modified EAST-ADL to include energy constraints and transformed energy-aware real-time (ERT) behaviors modeled in EAST-ADL/STATEFLOW into UPPAAL models amenable to formal verification. Previous work is extended in this paper by including support for SIMULINK and an integration of Simulink/Stateflow within a same tool-chain. Simulink/Stateflow models are transformed, based on extended ERT constraints in EAST-ADL, into verifiable UPPAAL models with stochastic semantics and integrate the translation with formal statistical analysis techniques: Probabilistic extension of EAST-ADL constraints is defined as a semantics denotation. A set of mapping rules is proposed to facilitate the guarantee of translation. Formal analysis on both functional- and non-functional properties is performed using SIMULINK DESIGN VERIFIER/UPPAAL-SMC. The analysis techniques are validated and demonstrated on the autonomous traffic sign recognition vehicle case study.
- Feb 28 2018 cs.SY arXiv:1802.09921v1We consider the multi-task coordination problem for multi-agent systems under the following objectives: 1. collision avoidance; 2. connectivity maintenance; 3. convergence to desired destinations. The paper focuses on the safety guaranteed region of multi-task coordination (SG-RMTC), i.e., the set of initial states from which all trajectories converge to the desired configuration, while at the same time achieve the multi-task coordination and avoid unsafe sets. In contrast to estimating the domain of attraction via Lyapunov functions, the main underlying idea is to employ the sublevel sets of Lyapunov-like barrier functions to approximate the SG-RMTC. Rather than using fixed Lyapunov-like barrier functions, a systematic way is proposed to search an optimal Lyapunov-like barrier function such that the under-estimate of SG-RMTC is maximized. Numerical examples illustrate the effectiveness of the proposed method.
- Feb 16 2018 cs.CL arXiv:1802.05672v1Traditional event detection methods heavily rely on manually engineered rich features. Recent deep learning approaches alleviate this problem by automatic feature engineering. But such efforts, like tradition methods, have so far only focused on single-token event mentions, whereas in practice events can also be a phrase. We instead use forward-backward recurrent neural networks (FBRNNs) to detect events that can be either words or phrases. To the best our knowledge, this is one of the first efforts to handle multi-word events and also the first attempt to use RNNs for event detection. Experimental results demonstrate that FBRNN is competitive with the state-of-the-art methods on the ACE 2005 and the Rich ERE 2015 event detection tasks.
- Feb 15 2018 cs.CV arXiv:1802.04914v2In this paper, we introduce a web-scale general visual search system deployed in Microsoft Bing. The system accommodates tens of billions of images in the index, with thousands of features for each image, and can respond in less than 200 ms. In order to overcome the challenges in relevance, latency, and scalability in such large scale of data, we employ a cascaded learning-to-rank framework based on various latest deep learning visual features, and deploy in a distributed heterogeneous computing platform. Quantitative and qualitative experiments show that our system is able to support various applications on Bing website and apps.
- Feb 14 2018 cs.AI arXiv:1802.04592v1Bike sharing provides an environment-friendly way for traveling and is booming all over the world. Yet, due to the high similarity of user travel patterns, the bike imbalance problem constantly occurs, especially for dockless bike sharing systems, causing significant impact on service quality and company revenue. Thus, it has become a critical task for bike sharing systems to resolve such imbalance efficiently. We model this problem as a Markov decision process (MDP), which takes both temporal and spatial features into consideration. We propose a novel deep reinforcement learning algorithm called Loss-Reduced Reinforcement Pricing (LRP), which builds upon the deterministic policy gradient algorithm. Different from existing methods that often ignore spatial information and rely heavily on accurate prediction, LRP is embedded with a novel network architecture to incorporate the dependence of neighboring regions, for reducing the training loss in Q-function learning. We conduct extensive experiments to evaluate the performance of the LRP algorithm, based on trajectory data from Mobike, a major Chinese dockless bike sharing company. Results show that LRP performs close to the 24-timeslot look-ahead optimization, and outperforms state-of-the-art methods in both service level and bike distribution. It also transfers well when applied to unseen areas, and can even make additional profit with the given budget. We further propose the first hybrid rebalancing system, which take advantages of both the truck-based and user-based approaches, and outperforms each individual approach.
- One of the services of DSCloud Platform is to provide the global directory service to solve the problems of dispersed, difficult retrieved and isolated information. In this paper, we describe DSCloud Platform's authorization policies and co-operating strategies for articles and comments, and usage scenery for co-editing posts and tables in the platform.
- In this paper, downlink delivery of popular content is optimized with the assistance of wireless cache nodes. Specifically, the requests of one file is modeled as a Poisson point process with finite lifetime, and two downlink transmission modes are considered: (1) the base station multicasts file segments to the requesting users and selected cache nodes; (2) the base station proactively multicasts file segments to the selected cache nodes without requests from users. Hence the cache nodes with decoded files can help to offload the traffic upon the next file request via other air interfaces, e.g. WiFi. Without proactive caching placement, we formulate the downlink traffic offloading as a Markov decision process with random number of stages, and propose a revised Bellman's equation to obtain the optimal control policy. In order to address the prohibitively huge state space, we also introduce a low-complexity sub-optimal solution based on linear approximation of the value functions, where the gap between the approximated value functions and the real ones is bounded analytically. The approximated value functions can be calculated from analytical expressions given the spatial distribution of requesting users. Moreover, we propose a learning-based algorithm to evaluate the approximated value functions for unknown distribution of requesting users. Finally, a proactive caching placement algorithm is introduced to exploit the temporal diversity of shadowing effect. It is shown by simulation that the proposed low-complexity algorithm based on approximated value functions can significantly reduce the resource consumption at the base station, and the proactive caching placement can further improve the performance.
- Motivated by the increasing importance of providing delay-guaranteed services in general computing and communication systems, and the recent wide adoption of learning and prediction in network control, in this work, we consider a general stochastic single-server multi-user system and investigate the fundamental benefit of predictive scheduling in improving timely-throughput, being the rate of packets that are delivered to destinations before their deadlines. By adopting an error rate-based prediction model, we first derive a Markov decision process (MDP) solution to optimize the timely-throughput objective subject to an average resource consumption constraint. Based on a packet-level decomposition of the MDP, we explicitly characterize the optimal scheduling policy and rigorously quantify the timely-throughput improvement due to predictive-service, which scales as $\Theta(p\left[C_{1}\frac{(a-a_{\max}q)}{p-q}\rho^{\tau}+C_{2}(1-\frac{1}{p})\right](1-\rho^{D}))$, where $a, a_{\max}, \rho\in(0, 1), C_1>0, C_2\ge0$ are constants, $p$ is the true-positive rate in prediction, $q$ is the false-negative rate, $\tau$ is the packet deadline and $D$ is the prediction window size. We also conduct extensive simulations to validate our theoretical findings. Our results provide novel insights into how prediction and system parameters impact performance and provide useful guidelines for designing predictive low-latency control algorithms.
- Convolutional neural networks (CNNs) can be applied to graph similarity matching, in which case they are called graph CNNs. Graph CNNs are attracting increasing attention due to their effectiveness and efficiency. However, the existing convolution approaches focus only on regular data forms and require the transfer of the graph or key node neighborhoods of the graph into the same fixed form. During this transfer process, structural information of the graph can be lost, and some redundant information can be incorporated. To overcome this problem, we propose the disordered graph convolutional neural network (DGCNN) based on the mixed Gaussian model, which extends the CNN by adding a preprocessing layer called the disordered graph convolutional layer (DGCL). The DGCL uses a mixed Gaussian function to realize the mapping between the convolution kernel and the nodes in the neighborhood of the graph. The output of the DGCL is the input of the CNN. We further implement a backward-propagation optimization process of the convolutional layer by which we incorporate the feature-learning model of the irregular node neighborhood structure into the network. Thereafter, the optimization of the convolution kernel becomes part of the neural network learning process. The DGCNN can accept arbitrary scaled and disordered neighborhood graph structures as the receptive fields of CNNs, which reduces information loss during graph transformation. Finally, we perform experiments on multiple standard graph datasets. The results show that the proposed method outperforms the state-of-the-art methods in graph classification and retrieval.
- We study the min-cost seed selection problem in online social networks, where the goal is to select a set of seed nodes with the minimum total cost such that the expected number of influenced nodes in the network exceeds a predefined threshold. We propose several algorithms that outperform the previous studies both on the theoretical approximation ratios and on the experimental performance. Under the case where the nodes have heterogeneous costs, our algorithms are the first bi- criteria approximation algorithms with polynomial running time and provable logarithmic performance bounds using a general contagion model. Under the case where the users have uniform costs, our algorithms achieve logarithmic approximation ratio and provable time complexity which is smaller than that of existing algorithms in orders of magnitude. We conduct extensive experiments using real social networks. The experimental results show that, our algorithms significantly outperform the existing algorithms both on the total cost and on the running time, and also scale well to billion-scale networks.
- In this paper, the downlink file transmission within a finite lifetime is optimized with the assistance of wireless cache nodes. Specifically, the number of requests within the lifetime of one file is modeled as a Poisson point process. The base station multicasts files to downlink users and the selected the cache nodes, so that the cache nodes can help to forward the files in the next file request. Thus we formulate the downlink transmission as a Markov decision process with random number of stages, where transmission power and time on each transmission are the control policy. Due to random number of file transmissions, we first proposed a revised Bellman's equation, where the optimal control policy can be derived. In order to address the prohibitively huge state space, we also introduce a low-complexity sub-optimal solution based on an linear approximation of the value function. The approximated value function can be calculated analytically, so that conventional numerical value iteration can be eliminated. Moreover, the gap between the approximated value function and the real value function is bounded analytically. It is shown by simulation that, with the approximated MDP approach, the proposed algorithm can significantly reduce the resource consumption at the base station.
- We study multiwinner voting problems when there is an additional requirement that the selected committee should be fair with respect to attributes such as gender, ethnicity, or political parties. Every setting of an attribute gives rise to a group, and the goal is to ensure that each group is neither over nor under represented in the selected committee. Prior work has largely focused on designing specialized score functions that lead to a precise level of representation with respect to disjoint attributes (e.g., only political affiliation). Here we propose a general algorithmic framework that allows the use of any score function and can guarantee flexible notions of fairness with respect to multiple, non-disjoint attributes (e.g., political affiliation and gender). Technically, we study the complexity of this constrained multiwinner voting problem subject to group-fairness constraints for monotone submodular score functions. We present approximation algorithms and hardness of approximation results for various attribute set structures and score functions.
- Oct 24 2017 cs.DC arXiv:1710.08101v1When there are huge volumes of information dispersing in the various machines, global directory services are required for the users. DSCloud Platform provides the global directory service, in which the directories are created and maintained by the users themselves. In this paper, we describe the DSCloud Platform directory service's functions, authorization, mounting users' local file systems, and usage scenery for education.
- Oct 17 2017 cs.CL arXiv:1710.05094v1Learning phrase representations has been widely explored in many Natural Language Processing (NLP) tasks (e.g., Sentiment Analysis, Machine Translation) and has shown promising improvements. Previous studies either learn non-compositional phrase representations with general word embedding learning techniques or learn compositional phrase representations based on syntactic structures, which either require huge amounts of human annotations or cannot be easily generalized to all phrases. In this work, we propose to take advantage of large-scaled paraphrase database and present a pair-wise gated recurrent units (pairwise-GRU) framework to generate compositional phrase representations. Our framework can be re-used to generate representations for any phrases. Experimental results show that our framework achieves state-of-the-art results on several phrase similarity tasks.
- Oct 10 2017 cs.CL arXiv:1710.02717v1Question classification is an important task with wide applications. However, traditional techniques treat questions as general sentences, ignoring the corresponding answer data. In order to consider answer information into question modeling, we first introduce novel group sparse autoencoders which refine question representation by utilizing group information in the answer set. We then propose novel group sparse CNNs which naturally learn question representation with respect to their answers by implanting group sparse autoencoders into traditional CNNs. The proposed model significantly outperform strong baselines on four datasets.
- Oct 10 2017 cs.CL arXiv:1710.02718v2This paper describes Oregon State University's submissions to the shared WMT'17 task "multimodal translation task I". In this task, all the sentence pairs are image captions in different languages. The key difference between this task and conventional machine translation is that we have corresponding images as additional information for each sentence pair. In this paper, we introduce a simple but effective system which takes an image shared between different languages, feeding it into the both encoding and decoding side. We report our system's performance for English-French and English-German with Flickr30K (in-domain) and MSCOCO (out-of-domain) datasets. Our system achieves the best performance in TER for English-German for MSCOCO dataset.
- Optimizing deep neural networks (DNNs) often suffers from the ill-conditioned problem. We observe that the scaling-based weight space symmetry property in rectified nonlinear network will cause this negative effect. Therefore, we propose to constrain the incoming weights of each neuron to be unit-norm, which is formulated as an optimization problem over Oblique manifold. A simple yet efficient method referred to as projection based weight normalization (PBWN) is also developed to solve this problem. PBWN executes standard gradient updates, followed by projecting the updated weight back to Oblique manifold. This proposed method has the property of regularization and collaborates well with the commonly used batch normalization technique. We conduct comprehensive experiments on several widely-used image datasets including CIFAR-10, CIFAR-100, SVHN and ImageNet for supervised learning over the state-of-the-art convolutional neural networks, such as Inception, VGG and residual networks. The results show that our method is able to improve the performance of DNNs with different architectures consistently. We also apply our method to Ladder network for semi-supervised learning on permutation invariant MNIST dataset, and our method outperforms the state-of-the-art methods: we obtain test errors as 2.52%, 1.06%, and 0.91% with only 20, 50, and 100 labeled samples, respectively.
- Oct 02 2017 cs.CL arXiv:1709.10191v1Sentence-level classification and sequential labeling are two fundamental tasks in language understanding. While these two tasks are usually modeled separately, in reality, they are often correlated, for example in intent classification and slot filling, or in topic classification and named-entity recognition. In order to utilize the potential benefits from their correlations, we propose a jointly trained model for learning the two tasks simultaneously via Long Short-Term Memory (LSTM) networks. This model predicts the sentence-level category and the word-level label sequence from the stepwise output hidden representations of LSTM. We also introduce a novel mechanism of "sparse attention" to weigh words differently based on their semantic relevance to sentence-level classification. The proposed method outperforms baseline models on ATIS and TREC datasets.
- Sep 20 2017 cs.LG arXiv:1709.06079v2Orthogonal matrix has shown advantages in training Recurrent Neural Networks (RNNs), but such matrix is limited to be square for the hidden-to-hidden transformation in RNNs. In this paper, we generalize such square orthogonal matrix to orthogonal rectangular matrix and formulating this problem in feed-forward Neural Networks (FNNs) as Optimization over Multiple Dependent Stiefel Manifolds (OMDSM). We show that the rectangular orthogonal matrix can stabilize the distribution of network activations and regularize FNNs. We also propose a novel orthogonal weight normalization method to solve OMDSM. Particularly, it constructs orthogonal transformation over proxy parameters to ensure the weight matrix is orthogonal and back-propagates gradient information through the transformation during training. To guarantee stability, we minimize the distortions between proxy parameters and canonical weights over all tractable orthogonal transformations. In addition, we design an orthogonal linear module (OLM) to learn orthogonal filter banks in practice, which can be used as an alternative to standard linear module. Extensive experiments demonstrate that by simply substituting OLM for standard linear module without revising any experimental protocols, our method largely improves the performance of the state-of-the-art networks, including Inception and residual networks on CIFAR and ImageNet datasets. In particular, we have reduced the test error of wide residual network on CIFAR-100 from 20.04% to 18.61% with such simple substitution. Our code is available online for result reproduction.
- Sep 14 2017 cs.MM arXiv:1709.04427v1As an efficient image contrast enhancement (CE) tool, adaptive gamma correction (AGC) was previously proposed by relating gamma parameter with cumulative distribution function (CDF) of the pixel gray levels within an image. ACG deals well with most dimmed images, but fails for globally bright images and the dimmed images with local bright regions. Such two categories of brightness-distorted images are universal in real scenarios, such as improper exposure and white object regions. In order to attenuate such deficiencies, here we propose an improved AGC algorithm. The novel strategy of negative images is used to realize CE of the bright images, and the gamma correction modulated by truncated CDF is employed to enhance the dimmed ones. As such, local over-enhancement and structure distortion can be alleviated. Both qualitative and quantitative experimental results show that our proposed method yields consistently good CE results.
- Sep 11 2017 cs.LG arXiv:1709.02664v1Selecting the right web links for a website is important because appropriate links not only can provide high attractiveness but can also increase the website's revenue. In this work, we first show that web links have an intrinsic \emphmulti-level feedback structure. For example, consider a $2$-level feedback web link: the $1$st level feedback provides the Click-Through Rate (CTR) and the $2$nd level feedback provides the potential revenue, which collectively produce the compound $2$-level revenue. We consider the context-free links selection problem of selecting links for a homepage so as to maximize the total compound $2$-level revenue while keeping the total $1$st level feedback above a preset threshold. We further generalize the problem to links with $n~(n\ge2)$-level feedback structure. The key challenge is that the links' multi-level feedback structures are unobservable unless the links are selected on the homepage. To our best knowledge, we are the first to model the links selection problem as a constrained multi-armed bandit problem and design an effective links selection algorithm by learning the links' multi-level structure with provable \emphsub-linear regret and violation bounds. We uncover the multi-level feedback structures of web links in two real-world datasets. We also conduct extensive experiments on the datasets to compare our proposed \textbfLExp algorithm with two state-of-the-art context-free bandit algorithms and show that \textbfLExp algorithm is the most effective in links selection while satisfying the constraint.
- This paper focuses on the non-orthogonal multiple access (NOMA) design for a classical two-user multiple access channel (MAC) with finite-alphabet inputs. We consider practical quadrature amplitude modulation (QAM) constellations at both transmitters, the sizes of which are assumed to be not necessarily identical. We propose to maximize the minimum Euclidean distance of the received sum-constellation with a maximum likelihood (ML) detector by adjusting the scaling factors (i.e., instantaneous transmitted powers and phases) of both users. The formulated problem is a mixed continuous-discrete optimization problem, which is nontrivial to resolve in general. By carefully observing the structure of the objective function, we discover that Farey sequence can be applied to tackle the formulated problem. However, the existing Farey sequence is not applicable when the constellation sizes of the two users are not the same. Motivated by this, we define a new type of Farey sequence, termed punched Farey sequence. Based on this, we manage to achieve a closed-form optimal solution to the original problem by first dividing the entire feasible region into a finite number of Farey intervals and then taking the maximum over all the possible intervals. The resulting sum-constellation is proved to be a regular QAM constellation of a larger size. Moreover, the superiority of NOMA over time-division multiple access (TDMA) in terms of minimum Euclidean distance is rigorously proved. Furthermore, the optimal rate allocation among the two users is obtained in closed-form to further maximize the obtained minimum Euclidean distance of the received signal subject to a total rate constraint. Finally, simulation results are provided to verify our theoretical analysis and demonstrate the merits of the proposed NOMA over existing orthogonal and non-orthogonal designs.
- Sep 01 2017 cs.CL arXiv:1708.09403v1We first present a minimal feature set for transition-based dependency parsing, continuing a recent trend started by Kiperwasser and Goldberg (2016a) and Cross and Huang (2016a) of using bi-directional LSTM features. We plug our minimal feature set into the dynamic-programming framework of Huang and Sagae (2010) and Kuhlmann et al. (2011) to produce the first implementation of worst-case O(n^3) exact decoders for arc-hybrid and arc-eager transition systems. With our minimal features, we also present O(n^3) global training methods. Finally, using ensembles including our new parsers, we achieve the best unlabeled attachment score reported (to our knowledge) on the Chinese Treebank and the "second-best-in-class" result on the English Penn Treebank.
- Aug 30 2017 cs.CL arXiv:1708.08484v1Discourse parsing has long been treated as a stand-alone problem independent from constituency or dependency parsing. Most attempts at this problem are pipelined rather than end-to-end, sophisticated, and not self-contained: they assume gold-standard text segmentations (Elementary Discourse Units), and use external parsers for syntactic features. In this paper we propose the first end-to-end discourse parser that jointly parses in both syntax and discourse levels, as well as the first syntacto-discourse treebank by integrating the Penn Treebank with the RST Treebank. Built upon our recent span-based constituency parser, this joint syntacto-discourse parser requires no preprocessing whatsoever (such as segmentation or feature extraction), achieves the state-of-the-art end-to-end discourse parsing accuracy.
- Long Short-Term Memory (LSTM) is the primary recurrent neural networks architecture for acoustic modeling in automatic speech recognition systems. Residual learning is an efficient method to help neural networks converge easier and faster. In this paper, we propose several types of residual LSTM methods for our acoustic modeling. Our experiments indicate that, compared with classic LSTM, our architecture shows more than 8% relative reduction in Phone Error Rate (PER) on TIMIT tasks. At the same time, our residual fast LSTM approach shows 4% relative reduction in PER on the same task. Besides, we find that all this architecture could have good results on THCHS-30, Librispeech and Switchboard corpora.
- This paper focuses on the design of non-orthogonal multiple access (NOMA) in a classical two-transmitter two-receiver Z-channel, wherein one transmitter sends information to its intended receiver from the direct link while the other transmitter sends information to both receivers from the direct and cross links. Unlike most existing designs using (continuous) Gaussian input distribution, we consider the practical finite-alphabet (i.e., discrete) inputs by assuming that the widely-used quadrature amplitude modulation (QAM) constellations are adopted by both transmitters. To balance the error performance of two receivers, we apply the max-min fairness design criterion in this paper. More specifically, we propose to jointly optimize the scaling factors at both transmitters, which control the minimum Euclidean distance of transmitting constellations, to maximize the smaller minimum Euclidean distance of two resulting constellations at the receivers, subject to an individual average power constraint at each transmitter. The formulated problem is a mixed continuous-discrete optimization problem and is thus intractable in general. By resorting to the Farey sequence, we manage to attain the closed-form expression for the optimal solution to the formulated problem. This is achieved by dividing the overall feasible region of the original optimization problem into a finite number of sub-intervals and deriving the optimal solution in each sub-interval. Through carefully observing the structure of the optimal solutions in all sub-intervals, we obtain compact and closed-form expressions for the optimal solutions to the original problem in three possible scenarios defined by the relative strength of the cross link. Simulation studies are provided to validate our analysis and demonstrate the merits of the proposed design over existing orthogonal or non-orthogonal schemes.
- In this paper, we propose a generic and simple strategy for utilizing stochastic gradient information in optimization. The technique essentially contains two consecutive steps in each iteration: 1) computing and normalizing each block (layer) of the mini-batch stochastic gradient; 2) selecting appropriate step size to update the decision variable (parameter) towards the negative of the block-normalized gradient. We conduct extensive empirical studies on various non-convex neural network optimization problems, including multi-layer perceptron, convolution neural networks and recurrent neural networks. The results indicate the block-normalized gradient can help accelerate the training of neural networks. In particular, we observe that the normalized gradient methods having constant step size with occasionally decay, such as SGD with momentum, have better performance in the deep convolution neural networks, while those with adaptive step sizes, such as Adam, perform better in recurrent neural networks. Besides, we also observe this line of methods can lead to solutions with better generalization properties, which is confirmed by the performance improvement over strong baselines.
- Jul 18 2017 cs.CV arXiv:1707.04677v1This paper aims at task-oriented action prediction, i.e., predicting a sequence of actions towards accomplishing a specific task under a certain scene, which is a new problem in computer vision research. The main challenges lie in how to model task-specific knowledge and integrate it in the learning procedure. In this work, we propose to train a recurrent long-short term memory (LSTM) network for handling this problem, i.e., taking a scene image (including pre-located objects) and the specified task as input and recurrently predicting action sequences. However, training such a network usually requires large amounts of annotated samples for covering the semantic space (e.g., diverse action decomposition and ordering). To alleviate this issue, we introduce a temporal And-Or graph (AOG) for task description, which hierarchically represents a task into atomic actions. With this AOG representation, we can produce many valid samples (i.e., action sequences according with common sense) by training another auxiliary LSTM network with a small set of annotated samples. And these generated samples (i.e., task-oriented action sequences) effectively facilitate training the model for task-oriented action prediction. In the experiments, we create a new dataset containing diverse daily tasks and extensively evaluate the effectiveness of our approach.
- Jul 05 2017 cs.CL arXiv:1707.01066v1Most previous event extraction studies have relied heavily on features derived from annotated event mentions, thus cannot be applied to new event types without annotation effort. In this work, we take a fresh look at event extraction and model it as a grounding problem. We design a transferable neural architecture, mapping event mentions and types jointly into a shared semantic space using structural and compositional neural networks, where the type of each event mention can be determined by the closest of all candidate types . By leveraging (1)~available manual annotations for a small set of existing event types and (2)~existing event ontologies, our framework applies to new event types without requiring additional annotation. Experiments on both existing event types (e.g., ACE, ERE) and new event types (e.g., FrameNet) demonstrate the effectiveness of our approach. \textitWithout any manual annotations for 23 new event types, our zero-shot framework achieved performance comparable to a state-of-the-art supervised model which is trained from the annotations of 500 event mentions.
- Jul 05 2017 cs.CL arXiv:1707.01075v1Slot Filling (SF) aims to extract the values of certain types of attributes (or slots, such as person:cities\_of\_residence) for a given entity from a large collection of source documents. In this paper we propose an effective DNN architecture for SF with the following new strategies: (1). Take a regularized dependency graph instead of a raw sentence as input to DNN, to compress the wide contexts between query and candidate filler; (2). Incorporate two attention mechanisms: local attention learned from query and candidate filler, and global attention learned from external knowledge bases, to guide the model to better select indicative contexts to determine slot type. Experiments show that this framework outperforms state-of-the-art on both relation extraction (16\% absolute F-score gain) and slot filling validation for each individual system (up to 8.5\% absolute F-score gain).
- Recent advances in imaging sensors and digital light projection technology have facilitated a rapid progress in 3D optical sensing, enabling 3D surfaces of complex-shaped objects to be captured with improved resolution and accuracy. However, due to the large number of projection patterns required for phase recovery and disambiguation, the maximum fame rates of current 3D shape measurement techniques are still limited to the range of hundreds of frames per second (fps). Here, we demonstrate a new 3D dynamic imaging technique, Micro Fourier Transform Profilometry ($\mu$FTP), which can capture 3D surfaces of transient events at up to 10,000 fps based on our newly developed high-speed fringe projection system. Compared with existing techniques, $\mu$FTP has the prominent advantage of recovering an accurate, unambiguous, and dense 3D point cloud with only two projected patterns. Furthermore, the phase information is encoded within a single high-frequency fringe image, thereby allowing motion-artifact-free reconstruction of transient events with temporal resolution of 50 microseconds. To show $\mu$FTP's broad utility, we use it to reconstruct 3D videos of 4 transient scenes: vibrating cantilevers, rotating fan blades, bullet fired from a toy gun, and balloon's explosion triggered by a flying dart, which were previously difficult or even unable to be captured with conventional approaches.
- We study two important SVM variants: hard-margin SVM (for linearly separable cases) and $\nu$-SVM (for linearly non-separable cases). We propose new algorithms from the perspective of saddle point optimization. Our algorithms achieve $(1-\epsilon)$-approximations with running time $\tilde{O}(nd+n\sqrt{d / \epsilon})$ for both variants, where $n$ is the number of points and $d$ is the dimensionality. To the best of our knowledge, the current best algorithm for $\nu$-SVM is based on quadratic programming approach which requires $\Omega(n^2 d)$ time in worst case~\citejoachims1998making,platt199912. In the paper, we provide the first nearly linear time algorithm for $\nu$-SVM. The current best algorithm for hard margin SVM achieved by Gilbert algorithm~\citegartner2009coresets requires $O(nd / \epsilon )$ time. Our algorithm improves the running time by a factor of $\sqrt{d}/\sqrt{\epsilon}$. Moreover, our algorithms can be implemented in the distributed settings naturally. We prove that our algorithms require $\tilde{O}(k(d +\sqrt{d/\epsilon}))$ communication cost, where $k$ is the number of clients, which almost matches the theoretical lower bound. Numerical experiments support our theory and show that our algorithms converge faster on high dimensional, large and dense data sets, as compared to previous methods.
- We investigate the problem of stochastic network optimization in the presence of imperfect state prediction and non-stationarity. Based on a novel distribution-accuracy curve prediction model, we develop the predictive learning-aided control (PLC) algorithm, which jointly utilizes historic and predicted network state information for decision making. PLC is an online algorithm that requires zero a-prior system statistical information, and consists of three key components, namely sequential distribution estimation and change detection, dual learning, and online queue-based control. Specifically, we show that PLC simultaneously achieves good long-term performance, short-term queue size reduction, accurate change detection, and fast algorithm convergence. In particular, for stationary networks, PLC achieves a near-optimal $[O(\epsilon)$, $O(\log(1/\epsilon)^2)]$ utility-delay tradeoff. For non-stationary networks, \plc obtains an $[O(\epsilon), O(\log^2(1/\epsilon)$ $+ \min(\epsilon^{c/2-1}, e_w/\epsilon))]$ utility-backlog tradeoff for distributions that last $\Theta(\frac{\max(\epsilon^{-c}, e_w^{-2})}{\epsilon^{1+a}})$ time, where $e_w$ is the prediction accuracy and $a=\Theta(1)>0$ is a constant (the Backpressue algorithm \citeneelynowbook requires an $O(\epsilon^{-2})$ length for the same utility performance with a larger backlog). Moreover, PLC detects distribution change $O(w)$ slots faster with high probability ($w$ is the prediction size) and achieves an $O(\min(\epsilon^{-1+c/2}, e_w/\epsilon)+\log^2(1/\epsilon))$ convergence time. Our results demonstrate that state prediction (even imperfect) can help (i) achieve faster detection and convergence, and (ii) obtain better utility-delay tradeoffs.
- We consider the stochastic composition optimization problem proposed in \citewang2017stochastic, which has applications ranging from estimation to statistical and machine learning. We propose the first ADMM-based algorithm named com-SVR-ADMM, and show that com-SVR-ADMM converges linearly for strongly convex and Lipschitz smooth objectives, and has a convergence rate of $O( \log S/S)$, which improves upon the $O(S^{-4/9})$ rate in \citewang2016accelerating when the objective is convex and Lipschitz smooth. Moreover, com-SVR-ADMM possesses a rate of $O(1/\sqrt{S})$ when the objective is convex but without Lipschitz smoothness. We also conduct experiments and show that it outperforms existing algorithms.
- Although hash function learning algorithms have achieved great success in recent years, most existing hash models are off-line, which are not suitable for processing sequential or online data. To address this problem, this work proposes an online hash model to accommodate data coming in stream for online learning. Specifically, a new loss function is proposed to measure the similarity loss between a pair of data samples in hamming space. Then, a structured hash model is derived and optimized in a passive-aggressive way. Theoretical analysis on the upper bound of the cumulative loss for the proposed online hash model is provided. Furthermore, we extend our online hashing from a single-model to a multi-model online hashing that trains multiple models so as to retain diverse online hashing models in order to avoid biased update. The competitive efficiency and effectiveness of the proposed online hash models are verified through extensive experiments on several large-scale datasets as compared to related hashing methods.
- Many of the existing methods for learning joint embedding of images and text use only supervised information from paired images and its textual attributes. Taking advantage of the recent success of unsupervised learning in deep neural networks, we propose an end-to-end learning framework that is able to extract more robust multi-modal representations across domains. The proposed method combines representation learning models (i.e., auto-encoders) together with cross-domain learning criteria (i.e., Maximum Mean Discrepancy loss) to learn joint embeddings for semantic and visual features. A novel technique of unsupervised-data adaptation inference is introduced to construct more comprehensive embeddings for both labeled and unlabeled data. We evaluate our method on Animals with Attributes and Caltech-UCSD Birds 200-2011 dataset with a wide range of applications, including zero and few-shot image recognition and retrieval, from inductive to transductive settings. Empirically, we show that our framework improves over the current state of the art on many of the considered tasks.
- Feb 27 2017 cs.DS arXiv:1702.07435v1In recent years, the capacitated center problems have attracted a lot of research interest. Given a set of vertices $V$, we want to find a subset of vertices $S$, called centers, such that the maximum cluster radius is minimized. Moreover, each center in $S$ should satisfy some capacity constraint, which could be an upper or lower bound on the number of vertices it can serve. Capacitated $k$-center problems with one-sided bounds (upper or lower) have been well studied in previous work, and a constant factor approximation was obtained. We are the first to study the capacitated center problem with both capacity lower and upper bounds (with or without outliers). We assume each vertex has a uniform lower bound and a non-uniform upper bound. For the case of opening exactly $k$ centers, we note that a generalization of a recent LP approach can achieve constant factor approximation algorithms for our problems. Our main contribution is a simple combinatorial algorithm for the case where there is no cardinality constraint on the number of open centers. Our combinatorial algorithm is simpler and achieves better constant approximation factor compared to the LP approach.
- Ensemble learning has been widely employed by mobile applications, ranging from environmental sensing to activity recognitions. One of the fundamental issue in ensemble learning is the trade-off between classification accuracy and computational costs, which is the goal of ensemble pruning. During crowdsourcing, the centralized aggregator releases ensemble learning models to a large number of mobile participants for task evaluation or as the crowdsourcing learning results, while different participants may seek for different levels of the accuracy-cost trade-off. However, most of existing ensemble pruning approaches consider only one identical level of such trade-off. In this study, we present an efficient ensemble pruning framework for personalized accuracy-cost trade-offs via multi-objective optimization. Specifically, for the commonly used linear-combination style of the trade-off, we provide an objective-mixture optimization to further reduce the number of ensemble candidates. Experimental results show that our framework is highly efficient for personalized ensemble pruning, and achieves much better pruning performance with objective-mixture optimization when compared to state-of-art approaches.
- It is known that certain structures of the signal in addition to the standard notion of sparsity (called structured sparsity) can improve the sample complexity in several compressive sensing applications. Recently, Hegde et al. proposed a framework, called approximation-tolerant model-based compressive sensing, for recovering signals with structured sparsity. Their framework requires two oracles, the head- and the tail-approximation projection oracles. The two oracles should return approximate solutions in the model which is closest to the query signal. In this paper, we consider two structured sparsity models and obtain improved projection algorithms. The first one is the tree sparsity model, which captures the support structure in the wavelet decomposition of piecewise-smooth signals. We propose a linear time $(1-\epsilon)$-approximation algorithm for head-approximation projection and a linear time $(1+\epsilon)$-approximation algorithm for tail-approximation projection. The best previous result is an $\tilde{O}(n\log n)$ time bicriterion approximation algorithm (meaning that their algorithm may return a solution of sparsity larger than $k$) by Hegde et al. Our result provides an affirmative answer to the open problem mentioned in the survey of Hegde and Indyk. As a corollary, we can recover a constant approximate $k$-sparse signal. The other is the Constrained Earth Mover Distance (CEMD) model, which is useful to model the situation where the positions of the nonzero coefficients of a signal do not change significantly as a function of spatial (or temporal) locations. We obtain the first single criterion constant factor approximation algorithm for the head-approximation projection. The previous best known algorithm is a bicriterion approximation. Using this result, we can get a faster constant approximation algorithm with fewer measurements for the recovery problem in CEMD model.
- OR multi-access channel is a simple model where the channel output is the Boolean OR among the Boolean channel inputs. We revisit this model, showing that employing Bloom filter, a randomized data structure, as channel inputs achieves its capacity region with joint decoding and the symmetric sum rate of $\ln 2$ bits per channel use without joint decoding. We then proceed to the "many-access" regime where the number of potential users grows without bound, treating both activity recognition and message transmission problems, establishing scaling laws which are optimal within a constant factor, based on Bloom filter channel inputs.
- Jan 10 2017 cs.OH arXiv:1701.01771v1This research was to design a 2.4 GHz class E Power Amplifier (PA) for health care, with 0.18um Semiconductor Manufacturing International Corporation CMOS technology by using Cadence software. And also RF switch was designed at cadence software with power Jazz 180nm SOI process. The ultimate goal for such application is to reach high performance and low cost, and between high performance and low power consumption design. This paper introduces the design of a 2.4GHz class E power amplifier and RF switch design. PA consists of cascade stage with negative capacitance. This power amplifier can transmit 16dBm output power to a 50\Omega load. The performance of the power amplifier and switch meet the specification requirements of the desired.
- Jan 06 2017 cs.CL arXiv:1701.01126v1Deep learning techniques are increasingly popular in the textual entailment task, overcoming the fragility of traditional discrete models with hard alignments and logics. In particular, the recently proposed attention models (Rocktäschel et al., 2015; Wang and Jiang, 2015) achieves state-of-the-art accuracy by computing soft word alignments between the premise and hypothesis sentences. However, there remains a major limitation: this line of work completely ignores syntax and recursion, which is helpful in many traditional efforts. We show that it is beneficial to extend the attention model to tree nodes between premise and hypothesis. More importantly, this subtree-level attention reveals information about entailment relation. We study the recursive composition of this subtree-level entailment relation, which can be viewed as a soft version of the Natural Logic framework (MacCartney and Manning, 2009). Experiments show that our structured attention and entailment composition model can correctly identify and infer entailment relations from the bottom up, and bring significant improvements in accuracy.
- We develop a framework to uncover and analyze dynamical anomalies from massive, nonlinear and non-stationary time series data. The framework consists of three steps: preprocessing of massive data sets to eliminate erroneous data segments, application of the empirical mode decomposition and Hilbert transform paradigm to obtain the fundamental components embedded in the time series at distinct time scales, and statistical/scaling analysis of the components. As a case study, we apply our framework to detecting and characterizing high frequency oscillations (HFOs) from a big database of rat EEG recordings. We find a striking phenomenon: HFOs exhibit on-off intermittency that can be quantified by algebraic scaling laws. Our framework can be generalized to big data-related problems in other fields such as large-scale sensor data and seismic data analysis.
- Dec 21 2016 cs.CL arXiv:1612.06475v1Parsing accuracy using efficient greedy transition systems has improved dramatically in recent years thanks to neural networks. Despite striking results in dependency parsing, however, neural models have not surpassed state-of-the-art approaches in constituency parsing. To remedy this, we introduce a new shift-reduce system whose stack contains merely sentence spans, represented by a bare minimum of LSTM features. We also design the first provably optimal dynamic oracle for constituency parsing, which runs in amortized O(1) time, compared to O(n^3) oracles for standard dependency parsing. Training with this oracle, we achieve the best F1 scores on both English and French of any parser that does not use reranking or external data.
- Many standard robotic platforms are equipped with at least a fixed 2D laser range finder and a monocular camera. Although those platforms do not have sensors for 3D depth sensing capability, knowledge of depth is an essential part in many robotics activities. Therefore, recently, there is an increasing interest in depth estimation using monocular images. As this task is inherently ambiguous, the data-driven estimated depth might be unreliable in robotics applications. In this paper, we have attempted to improve the precision of monocular depth estimation by introducing 2D planar observation from the remaining laser range finder without extra cost. Specifically, we construct a dense reference map from the sparse laser range data, redefining the depth estimation task as estimating the distance between the real and the reference depth. To solve the problem, we construct a novel residual of residual neural network, and tightly combine the classification and regression losses for continuous depth estimation. Experimental results suggest that our method achieves considerable promotion compared to the state-of-the-art methods on both NYUD2 and KITTI, validating the effectiveness of our method on leveraging the additional sensory information. We further demonstrate the potential usage of our method in obstacle avoidance where our methodology provides comprehensive depth information compared to the solution using monocular camera or 2D laser range finder alone.
- Oct 31 2016 cs.DC arXiv:1610.09190v1This paper presents a distributed search engine based on semantic P2P Networks. The user's computers join the domains in which user wants to share information in semantic P2P networks which is domain specific virtual tree (VIRGO ). Each user computer contains search engine which indexes the domain specific information on local computer or Internet. We can get all search information through P2P message provided by all joined computers. By companies' effort, we have implemented a prototype of distributed search engine, which demonstrates easily retrieving domain-related information provided by joined computers .
- Oct 31 2016 cs.CR arXiv:1610.09231v1This paper presents an integrity checker of JAVA P2P distributed system with auto source code composition. JAVA distributed system must guarantee the integrity of program itself and the system components of JAVA virtual machine against attackers, hackers, spies, cheaters, conspirators, etc. There are lots of trusted computing methods to guarantee the integrity of the system. We here present a novel method using just-in-time auto source code composition to generate autocheck class for integrity measure and encrypt of integrity reporting. By companies' effort, we have implemented and use it in DSCloud platform.
- In this work, we propose a multi-layer market for vehicle-to-grid energy trading. In the macro layer, we consider a double auction mechanism, under which the utility company act as an auctioneer and energy buyers and sellers interact. This double auction mechanism is strategy-proof and converges asymptotically. In the micro layer, the aggregators, which are the sellers in the macro layer, are paid with commissions to sell the energy of plug-in hybrid electric vehicles (PHEVs) and to maximize their utilities. We analyze the interaction between the macro and micro layers and study some simplified cases. Depending on the elasticity of supply and demand, the utility is analyzed under different scenarios. Simulation results show that our approach can significantly increase the utility of PHEVs.
- Sep 06 2016 cs.NI arXiv:1609.01101v1The aim of our work is to evaluate the performance of non-beacon IEEE 802.15.4 networks with acknowledgement (ACK) mode and retransmission limits in a finer time unit. Moreover, we predict network performance parameters using backpropagation artificial neural networks (BP-ANNs) with respect to a given quality of service for real-world applications. Therefore, our proposed methods can assist the deployment of a star network with its performance specified in a more practical way. First, the discrete time Markov chain model and M/M/1/k queue are used to describe the full unslotted carrier sense multiple access with collision avoidance (CSMA/CA) algorithm in a non-beacon network. Considering MAC buffer size, unsaturated traffic, and saturated traffic, we build three analytical models to derive eight important performance metrics, e.g., throughput, delay, and reliability. In addition, extensive simulation results show the accuracy of the analytical models in throughput and reliability. Finally, we use the analytical data to train the BP-ANNs models to predict the key parameters such as node number and delay. All results from the simulation data used to test the BP-ANNs show the accuracy these models. Thus, these methods and results can be used to deploy star networks in application environments.
- Consider statistical learning (e.g. discrete distribution estimation) with local $\epsilon$-differential privacy, which preserves each data provider's privacy locally, we aim to optimize statistical data utility under the privacy constraints. Specifically, we study maximizing mutual information between a provider's data and its private view, and give the exact mutual information bound along with an attainable mechanism: $k$-subset mechanism as results. The mutual information optimal mechanism randomly outputs a size $k$ subset of the original data domain with delicate probability assignment, where $k$ varies with the privacy level $\epsilon$ and the data domain size $d$. After analysing the limitations of existing local private mechanisms from mutual information perspective, we propose an efficient implementation of the $k$-subset mechanism for discrete distribution estimation, and show its optimality guarantees over existing approaches.
- Jul 25 2016 cs.LG arXiv:1607.06657v4We propose a novel support vector regression approach called e-Distance Weighted Support Vector Regression (e-DWSVR).e-DWSVR specifically addresses two challenging issues in support vector regression: first, the process of noisy data; second, how to deal with the situation when the distribution of boundary data is different from that of the overall data. The proposed e-DWSVR optimizes the minimum margin and the mean of functional margin simultaneously to tackle these two issues. In addition, we use both dual coordinate descent (CD) and averaged stochastic gradient descent (ASGD) strategies to make e-DWSVR scalable to large scale problems. We report promising results obtained by e-DWSVR in comparison with existing methods on several benchmark datasets.
- Jul 19 2016 cs.CG arXiv:1607.04989v2Solving geometric optimization problems over uncertain data have become increasingly important in many applications and have attracted a lot of attentions in recent years. In this paper, we study two important geometric optimization problems, the $k$-center problem and the $j$-flat-center problem, over stochastic/uncertain data points in Euclidean spaces. For the stochastic $k$-center problem, we would like to find $k$ points in a fixed dimensional Euclidean space, such that the expected value of the $k$-center objective is minimized. For the stochastic $j$-flat-center problem, we seek a $j$-flat (i.e., a $j$-dimensional affine subspace) such that the expected value of the maximum distance from any point to the $j$-flat is minimized. We consider both problems under two popular stochastic geometric models, the existential uncertainty model, where the existence of each point may be uncertain, and the locational uncertainty model, where the location of each point may be uncertain. We provide the first PTAS (Polynomial Time Approximation Scheme) for both problems under the two models. Our results generalize the previous results for stochastic minimum enclosing ball and stochastic enclosing cylinder.
- Jun 22 2016 cs.CL arXiv:1606.06406v1Recently, neural network approaches for parsing have largely automated the combination of individual features, but still rely on (often a larger number of) atomic features created from human linguistic intuition, and potentially omitting important global context. To further reduce feature engineering to the bare minimum, we use bi-directional LSTM sentence representations to model a parser state with only three sentence positions, which automatically identifies important aspects of the entire sentence. This model achieves state-of-the-art results among greedy dependency parsers for English. We also introduce a novel transition system for constituency parsing which does not require binarization, and together with the above architecture, achieves state-of-the-art results among greedy parsers for both English and Chinese.
- May 10 2016 cs.OH arXiv:1605.02455v1The objective of this research was to design a 2.4 GHz class AB Power Amplifier, with 0.18 um SMIC CMOS technology by using Cadence software, for health care applications. The ultimate goal for such application is to minimize the trade-offs between performance and cost, and between performance and low power consumption design. The performance of the power amplifier meets the specification requirements of the desired.
- Phase retrieval has been mainly considered in the presence of Gaussian noise. However, the performance of the algorithms proposed under the Gaussian noise model severely degrades when grossly corrupted data, i.e., outliers, exist. This paper investigates techniques for phase retrieval in the presence of heavy-tailed noise -- which is considered a better model for situations where outliers exist. An $\ell_p$-norm ($0<p<2$) based estimator is proposed for fending against such noise, and two-block inexact alternating optimization is proposed as the algorithmic framework to tackle the resulting optimization problem. Two specific algorithms are devised by exploring different local approximations within this framework. Interestingly, the core conditional minimization steps can be interpreted as iteratively reweighted least squares and gradient descent. Convergence properties of the algorithms are discussed, and the Cramér-Rao bound (CRB) is derived. Simulations demonstrate that the proposed algorithms approach the CRB and outperform state-of-the-art algorithms in heavy-tailed noise.
- May 03 2016 cs.PF arXiv:1605.00559v1We consider the peak age-of-information (PAoI) in an M/M/1 queueing system with packet delivery error, i.e., update packets can get lost during transmissions to their destination. We focus on two types of policies, one is to adopt Last-Come-First-Served (LCFS) scheduling, and the other is to utilize retransmissions, i.e., keep transmitting the most recent packet. Both policies can effectively avoid the queueing delay of a busy channel and ensure a small PAoI. Exact PAoI expressions under both policies with different error probabilities are derived, including First-Come-First-Served (FCFS), LCFS with preemptive priority, LCFS with non-preemptive priority, Retransmission with preemptive priority, and Retransmission with non-preemptive priority. Numerical results obtained from analysis and simulation are presented to validate our results.
- Apr 07 2016 cs.GT arXiv:1604.01627v5The growth of the sharing economy is driven by the emergence of sharing platforms, e.g., Uber and Lyft, that match owners looking to share their resources with customers looking to rent them. The design of such platforms is a complex mixture of economics and engineering, and how to "optimally" design such platforms is still an open problem. In this paper, we focus on the design of prices and subsidies in sharing platforms. Our results provide insights into the tradeoff between revenue maximizing prices and social welfare maximizing prices. Specifically, we introduce a novel model of sharing platforms and characterize the profit and social welfare maximizing prices in this model. Further, we bound the efficiency loss under profit maximizing prices, showing that there is a strong alignment between profit and efficiency in practical settings. Our results highlight that the revenue of platforms may be limited in practice due to supply shortages; thus platforms have a strong incentive to encourage sharing via subsidies. We provide an analytic characterization of when such subsidies are valuable and show how to optimize the size of the subsidy provided. Finally, we validate the insights from our analysis using data from Didi Chuxing, the largest ridesharing platform in China.
- Apr 07 2016 cs.GT arXiv:1604.01672v1In this paper, we investigate the effect of brand in market competition. Specifically, we propose a variant Hotelling model where companies and customers are represented by points in an Euclidean space, with axes being product features. $N$ companies compete to maximize their own profits by optimally choosing their prices, while each customer in the market, when choosing sellers, considers the sum of product price, discrepancy between product feature and his preference, and a company's brand name, which is modeled by a function of its market area of the form $-\beta\cdot\text{(Market Area)}^q$, where $\beta$ captures the brand influence and $q$ captures how market share affects the brand. By varying the parameters $\beta$ and $q$, we derive existence results of Nash equilibrium and equilibrium market prices and shares. In particular, we prove that pure Nash equilibrium always exists when $q=0$ for markets with either one and two dominating features, and it always exists in a single dominating feature market when market affects brand name linearly, i.e., $q=1$. Moreover, we show that at equilibrium, a company's price is proportional to its market area over the competition intensity with its neighbors, a result that quantitatively reconciles the common belief of a company's pricing power. We also study an interesting "wipe out" phenomenon that only appears when $q>0$, which is similar to the "undercut" phenomenon in the Hotelling model, where companies may suddenly lose the entire market area with a small price increment. Our results offer novel insight into market pricing and positioning under competition with brand effect.
- Recent research has shown great progress on fine-grained entity typing. Most existing methods require pre-defining a set of types and training a multi-class classifier from a large labeled data set based on multi-level linguistic features. They are thus limited to certain domains, genres and languages. In this paper, we propose a novel unsupervised entity typing framework by combining symbolic and distributional semantics. We start from learning general embeddings for each entity mention, compose the embeddings of specific contexts using linguistic structures, link the mention to knowledge bases and learn its related knowledge representations. Then we develop a novel joint hierarchical clustering and linking algorithm to type all mentions using these representations. This framework doesn't rely on any annotated data, predefined typing schema, or hand-crafted features, therefore it can be quickly adapted to a new domain, genre and language. Furthermore, it has great flexibility at incorporating linguistic structures (e.g., Abstract Meaning Representation (AMR), dependency relations) to improve specific context representation. Experiments on genres (news and discussion forum) show comparable performance with state-of-the-art supervised typing systems trained from a large amount of labeled data. Results on various languages (English, Chinese, Japanese, Hausa, and Yoruba) and domains (general and biomedical) demonstrate the portability of our framework.
- Mar 11 2016 cs.CR arXiv:1603.03086v2Hardware-based malware detectors (HMDs) are a key emerging technology to build trustworthy computing platforms, especially mobile platforms. Quantifying the efficacy of HMDs against malicious adversaries is thus an important problem. The challenge lies in that real-world malware typically adapts to defenses, evades being run in experimental settings, and hides behind benign applications. Thus, realizing the potential of HMDs as a line of defense - that has a small and battery-efficient code base - requires a rigorous foundation for evaluating HMDs. To this end, we introduce EMMA - a platform to evaluate the efficacy of HMDs for mobile platforms. EMMA deconstructs malware into atomic, orthogonal actions and introduces a systematic way of pitting different HMDs against a diverse subset of malware hidden inside benign applications. EMMA drives both malware and benign programs with real user-inputs to yield an HMD's effective operating range - i.e., the malware actions a particular HMD is capable of detecting. We show that small atomic actions, such as stealing a Contact or SMS, have surprisingly large hardware footprints, and use this insight to design HMD algorithms that are less intrusive than prior work and yet perform 24.7% better. Finally, EMMA brings up a surprising new result - obfuscation techniques used by malware to evade static analyses makes them more detectable using HMDs.
- Increasing threats of global warming and climate changes call for an energy-efficient and sustainable design of future wireless communication systems. To this end, a novel two-scale stochastic control framework is put forth for smart-grid powered coordinated multi-point (CoMP) systems. Taking into account renewable energy sources (RES), dynamic pricing, two-way energy trading facilities and imperfect energy storage devices, the energy management task is formulated as an infinite-horizon optimization problem minimizing the time-average energy transaction cost, subject to the users' quality of service (QoS) requirements. Leveraging the Lyapunov optimization approach as well as the stochastic subgradient method, a two-scale online control (TS-OC) approach is developed for the resultant smart-grid powered CoMP systems. Using only historical data, the proposed TS-OC makes online control decisions at two timescales, and features a provably feasible and asymptotically near-optimal solution. Numerical tests further corroborate the theoretical analysis, and demonstrate the merits of the proposed approach.
- Dec 22 2015 cs.NI arXiv:1512.06428v2The explosive growth of global mobile traffic has lead to a rapid growth in the energy consumption in communication networks. In this paper, we focus on the energy-aware design of the network selection, subchannel, and power allocation in cellular and Wi-Fi networks, while taking into account the traffic delay of mobile users. The problem is particularly challenging due to the two-timescale operations for the network selection (large timescale) and subchannel and power allocation (small timescale). Based on the two-timescale Lyapunov optimization technique, we first design an online Energy-Aware Network Selection and Resource Allocation (ENSRA) algorithm. The ENSRA algorithm yields a power consumption within O(1/V) bound of the optimal value, and guarantees an O(V) traffic delay for any positive control parameter V. Motivated by the recent advancement in the accurate estimation and prediction of user mobility, channel conditions, and traffic demands, we further develop a novel predictive Lyapunov optimization technique to utilize the predictive information, and propose a Predictive Energy-Aware Network Selection and Resource Allocation (P-ENSRA) algorithm. We characterize the performance bounds of P-ENSRA in terms of the power-delay tradeoff theoretically. To reduce the computational complexity, we finally propose a Greedy Predictive Energy-Aware Network Selection and Resource Allocation (GP-ENSRA) algorithm, where the operator solves the problem in P-ENSRA approximately and iteratively. Numerical results show that GP-ENSRA significantly improves the power-delay performance over ENSRA in the large delay regime. For a wide range of system parameters, GP-ENSRA reduces the traffic delay over ENSRA by 20~30% under the same power consumption.
- Oct 27 2015 cs.CR arXiv:1510.07338v2We present and evaluate a large-scale malware detection system integrating machine learning with expert reviewers, treating reviewers as a limited labeling resource. We demonstrate that even in small numbers, reviewers can vastly improve the system's ability to keep pace with evolving threats. We conduct our evaluation on a sample of VirusTotal submissions spanning 2.5 years and containing 1.1 million binaries with 778GB of raw feature data. Without reviewer assistance, we achieve 72% detection at a 0.5% false positive rate, performing comparable to the best vendors on VirusTotal. Given a budget of 80 accurate reviews daily, we improve detection to 89% and are able to detect 42% of malicious binaries undetected upon initial submission to VirusTotal. Additionally, we identify a previously unnoticed temporal inconsistency in the labeling of training datasets. We compare the impact of training labels obtained at the same time training data is first seen with training labels obtained months later. We find that using training labels obtained well after samples appear, and thus unavailable in practice for current training data, inflates measured detection by almost 20 percentage points. We release our cluster-based implementation, as well as a list of all hashes in our evaluation and 3% of our entire dataset.
- Oct 15 2015 cs.DS arXiv:1510.04099v1Markov Chain Monte Carlo (MCMC) method is a widely used algorithm design scheme with many applications. To make efficient use of this method, the key step is to prove that the Markov chain is rapid mixing. Canonical paths is one of the two main tools to prove rapid mixing. However, there are much fewer success examples comparing to coupling, the other main tool. The main reason is that there is no systematic approach or general recipe to design canonical paths. Building up on a previous exploration by McQuillan, we develop a general theory to design canonical paths for MCMC: We reduce the task of designing canonical paths to solving a set of linear equations, which can be automatically done even by a machine. Making use of this general approach, we obtain fully polynomial-time randomized approximation schemes (FPRAS) for counting the number of $b$-matching with $b\leq 7$ and $b$-edge-cover with $b\leq 2$. They are natural generalizations of matchings and edge covers for graphs. No polynomial time approximation was previously known for these problems.
- Reconstructing a signal from squared linear (rank-one quadratic) measurements is a challenging problem with important applications in optics and imaging, where it is known as phase retrieval. This paper proposes two new phase retrieval algorithms based on non-convex quadratically constrained quadratic programming (QCQP) formulations, and a recently proposed approximation technique dubbed feasible point pursuit (FPP). The first is designed for uniformly distributed bounded measurement errors, such as those arising from high-rate quantization (B-FPP). The second is designed for Gaussian measurement errors, using a least squares criterion (LS-FPP). Their performance is measured against state-of-the-art algorithms and the Cramér-Rao bound (CRB), which is also derived here. Simulations show that LS-FPP outperforms the state-of-art and operates close to the CRB. Compact CRB expressions, properties, and insights are obtained by explicitly computing the CRB in various special cases -- including when the signal of interest admits a sparse parametrization, using harmonic retrieval as an example.