OpenRaiser/Intern-Atlas huggingface dataset:
A survey on feature weighting based K-Means algorithms
Venue: arXiv cs.LG 2015
Year: 2015

In a real-world data set there is always the possibility, rather high in our opinion, that different features may have different degrees of relevance. Most machine learning algorithms deal with this fact by either selecting or deselecting features in the data preprocessing phase. However, we maintain that even among relevant features there may be different degrees of relevance, and this should be taken into account during the clustering process. With over 50 years of history, K-Means is arguably the most popular partitional clustering algorithm there is. The first K-Means based clustering algorithm to compute feature weights was designed just over 30 years ago. Various such algorithms have been designed since but there has not been, to our knowledge, a survey integrating empirical evidence of cluster recovery ability, common flaws, and possible directions for future research. This paper elaborates on the concept of feature weighting and addresses these issues by critically analysing some of the most popular, or innovative, feature weighting mechanisms based in K-Means.
The effect of social welfare system based on the complex network
Venue: arXiv cs.SI 2015
Year: 2015

With the passage of time, the development of communication technology and transportation broke the isolation among people. Relationship tends to be complicated, pluralism, dynamism. In the network where interpersonal relationship and evolved complex net based on game theory work serve respectively as foundation architecture and theoretical model, with the combination of game theory and regard public welfare as influencing factor, we artificially initialize that closed network system. Through continual loop operation of the program, we summarize the changing rule of the cooperative behavior in the interpersonal relationship, so that we can analyze the policies about welfare system about whole network and the relationship of frequency of betrayal in cooperative behavior. Most analytical data come from some simple investigations and some estimates based on internet and environment and the study put emphasis on simulating social network and analyze influence of social welfare system on Cooperative Behavio.
A straightforward method to assess motion blur for different types of displays
Venue: arXiv cs.CV 2015
Year: 2015

A simulation method based on the liquid crystal response and the human visual system is suitable to characterize motion blur for LCDs but not other display types. We propose a more straightforward and widely applicable method to quantify motion blur based on the width of the moving object. We thus compare various types of displays objectively. A perceptual experiment was conducted to validate the proposed method. We test varying motion velocities for nine commercial displays. We compare the three motion blur evaluation methods (simulation, human perception, and our method) using z-scores. Our comparisons indicate that our method accurately characterizes motion blur for various display types.
A Survey of League Championship Algorithm: Prospects and Challenges
Venue: arXiv cs.AI 2015
Year: 2015

The League Championship Algorithm (LCA) is sport-inspired optimization algorithm that was introduced by Ali Husseinzadeh Kashan in the year 2009. It has since drawn enormous interest among the researchers because of its potential efficiency in solving many optimization problems and real-world applications. The LCA has also shown great potentials in solving non-deterministic polynomial time (NP-complete) problems. This survey presents a brief synopsis of the LCA literatures in peer-reviewed journals, conferences and book chapters. These research articles are then categorized according to indexing in the major academic databases (Web of Science, Scopus, IEEE Xplore and the Google Scholar). The analysis was also done to explore the prospects and the challenges of the algorithm and its acceptability among researchers. This systematic categorization can be used as a basis for future studies.
Understanding Human-Centric Images: From Geometry to Fashion
Venue: arXiv cs.CV 2015
Year: 2015

Understanding humans from photographs has always been a fundamental goal of computer vision. In this thesis we have developed a hierarchy of tools that cover a wide range of topics with the objective of understanding humans from monocular RGB image: from low level feature point descriptors to high level fashion-aware conditional random fields models. In order to build these high level models it is paramount to have a battery of robust and reliable low and mid level cues. Along these lines, we have proposed two low-level keypoint descriptors: one based on the theory of the heat diffusion on images, and the other that uses a convolutional neural network to learn discriminative image patch representations. We also introduce distinct low-level generative models for representing human pose: in particular we present a discrete model based on a directed acyclic graph and a continuous model that consists of poses clustered on a Riemannian manifold. As mid level cues we propose two 3D human pose estimation algorithms: one that estimates the 3D pose given a noisy 2D estimation, and an approach that simultaneously estimates both the 2D and 3D pose. Finally, we formulate higher level models built upon low and mid level cues for understanding humans from single images. Concretely, we focus on two different tasks in the context of fashion: semantic segmentation of clothing, and predicting the fashionability from images with metadata to ultimately provide fashion advice to the user. For all presented approaches we present extensive results and comparisons against the state-of-the-art and show significant improvements on the entire variety of tasks we tackle.
LiFi - Let There Be Light
Venue: arXiv cs.NI 2015
Year: 2015

The paper proclaims a summary of Li-Fi technology. It is an efficient data communication mechanism involving visible light as a medium of transmission. This monograph introduces the concept of Li-Fi and its working model. Furthermore, it discusses its benefits, shortcomings and examines ways to mitigate the drawbacks. Additionally, it analyzes its present applications and explores its future scope in the competitive wireless network market.
Detection of Slang Words in e-Data using semi-Supervised Learning
Venue: arXiv cs.CL 2015
Year: 2015

The proposed algorithmic approach deals with finding the sense of a word in an electronic data. Now a day,in different communication mediums like internet, mobile services etc. people use few words, which are slang in nature. This approach detects those abusive words using supervised learning procedure. But in the real life scenario, the slang words are not used in complete word forms always. Most of the times, those words are used in different abbreviated forms like sounds alike forms, taboo morphemes etc. This proposed approach can detect those abbreviated forms also using semi supervised learning procedure. Using the synset and concept analysis of the text, the probability of a suspicious word to be a slang word is also evaluated.
Removing Manually-Generated Boilerplate from Electronic Texts: Experiments with Project Gutenberg e-Books
Venue: arXiv cs.DL 2016
Year: 2016

Collaborative work on unstructured or semi-structured documents, such as in literature corpora or source code, often involves agreed upon templates containing metadata. These templates are not consistent across users and over time. Rule-based parsing of these templates is expensive to maintain and tends to fail as new documents are added. Statistical techniques based on frequent occurrences have the potential to identify automatically a large fraction of the templates, thus reducing the burden on the programmers. We investigate the case of the Project Gutenberg corpus, where most documents are in ASCII format with preambles and epilogues that are often copied and pasted or manually typed. We show that a statistical approach can solve most cases though some documents require knowledge of English. We also survey various technical solutions that make our approach applicable to large data sets.
The Offset Tree for Learning with Partial Labels
Venue: arXiv cs.LG 2016
Year: 2016

We present an algorithm, called the Offset Tree, for learning to make decisions in situations where the payoff of only one choice is observed, rather than all choices. The algorithm reduces this setting to binary classification, allowing one to reuse of any existing, fully supervised binary classification algorithm in this partial information setting. We show that the Offset Tree is an optimal reduction to binary classification. In particular, it has regret at most $(k-1)$ times the regret of the binary classifier it uses (where $k$ is the number of choices), and no reduction to binary classification can do better. This reduction is also computationally optimal, both at training and test time, requiring just $O(\log_2 k)$ work to train on an example or make a prediction. Experiments with the Offset Tree show that it generally performs better than several alternative approaches.
Linear Recursion
Venue: arXiv cs.LO 2016
Year: 2016

We define two extensions of the typed linear lambda-calculus that yield minimal Turing-complete systems. The extensions are based on unbounded recursion in one case, and bounded recursion with minimisation in the other. We show that both approaches are compatible with linearity and typeability constraints. Both extensions of the typed linear lambda-calculus are minimal, in the sense that taking out any of the components breaks the universality of the system. We discuss implementation techniques that exploit the linearity of the calculi. Finally, we apply the results to languages with fixpoint operators: we give a compilation of the programming language PCF into a linear lambda-calculus with linear unbounded recursion.
Vsep-New Heuristic and Exact Algorithms for Graph Automorphism Group Computation
Venue: arXiv cs.DS 2016
Year: 2016

One exact and two heuristic algorithms for determining the generators, orbits and order of the graph automorphism group are presented. A basic tool of these algorithms is the well-known individualization and refinement procedure. A search tree is used in the algorithms - each node of the tree is a partition. All nonequivalent discreet partitions derivative of the selected vertices are stored in a coded form. A new strategy is used in the exact algorithm: if during its execution some of the searched or intermediate variables obtain a wrong value then the algorithm continues from a new start point losing some of the results determined so far. The algorithms has been tested on one of the known benchmark graphs and shows lower running times for some graph families. The heuristic versions of the algorithms are based on determining some number of discreet partitions derivative of each vertex in the selected cell of the initial partition and comparing them for an automorphism - their search trees are reduced. The heuristic algorithms are almost exact and are many times faster than the exact one. The experimental tests exhibit that the worst-cases running time of the exact algorithm is exponential but it is polynomial for the heuristic algorithms. Several cell selectors are used. Some of them are new. We also use a chooser of cell selector for choosing the optimal cell selector for the manipulated graph. The proposed heuristic algorithms use two main heuristic procedures that generate two different forests of search trees.
A Note on a Characterization of Rényi Measures and its Relation to Composite Hypothesis Testing
Venue: arXiv cs.IT 2016
Year: 2016

The Rényi information measures are characterized in terms of their Shannon counterparts, and properties of the former are recovered from first principle via the associated properties of the latter. Motivated by this characterization, a two-sensor composite hypothesis testing problem is presented, and the optimal worst case miss-detection exponent is obtained in terms of a Rényi divergence.
An Introduction to Functional dependency in Relational Databases
Venue: arXiv cs.DB 2016
Year: 2016

This write-up is the suggested lecture notes for a second level course on advanced topics in database systems for master's students of Computer Science with a theoretical focus. A prerequisite in algorithms and an exposure to database systems are required. Additional reading may require exposure to mathematical logic. The starting point for these notes are from M.Y.Vardi's survey listed herein as a reference - some of the proofs are presented as such . This select rewrite on functional dependency is intended to provide a few clarifications even though radically new design approaches are now being proposed.
Complexity of Metric Dimension on Planar Graphs
Venue: arXiv cs.CC 2016
Year: 2016

The metric dimension of a graph $G$ is the size of a smallest subset $L \subseteq V(G)$ such that for any $x,y \in V(G)$ with $x\not= y$ there is a $z \in L$ such that the graph distance between $x$ and $z$ differs from the graph distance between $y$ and $z$. Even though this notion has been part of the literature for almost 40 years, prior to our work the computational complexity of determining the metric dimension of a graph was still very unclear. In this paper, we show tight complexity boundaries for the Metric Dimension problem. We achieve this by giving two complementary results. First, we show that the Metric Dimension problem on planar graphs of maximum degree $6$ is NP-complete. Then, we give a polynomial-time algorithm for determining the metric dimension of outerplanar graphs.
An inventory of three-dimensional Hilbert space-filling curves
Venue: arXiv cs.CG 2016
Year: 2016

Hilbert's two-dimensional space-filling curve is appreciated for its good locality properties for many applications. However, it is not clear what is the best way to generalize this curve to filling higher-dimensional spaces. We argue that the properties that make Hilbert's curve unique in two dimensions, are shared by 10694807 structurally different space-filling curves in three dimensions. These include several curves that have, in some sense, better locality properties than any generalized Hilbert curve that has been considered in the literature before.
The Parameterised Complexity of List Problems on Graphs of Bounded Treewidth
Venue: arXiv cs.CC 2016
Year: 2016

We consider the parameterised complexity of several list problems on graphs, with parameter treewidth or pathwidth. In particular, we show that List Edge Chromatic Number and List Total Chromatic Number are fixed parameter tractable, parameterised by treewidth, whereas List Hamilton Path is W[1]-hard, even parameterised by pathwidth. These results resolve two open questions of Fellows, Fomin, Lokshtanov, Rosamond, Saurabh, Szeider and Thomassen (2011).
On the Spatial Degrees of Freedom of Multicell and Multiuser MIMO Channels
Venue: arXiv cs.IT 2016
Year: 2016

We study the converse and achievability for the degrees of freedom of the multicellular multiple-input multiple-output (MIMO) multiple access channel (MAC) with constant channel coefficients. We assume L>1 homogeneous cells with K>0 users per cell where the users have M antennas and the base stations are equipped with N antennas. The degrees of freedom outer bound for this L-cell and K-user MIMO MAC is formulated. The characterized outer bound uses insight from a limit on the total degrees of freedom for the L-cell heterogeneous MIMO network. We also show through an example that a scheme selecting a transmitter and performing partial message sharing outperforms a multiple distributed transmission strategy in terms of the total degrees of freedom. Simple linear schemes attaining the outer bound (i.e., those achieving the optimal degrees of freedom) are explores for a few cases. The conditions for the required spatial dimensions attaining the optimal degrees of freedom are characterized in terms of K, L, and the number of transmit streams. The optimal degrees of freedom for the two-cell MIMO MAC are examined by using transmit zero forcing and null space interference alignment and subsequently, simple receive zero forcing is shown to provide the optimal degrees of freedom for L>1. By the uplink and downlink duality, the degrees of freedom results in this paper are also applicable to the downlink. In the downlink scenario, we study the degrees of freedom of L-cell MIMO interference channel exploring multiuser diversity. Strong convergence modes of the instantaneous degrees of freedom as the number of users increases are characterized.
A unified graphical approach to random coding for multi-terminal networks
Venue: arXiv cs.IT 2016
Year: 2016

A unified graphical approach to random coding for any memoryless, single-hop, K-user channel with or without common information is defined through two steps. The first step is user virtualization: each user is divided into multiple virtual sub-users according to a chosen rate-splitting strategy. This results in an enhanced channel with a possibly larger number of users for which more coding possibilities are available and for which common messages to any subset of users can be encoded. Following user virtualization, the message of each user in the enhanced model is coded using a chosen combination of coded time-sharing, superposition coding and joint binning. A graph is used to represent the chosen coding strategies: nodes in the graph represent codewords while edges represent coding operations. This graph is used to construct a graphical Markov model which illustrates the statistical dependency among codewords that can be introduced by the superposition coding or joint binning. Using this statistical representation of the overall codebook distribution, the error probability of the code is shown to vanish via a unified analysis. The rate bounds that define the achievable rate region are obtained by linking the error analysis to the properties of the graphical Markov model. This proposed framework makes it possible to numerically obtain an achievable rate region by specifying a user virtualization strategy and describing a set of coding operations. The union of these rate regions defines the maximum achievable rate region of our unified coding strategy.
Secure Multiplex Coding with Dependent and Non-Uniform Multiple Messages
Venue: arXiv cs.IT 2016
Year: 2016

The secure multiplex coding (SMC) is a technique to remove rate loss in the coding for wire-tap channels and broadcast channels with confidential messages caused by the inclusion of random bits into transmitted signals. SMC replaces the random bits by other meaningful secret messages, and a collection of secret messages serves as the random bits to hide the rest of messages. In the previous researches, multiple secret messages were assumed to have independent and uniform distributions, which is difficult to be ensured in practice. We remove this restrictive assumption by a generalization of the channel resolvability technique. We also give practical construction techniques for SMC by using an arbitrary given error-correcting code as an ingredient, and channel-universal coding of SMC. By using the same principle as the channel-universal SMC, we give coding for the broadcast channel with confidential messages universal to both channel and source distributions.
Interval Routing Schemes for Circular-Arc Graphs
Venue: arXiv cs.DS 2016
Year: 2016

Interval routing is a space efficient method to realize a distributed routing function. In this paper we show that every circular-arc graph allows a shortest path strict 2-interval routing scheme, i.e., by introducing a global order on the vertices and assigning at most two (strict) intervals in this order to the ends of every edge allows to depict a routing function that implies exclusively shortest paths. Since circular-arc graphs do not allow shortest path 1-interval routing schemes in general, the result implies that the class of circular-arc graphs has strict compactness 2, which was a hitherto open question. Additionally, we show that the constructed 2-interval routing scheme is a 1-interval routing scheme with at most one additional interval assigned at each vertex and we an outline algorithm to calculate the routing scheme for circular-arc graphs in O(n^2) time, where n is the number of vertices.
Single-laser 32.5 Tbit/s Nyquist WDM transmission
Venue: arXiv cs.NI 2016
Year: 2016

We demonstrate 32.5 Tbit/s 16QAM Nyquist WDM transmission over a total length of 227 km of SMF-28 without optical dispersion compensation. A number of 325 optical carriers are derived from a single laser and encoded with dual-polarization 16QAM data using sinc-shaped Nyquist pulses. As we use no guard bands, the carriers have a spacing of 12.5 GHz equal to the Nyquist bandwidth of the data. We achieve a high net spectral efficiency of 6.4 bit/s/Hz using a software-defined transmitter which generates the electrical modulator drive signals in real-time.
Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates
Venue: arXiv cs.DS 2016
Year: 2016

Result diversification is an important aspect in web-based search, document summarization, facility location, portfolio management and other applications. Given a set of ranked results for a set of objects (e.g. web documents, facilities, etc.) with a distance between any pair, the goal is to select a subset $S$ satisfying the following three criteria: (a) the subset $S$ satisfies some constraint (e.g. bounded cardinality); (b) the subset contains results of high "quality"; and (c) the subset contains results that are "diverse" relative to the distance measure. The goal of result diversification is to produce a diversified subset while maintaining high quality as much as possible. We study a broad class of problems where the distances are a metric, where the constraint is given by independence in a matroid, where quality is determined by a monotone submodular function, and diversity is defined as the sum of distances between objects in $S$. Our problem is a generalization of the {\em max sum diversification} problem studied in \cite{GoSh09} which in turn is a generaliztion of the {\em max sum $p$-dispersion problem} studied extensively in location theory. It is NP-hard even with the triangle inequality. We propose two simple and natural algorithms: a greedy algorithm for a cardinality constraint and a local search algorithm for an arbitary matroid constraint. We prove that both algorithms achieve constant approximation ratios.