OpenRaiser/Intern-Atlas huggingface dataset:
A Deeper Look into Sarcastic Tweets Using Deep Convolutional Neural Networks
Venue: arXiv cs.CL 2017
Year: 2017

Sarcasm detection is a key task for many natural language processing tasks. In sentiment analysis, for example, sarcasm can flip the polarity of an "apparently positive" sentence and, hence, negatively affect polarity detection performance. To date, most approaches to sarcasm detection have treated the task primarily as a text categorization problem. Sarcasm, however, can be expressed in very subtle ways and requires a deeper understanding of natural language that standard text categorization techniques cannot grasp. In this work, we develop models based on a pre-trained convolutional neural network for extracting sentiment, emotion and personality features for sarcasm detection. Such features, along with the network's baseline features, allow the proposed models to outperform the state of the art on benchmark datasets. We also address the often ignored generalizability issue of classifying data that have not been seen by the models at learning phase.
Anchor Free IP Mobility
Venue: arXiv cs.NI 2017
Year: 2017

Efficient mobility management techniques are critical in providing seamless connectivity and session continuity between a mobile node and the network during its movement. Current mobility management solutions generally require a central entity in the network core, tracking IP address movement and anchoring traffic from source to destination through point-to-point tunnels. Intuitively, this approach suffers from scalability limitations as it creates bottlenecks in the network, due to sub-optimal routing via the anchor point. Meanwhile, alternative anchorless, solutions are not feasible due to the current limitations of the IP semantics, which strongly ties addressing information to location. In contrast, novel path-based forwarding solutions may be exploited for feasible anchorless solutions. In this paper, we propose a novel network-based mobility management solution that facilitates IP mobility over such a path-based forwarding substrate. Our solution exploits the advantages of such substrates in decoupling path calculation from data transfer to eliminate the need for anchoring traffic through the network core; thereby, allowing flexible path calculation and service provisioning. Furthermore, by eliminating the limitation of routing via the anchor point, our approach reduces the network cost compared to anchored solution through bandwidth saving while maintaining comparable handover delay. We evaluate our solution through analytical and simulation models and compare it with the IETF standardized solution, Proxy Mobile IPv6 (PMIPv6). Evaluation results illustrate a significant saving in the total network cost when using our proposed solution, compared to its counterpart.
Learning Adaptive Parameter Tuning for Image Processing
Venue: arXiv cs.CV 2017
Year: 2017

The non-stationary nature of image characteristics calls for adaptive processing, based on the local image content. We propose a simple and flexible method to learn local tuning of parameters in adaptive image processing: we extract simple local features from an image and learn the relation between these features and the optimal filtering parameters. Learning is performed by optimizing a user defined cost function (any image quality metric) on a training set. We apply our method to three classical problems (denoising, demosaicing and deblurring) and we show the effectiveness of the learned parameter modulation strategies. We also show that these strategies are consistent with theoretical results from the literature.
Fast Learning with Nonconvex L1-2 Regularization
Venue: arXiv cs.LG 2017
Year: 2017

Convex regularizers are often used for sparse learning. They are easy to optimize, but can lead to inferior prediction performance. The difference of $\ell_1$ and $\ell_2$ ($\ell_{1-2}$) regularizer has been recently proposed as a nonconvex regularizer. It yields better recovery than both $\ell_0$ and $\ell_1$ regularizers on compressed sensing. However, how to efficiently optimize its learning problem is still challenging. The main difficulty is that both the $\ell_1$ and $\ell_2$ norms in $\ell_{1-2}$ are not differentiable, and existing optimization algorithms cannot be applied. In this paper, we show that a closed-form solution can be derived for the proximal step associated with this regularizer. We further extend the result for low-rank matrix learning and the total variation model. Experiments on both synthetic and real data sets show that the resultant accelerated proximal gradient algorithm is more efficient than other noncovex optimization algorithms.
Massive Machine-Type Communication (mMTC) Access with Integrated Authentication
Venue: arXiv cs.IT 2017
Year: 2017

We present a connection establishment protocol with integrated authentication, suited for Massive Machine-Type Communications (mMTC). The protocol is contention-based and its main feature is that a device contends with a unique signature that also enables the authentication of the device towards the network. The signatures are inspired by Bloom filters and are created based on the output of the MILENAGE authentication and encryption algorithm set, which is used in the authentication and security procedures in the LTE protocol family. We show that our method utilizes the system resources more efficiently, achieves lower latency of connection establishment for Poisson arrivals and allows a $87\%$ signalling overhead reduction. An important conclusion is that the mMTC traffic benefits profoundly from integration of security features into the connection establishment/access protocols, instead of addressing them post-hoc, which has been a common practice.
Kernel Bandwidth Selection for SVDD: Peak Criterion Approach for Large Data
Venue: arXiv cs.LG 2017
Year: 2017

Support Vector Data Description (SVDD) provides a useful approach to construct a description of multivariate data for single-class classification and outlier detection with various practical applications. Gaussian kernel used in SVDD formulation allows flexible data description defined by observations designated as support vectors. The data boundary of such description is non-spherical and conforms to the geometric features of the data. By varying the Gaussian kernel bandwidth parameter, the SVDD-generated boundary can be made either smoother (more spherical) or tighter/jagged. The former case may lead to under-fitting, whereas the latter may result in overfitting. Peak criterion has been proposed to select an optimal value of the kernel bandwidth to strike the balance between the data boundary smoothness and its ability to capture the general geometric shape of the data. Peak criterion involves training SVDD at various values of the kernel bandwidth parameter. When training datasets are large, the time required to obtain the optimal value of the Gaussian kernel bandwidth parameter according to Peak method can become prohibitively large. This paper proposes an extension of Peak method for the case of large data. The proposed method gives good results when applied to several datasets. Two existing alternative methods of computing the Gaussian kernel bandwidth parameter (Coefficient of Variation and Distance to the Farthest Neighbor) were modified to allow comparison with the proposed method on convergence. Empirical comparison demonstrates the advantage of the proposed method.
Geometric complexity theory and matrix powering
Venue: arXiv cs.CC 2017
Year: 2017

Valiant's famous determinant versus permanent problem is the flagship problem in algebraic complexity theory. Mulmuley and Sohoni (Siam J Comput 2001, 2008) introduced geometric complexity theory, an approach to study this and related problems via algebraic geometry and representation theory. Their approach works by multiplying the permanent polynomial with a high power of a linear form (a process called padding) and then comparing the orbit closures of the determinant and the padded permanent. This padding was recently used heavily to show no-go results for the method of shifted partial derivatives (Efremenko, Landsberg, Schenck, Weyman, 2016) and for geometric complexity theory (Ikenmeyer Panova, FOCS 2016 and Bürgisser, Ikenmeyer Panova, FOCS 2016). Following a classical homogenization result of Nisan (STOC 1991) we replace the determinant in geometric complexity theory with the trace of a variable matrix power. This gives an equivalent but much cleaner homogeneous formulation of geometric complexity theory in which the padding is removed. This radically changes the representation theoretic questions involved to prove complexity lower bounds. We prove that in this homogeneous formulation there are no orbit occurrence obstructions that prove even superlinear lower bounds on the complexity of the permanent. This is the first no-go result in geometric complexity theory that rules out superlinear lower bounds in some model. Interestingly---in contrast to the determinant---the trace of a variable matrix power is not uniquely determined by its stabilizer.
Demystifying ResNet
Venue: arXiv cs.NE 2017
Year: 2017

The Residual Network (ResNet), proposed in He et al. (2015), utilized shortcut connections to significantly reduce the difficulty of training, which resulted in great performance boosts in terms of both training and generalization error. It was empirically observed in He et al. (2015) that stacking more layers of residual blocks with shortcut 2 results in smaller training error, while it is not true for shortcut of length 1 or 3. We provide a theoretical explanation for the uniqueness of shortcut 2. We show that with or without nonlinearities, by adding shortcuts that have depth two, the condition number of the Hessian of the loss function at the zero initial point is depth-invariant, which makes training very deep models no more difficult than shallow ones. Shortcuts of higher depth result in an extremely flat (high-order) stationary point initially, from which the optimization algorithm is hard to escape. The shortcut 1, however, is essentially equivalent to no shortcuts, which has a condition number exploding to infinity as the number of layers grows. We further argue that as the number of layers tends to infinity, it suffices to only look at the loss function at the zero initial point. Extensive experiments are provided accompanying our theoretical results. We show that initializing the network to small weights with shortcut 2 achieves significantly better results than random Gaussian (Xavier) initialization, orthogonal initialization, and shortcuts of deeper depth, from various perspectives ranging from final loss, learning dynamics and stability, to the behavior of the Hessian along the learning process.
Epistemic extensions of combined classical and intuitionistic propositional logic
Venue: arXiv cs.LO 2017
Year: 2017

Logic $L$ was introduced by Lewitzka [7] as a modal system that combines intuitionistic and classical logic: $L$ is a conservative extension of CPC and it contains a copy of IPC via the embedding $φ\mapsto\squareφ$. In this article, we consider $L3$, i.e. $L$ augmented with S3 modal axioms, define basic epistemic extensions and prove completeness w.r.t. algebraic semantics. The resulting logics combine classical knowledge and belief with intuitionistic truth. Some epistemic laws of Intuitionistic Epistemic Logic studied by Artemov and Protopopescu [1] are reflected by classical modal principles. In particular, the implications "intuitionistic truth $\Rightarrow$ knowledge $\Rightarrow$ classical truth" are represented by the theorems $\squareφ\rightarrow Kφ$ and $Kφ\rightarrowφ$ of our logic $EL3$, where we are dealing with classical instead of intuitionistic knowledge. Finally, we show that a modification of our semantics yields algebraic models for the systems of Intuitionistic Epistemic Logic introduced in [1].
Decentralized Caching and Coded Delivery with Distinct Cache Capacities
Venue: arXiv cs.IT 2017
Year: 2017

Decentralized proactive caching and coded delivery is studied in a content delivery network, where each user is equipped with a cache memory, not necessarily of equal capacity. Cache memories are filled in advance during the off-peak traffic period in a decentralized manner, i.e., without the knowledge of the number of active users, their identities, or their particular demands. User demands are revealed during the peak traffic period, and are served simultaneously through an error-free shared link. The goal is to find the minimum delivery rate during the peak traffic period that is sufficient to satisfy all possible demand combinations. A group-based decentralized caching and coded delivery scheme is proposed, and it is shown to improve upon the state-of-the-art in terms of the minimum required delivery rate when there are more users in the system than files. Numerical results indicate that the improvement is more significant as the cache capacities of the users become more skewed. A new lower bound on the delivery rate is also presented, which provides a tighter bound than the classical cut-set bound.
Non-Orthogonal Multiple Access in Multi-Cell Networks: Theory, Performance, and Practical Challenges
Venue: arXiv cs.IT 2017
Year: 2017

Non-orthogonal multiple access (NOMA) is a potential enabler for the development of 5G and beyond wireless networks. By allowing multiple users to share the same time and frequency, NOMA can scale up the number of served users, increase the spectral efficiency, and improve user-fairness compared to existing orthogonal multiple access (OMA) techniques. While single-cell NOMA has drawn significant attention recently, much less attention has been given to multi-cell NOMA. This article discusses the opportunities and challenges of NOMA in a multi-cell environment. As the density of base stations and devices increases, inter-cell interference becomes a major obstacle in multi-cell networks. As such, identifying techniques that combine interference management approaches with NOMA is of great significance. After discussing the theory behind NOMA, this paper provides an overview of the current literature and discusses key implementation and research challenges, with an emphasis on multi-cell NOMA.
On the Configuration-LP of the Restricted Assignment Problem
Venue: arXiv cs.DS 2017
Year: 2017

We consider the classical problem of Scheduling on Unrelated Machines. In this problem a set of jobs is to be distributed among a set of machines and the maximum load (makespan) is to be minimized. The processing time $p_{ij}$ of a job $j$ depends on the machine $i$ it is assigned to. Lenstra, Shmoys and Tardos gave a polynomial time $2$-approximation for this problem. In this paper we focus on a prominent special case, the Restricted Assignment problem, in which $p_{ij}\in\{p_j,\infty\}$. The configuration-LP is a linear programming relaxation for the Restricted Assignment problem. It was shown by Svensson that the multiplicative gap between integral and fractional solution, the integrality gap, is at most $2 - 1/17 \approx 1.9412$. In this paper we significantly simplify his proof and achieve a bound of $2 - 1/6 \approx 1.8333$. As a direct consequence this provides a polynomial $(2 - 1/6 + ε)$-estimation algorithm for the Restricted Assignment problem by approximating the configuration-LP. The best lower bound known for the integrality gap is $1.5$ and no estimation algorithm with a guarantee better than $1.5$ exists unless $\mathrm{P} = \mathrm{NP}$.
Real-Time Visual Place Recognition for Personal Localization on a Mobile Device
Venue: arXiv cs.RO 2017
Year: 2017

The paper presents an approach to indoor personal localization on a mobile device based on visual place recognition. We implemented on a smartphone two state-of-the-art algorithms that are representative to two different approaches to visual place recognition: FAB-MAP that recognizes places using individual images, and ABLE-M that utilizes sequences of images. These algorithms are evaluated in environments of different structure, focusing on problems commonly encountered when a mobile device camera is used. The conclusions drawn from this evaluation are guidelines to design the FastABLE system, which is based on the ABLE-M algorithm, but introduces major modifications to the concept of image matching. The improvements radically cut down the processing time and improve scalability, making it possible to localize the user in long image sequences with the limited computing power of a mobile device. The resulting place recognition system compares favorably to both the ABLE-M and the FAB-MAP solutions in the context of real-time personal localization.
What Is the True Value of Dynamic TDD: A MAC Layer Perspective
Venue: arXiv cs.IT 2017
Year: 2017

Small cell networks (SCNs) are envisioned to embrace dynamic time division duplexing (TDD) in order to tailor downlink (DL)/uplink (UL) subframe resources to quick variations and burstiness of DL/UL traffic. The study of dynamic TDD is particularly important because it provides valuable insights on the full duplex transmission technology, which has been identified as one of the candidate technologies for the 5th-generation (5G) networks. Up to now, the existing works on dynamic TDD have shown that the UL of dynamic TDD suffers from severe performance degradation due to the strong DL-to-UL interference in the physical (PHY) layer. This conclusion raises a fundamental question: Despite such obvious technology disadvantage, what is the true value of dynamic TDD? In this paper, we answer this question from a media access control (MAC) layer viewpoint and present analytical results on the DL/UL time resource utilization (TRU) of synchronous dynamic TDD, which has been widely adopted in the existing 4th-generation (4G) systems. Our analytical results shed new light on the dynamic TDD in future synchronous 5G networks.
Mobile Lattice-Coded Physical-Layer Network Coding With Practical Channel Alignment
Venue: arXiv cs.NI 2017
Year: 2017

Physical-layer network coding (PNC) is a communications paradigm that exploits overlapped transmissions to boost the throughput of wireless relay networks. A high point of PNC research was a theoretical proof that PNC that makes use of lattice codes could approach the information-theoretic capacity of a two-way relay network (TWRN), where two end nodes communicate via a relay node. The capacity cannot be achieved by conventional methods of time-division or straightforward network coding. Many practical challenges, however, remain to be addressed before the full potential of lattice-coded PNC can be realized. Two major challenges are: for good performance in lattice-coded PNC, channels of simultaneously transmitting nodes must be aligned; for lattice-coded PNC to be practical, the complexity of lattice encoding at the transmitters and lattice decoding at the receiver must be reduced. We address these challenges and implement a first lattice-coded PNC system on a software-defined radio platform. Specifically, we design and implement a low-overhead channel precoding system that accurately aligns the channels of distributed nodes. In our implementation, the nodes only use low-cost temperature-compensated oscillators---a consequent challenge is that the channel alignment must be done more frequently and more accurately compared with the use of expensive oscillators. The low overhead and accurate channel alignment are achieved by (1)a channel precoding system implemented over FPGA to realize fast feedback of channel state information; (2)a highly-accurate carrier frequency offset estimation method; and (3)a partial-feedback channel estimation method that significantly reduces the feedback information from the receiver to the transmitters for channel precoding at the transmitters. To reduce lattice encoding and decoding complexities, we adapt the low-density lattice code for use in PNC systems.
Attributing Hacks
Venue: arXiv cs.LG 2017
Year: 2017

In this paper we describe an algorithm for estimating the provenance of hacks on websites. That is, given properties of sites and the temporal occurrence of attacks, we are able to attribute individual attacks to joint causes and vulnerabilities, as well as estimating the evolution of these vulnerabilities over time. Specifically, we use hazard regression with a time-varying additive hazard function parameterized in a generalized linear form. The activation coefficients on each feature are continuous-time functions over time. We formulate the problem of learning these functions as a constrained variational maximum likelihood estimation problem with total variation penalty and show that the optimal solution is a 0th order spline (a piecewise constant function) with a finite number of known knots. This allows the inference problem to be solved efficiently and at scale by solving a finite dimensional optimization problem. Extensive experiments on real data sets show that our method significantly outperforms Cox's proportional hazard model. We also conduct a case study and verify that the fitted functions are indeed recovering vulnerable features and real-life events such as the release of code to exploit these features in hacker blogs.
Formation Control for Multi-Agent Systems with Connectivity Preservation and Event-Triggered Controllers
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, event-triggered controllers and corresponding algorithms are proposed to establish the formation with connectivity preservation for multi-agent systems. Each agent needs to update its control input and to broadcast this control input together with the relative state information to its neighbors at its own triggering times, and to receive information at its neighbors' triggering times. Two types of system dynamics, single integrators and double integrators, are considered. As a result, all agents converge to the formation exponentially with connectivity preservation, and Zeno behavior can be excluded. Numerical simulations show the effectiveness of the theoretical results.
Constructions and bounds for separating hash families
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we present a new construction for strong separating hash families by using hypergraphs and obtain some optimal separating hash families. We also improve some previously known bounds of separating hash families.