OpenRaiser/Intern-Atlas huggingface dataset:
Using Linguistic Features to Estimate Suicide Probability of Chinese Microblog Users
Venue: arXiv cs.SI 2014
Year: 2014

If people with high risk of suicide can be identified through social media like microblog, it is possible to implement an active intervention system to save their lives. Based on this motivation, the current study administered the Suicide Probability Scale(SPS) to 1041 weibo users at Sina Weibo, which is a leading microblog service provider in China. Two NLP (Natural Language Processing) methods, the Chinese edition of Linguistic Inquiry and Word Count (LIWC) lexicon and Latent Dirichlet Allocation (LDA), are used to extract linguistic features from the Sina Weibo data. We trained predicting models by machine learning algorithm based on these two types of features, to estimate suicide probability based on linguistic features. The experiment results indicate that LDA can find topics that relate to suicide probability, and improve the performance of prediction. Our study adds value in prediction of suicidal probability of social network users with their behaviors.
Iterated geometric harmonics for data imputation and reconstruction of missing data
Venue: arXiv cs.LG 2014
Year: 2014

The method of geometric harmonics is adapted to the situation of incomplete data by means of the iterated geometric harmonics (IGH) scheme. The method is tested on natural and synthetic data sets with 50--500 data points and dimensionality of 400--10,000. Experiments suggest that the algorithm converges to a near optimal solution within 4--6 iterations, at runtimes of less than 30 minutes on a medium-grade desktop computer. The imputation of missing data values is applied to collections of damaged images (suffering from data annihilation rates of up to 70\%) which are reconstructed with a surprising degree of accuracy.
A Probabilistic Translation Method for Dictionary-based Cross-lingual Information Retrieval in Agglutinative Languages
Venue: arXiv cs.IR 2014
Year: 2014

Translation ambiguity, out of vocabulary words and missing some translations in bilingual dictionaries make dictionary-based Cross-language Information Retrieval (CLIR) a challenging task. Moreover, in agglutinative languages which do not have reliable stemmers, missing various lexical formations in bilingual dictionaries degrades CLIR performance. This paper aims to introduce a probabilistic translation model to solve the ambiguity problem, and also to provide most likely formations of a dictionary candidate. We propose Minimum Edit Support Candidates (MESC) method that exploits a monolingual corpus and a bilingual dictionary to translate users' native language queries to documents' language. Our experiments show that the proposed method outperforms state-of-the-art dictionary-based English-Persian CLIR.
Science and Ethnicity: How Ethnicities Shape the Evolution of Computer Science Research Community
Venue: arXiv cs.DL 2014
Year: 2014

Globalization and the world wide web has resulted in academia and science being an international and multicultural community forged by researchers and scientists with different ethnicities. How ethnicity shapes the evolution of membership, status and interactions of the scientific community, however, is not well understood. This is due to the difficulty of ethnicity identification at the large scale. We use name ethnicity classification as an indicator of ethnicity. Based on automatic name ethnicity classification of 1.7+ million authors gathered from Web, the name ethnicity of computer science scholars is investigated by population size, publication contribution and collaboration strength. By showing the evolution of name ethnicity from 1936 to 2010, we discover that ethnicity diversity has increased significantly over time and that different research communities in certain publication venues have different ethnicity compositions. We notice a clear rise in the number of Asian name ethnicities in papers. Their fraction of publication contribution increases from approximately 10% to near 50% from 1970 to 2010. We also find that name ethnicity acts as a homophily factor on coauthor networks, shaping the formation of coauthorship as well as evolution of research communities.
Tensor object classification via multilinear discriminant analysis network
Venue: arXiv cs.CV 2014
Year: 2014

This paper proposes a multilinear discriminant analysis network (MLDANet) for the recognition of multidimensional objects, known as tensor objects. The MLDANet is a variation of linear discriminant analysis network (LDANet) and principal component analysis network (PCANet), both of which are the recently proposed deep learning algorithms. The MLDANet consists of three parts: 1) The encoder learned by MLDA from tensor data. 2) Features maps ob-tained from decoder. 3) The use of binary hashing and histogram for feature pooling. A learning algorithm for MLDANet is described. Evaluations on UCF11 database indicate that the proposed MLDANet outperforms the PCANet, LDANet, MPCA + LDA, and MLDA in terms of classification for tensor objects.
Faster Exact Search using Document Clustering
Venue: arXiv cs.IR 2014
Year: 2014

We show how full-text search based on inverted indices can be accelerated by clustering the documents without losing results (SeCluD -- SEarch with CLUstered Documents). We develop a fast multilevel clustering algorithm that explicitly uses query cost for conjunctive queries as an objective function. Depending on the inputs we get up to four times faster than non-clustered search. The resulting clusters are also useful for data compression and for distributing the work over many machines.
Optical Character Recognition, Using K-Nearest Neighbors
Venue: arXiv cs.CV 2014
Year: 2014

The problem of optical character recognition, OCR, has been widely discussed in the literature. Having a hand-written text, the program aims at recognizing the text. Even though there are several approaches to this issue, it is still an open problem. In this paper we would like to propose an approach that uses K-nearest neighbors algorithm, and has the accuracy of more than 90%. The training and run time is also very short.
Branch-Avoiding Graph Algorithms
Venue: arXiv cs.DC 2014
Year: 2014

This paper quantifies the impact of branches and branch mispredictions on the single-core performance for two classes of graph problems. Specifically, we consider classical algorithms for computing connected components and breadth-first search (BFS). We show that branch mispredictions are costly and can reduce performance by as much as 30%-50%. This insight suggests that one should seek graph algorithms and implementations that avoid branches. As a proof-of-concept, we devise such implementations for both the classic top-down algorithm for BFS and the Shiloach-Vishkin algorithm for connected components. We evaluate these implementations on current x86 and ARM-based processors to show the efficacy of the approach. Our results suggest how both compiler writers and architects might exploit this insight to improve graph processing systems more broadly and create better systems for such problems.
Pervasive Healthcare-A Comprehensive Survey of Tools and Techniques
Venue: arXiv cs.CY 2014
Year: 2014

Pervasive healthcare is an emerging technology that aims to provide round-the-clock monitoring of several vital signs of patients using various health sensors, specialized communication protocols, and intelligent context-aware applications. Pervasive healthcare applications proactively contact the caregiver provided any abnormality arises in the health condition of a monitored patient. It has been a boon to the patients suffering from different diseases and requiring continuous monitoring and care, such as, disabled individuals, elderly and weak persons living alone, children of different ages, and adults who are susceptible to near-fatal falls or sudden increases in blood pressure, heart rates, stress level, etc. Existing surveys on pervasive healthcare cover generic techniques or a particular application, like fall detection. In this paper, we carry out a comprehensive coverage of several common disorders addressed by pervasive healthcare in recent years. We roughly classify different diseases by age groups of patients and then discuss various hardware and software tools and techniques to detect or treat them. We have also included detailed tabular classification of a large selection of significant research articles in pervasive healthcare.
Optimal Data Structures for Farthest-Point Queries in Cactus Networks
Venue: arXiv cs.DS 2014
Year: 2014

Consider the continuum of points on the edges of a network, i.e., a connected, undirected graph with positive edge weights. We measure the distance between these points in terms of the weighted shortest path distance, called the network distance. Within this metric space, we study farthest points and farthest distances. We introduce optimal data structures supporting queries for the farthest distance and the farthest points on trees, cycles, uni-cyclic networks, and cactus networks.
Child Education Through Animation: An Experimental Study
Venue: arXiv cs.CY 2014
Year: 2014

Teachers have tried to teach their students by introducing text books along with verbal instructions in traditional education system. However, teaching and learning methods could be changed for developing Information and Communication Technology. It's time to adapt students with interactive learning system so that they can improve their learning, catching, and memorizing capabilities. It is indispensable to create high quality and realistic leaning environment for students. Visual learning can be easier to understand and deal with their learning. We developed visual learning materials in the form of video for students of primary level using different multimedia application tools. The objective of this paper is to examine the impact of students abilities to acquire new knowledge or skills through visual learning materials and blended leaning that is integration of visual learning materials with teachers instructions. We visited a primary school in Dhaka city for this study and conducted teaching with three different groups of students, (i) teacher taught students by traditional system on same materials and marked level of students ability to adapt by a set of questions, (ii) another group was taught with only visual learning material and assessment was done with 15 questionnaires, (iii) the third group was taught with the video of solar system combined with teachers instructions and assessed with the same questionnaires. This integration of visual materials with verbal instructions is a blended approach of learning. The interactive blended approach greatly promoted students ability of acquisition of knowledge and skills. Students response and perception were very positive towards the blended technique than the other two methods. This interactive blending leaning system may be an appropriate method especially for school children.
Link-State Based Decode-Forward Schemes for Two-way Relaying
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we analyze a composite decode-and-forward scheme for the two-way relay channel with a direct link. During transmission, our scheme combines both block Markov coding and an independent coding scheme similar to network coding at the relay. The main contribution of this work is to examine how link state impacts the allocation of power between these two distinct techniques, which in turn governs the necessity of each technique in achieving the largest transmission rate region. We analytically determine the link-state regimes and associated relaying techniques. Our results illustrate an interesting trend: when the user-to-relay link is marginally stronger than the direct link, it is optimal to use only independent coding. In this case, the relay need not use full power. However, for larger user-to-relay link gains, the relay must supplement independent coding with block Markov coding to achieve the largest rate region. These link-state regimes are important for the application of two-way relaying in 5G networks, such as in D2D mode or relay-aided transmission.
Online Collaborative-Filtering on Graphs
Venue: arXiv cs.LG 2014
Year: 2014

A common phenomena in modern recommendation systems is the use of feedback from one user to infer the `value' of an item to other users. This results in an exploration vs. exploitation trade-off, in which items of possibly low value have to be presented to users in order to ascertain their value. Existing approaches to solving this problem focus on the case where the number of items are small, or admit some underlying structure -- it is unclear, however, if good recommendation is possible when dealing with content-rich settings with unstructured content. We consider this problem under a simple natural model, wherein the number of items and the number of item-views are of the same order, and an `access-graph' constrains which user is allowed to see which item. Our main insight is that the presence of the access-graph in fact makes good recommendation possible -- however this requires the exploration policy to be designed to take advantage of the access-graph. Our results demonstrate the importance of `serendipity' in exploration, and how higher graph-expansion translates to a higher quality of recommendations; it also suggests a reason why in some settings, simple policies like Twitter's `Latest-First' policy achieve a good performance. From a technical perspective, our model presents a way to study exploration-exploitation tradeoffs in settings where the number of `trials' and `strategies' are large (potentially infinite), and more importantly, of the same order. Our algorithms admit competitive-ratio guarantees which hold for the worst-case user, under both finite-population and infinite-horizon settings, and are parametrized in terms of properties of the underlying graph. Conversely, we also demonstrate that improperly-designed policies can be highly sub-optimal, and that in many settings, our results are order-wise optimal.
Interactive Digital Learning Materials for Kindergarten Students in Bangladesh
Venue: arXiv cs.CY 2014
Year: 2014

The pedagogy of teaching and learning has changed with the proliferation of communication technology and it is necessary to develop interactive learning materials for children that may improve their learning, catching, and memorizing capabilities. Perhaps, one of the most important innovations in the age of technology is multimedia and its application. It is imperative to create high quality and realistic learning environment for children. Interactive learning materials can be easier to understand and deal with their first learning. We developed some interactive learning materials in the form of a video for Playgroup using multimedia application tools. This study investigated the impact of students' abilities to acquire new knowledge or skills through interactive learning materials. We visited one kindergartens (Nursery schools), interviewed class teachers about their teaching methods and level of students' ability of recognizing English alphabets, pictures, etc. The course teachers were provided interactive learning materials to show their playgroups for a number of sessions. The video included English alphabets with related words and pictures, and motivational fun. We noticed that almost all children were very interested to interact with their leaning video. The students were assessed individually and asked to recognize the alphabets, and pictures. The students adapted with their first alphabets very quickly. However, there were individual differences in their cognitive development. This interactive multimedia can be an alternative to traditional pedagogy for teaching playgroups.
Competitive analysis via benchmark decomposition
Venue: arXiv cs.GT 2014
Year: 2014

We propose a uniform approach for the design and analysis of prior-free competitive auctions and online auctions. Our philosophy is to view the benchmark function as a variable parameter of the model and study a broad class of functions instead of a individual target benchmark. We consider a multitude of well-studied auction settings, and improve upon a few previous results. (1) Multi-unit auctions. Given a $β$-competitive unlimited supply auction, the best previously known multi-unit auction is $2β$-competitive. We design a $(1+β)$-competitive auction reducing the ratio from $4.84$ to $3.24$. These results carry over to matroid and position auctions. (2) General downward-closed environments. We design a $6.5$-competitive auction improving upon the ratio of $7.5$. Our auction is noticeably simpler than the previous best one. (3) Unlimited supply online auctions. Our analysis yields an auction with a competitive ratio of $4.12$, which significantly narrows the margin of $[4,4.84]$ previously known for this problem. A particularly important tool in our analysis is a simple decomposition lemma, which allows us to bound the competitive ratio against a sum of benchmark functions. We use this lemma in a "divide and conquer" fashion by dividing the target benchmark into the sum of simpler functions.
Spiders can be recognized by counting their legs
Venue: arXiv cs.DM 2014
Year: 2014

Spiders are arthropods that can be distinguished from their closest relatives, the insects, by counting their legs. Spiders have 8, insects just 6. Spider graphs are a very restricted class of graphs that naturally appear in the context of cograph editing. The vertex set of a spider (or its complement) is naturally partitioned into a clique (the body), an independent set (the legs), and a rest (serving as the head). Here we show that spiders can be recognized directly from their degree sequences through the number of their legs (vertices with degree 1). Furthermore, we completely characterize the degree sequences of spiders.
Incentive Design in Peer Review: Rating and Repeated Endogenous Matching
Venue: arXiv cs.GT 2014
Year: 2014

Peer review (e.g., grading assignments in Massive Open Online Courses (MOOCs), academic paper review) is an effective and scalable method to evaluate the products (e.g., assignments, papers) of a large number of agents when the number of dedicated reviewing experts (e.g., teaching assistants, editors) is limited. Peer review poses two key challenges: 1) identifying the reviewers' intrinsic capabilities (i.e., adverse selection) and 2) incentivizing the reviewers to exert high effort (i.e., moral hazard). Some works in mechanism design address pure adverse selection using one-shot matching rules, and pure moral hazard was addressed in repeated games with exogenously given and fixed matching rules. However, in peer review systems exhibiting both adverse selection and moral hazard, one-shot or exogenous matching rules do not link agents' current behavior with future matches and future payoffs, and as we prove, will induce myopic behavior (i.e., exerting the lowest effort) resulting in the lowest review quality. In this paper, we propose for the first time a solution that simultaneously solves adverse selection and moral hazard. Our solution exploits the repeated interactions of agents, utilizes ratings to summarize agents' past review quality, and designs matching rules that endogenously depend on agents' ratings. Our proposed matching rules are easy to implement and require no knowledge about agents' private information (e.g., their benefit and cost functions). Yet, they are effective in guiding the system to an equilibrium where the agents are incentivized to exert high effort and receive ratings that precisely reflect their review quality. Using several illustrative examples, we quantify the significant performance gains obtained by our proposed mechanism as compared to existing one-shot or exogenous matching rules.
A Subspace Method for I/Q Imbalance Estimation in Low-IF Receivers
Venue: arXiv cs.IT 2014
Year: 2014

In low-intermediate-frequency (low-IF) receivers, I/Q imbalance (IQI) causes interference on the desired signal from the blocker signal transmitted over the image frequencies. Conventional approaches for data-aided IQI estimation in zero-IF receivers are not applicable to low-IF receivers. In zero-IF receivers, IQI induces self-interference where the pilots of the image interference are completely identified. However, in low IF receivers, the image interference originates from a foreign signal whose training sequence timing and structure are neither known nor synchronized with the desired signal. We develop a data-aided subspace method for the estimation of IQI parameters in low-IF receivers in the presence of unknown fading channel. Our approach does not require the knowledge of the interference statistics, channel model nor noise statistics. Simulation results demonstrate the superiority of our approach over other blind IQI compensation approaches.
Multisequences with high joint nonlinear complexity
Venue: arXiv cs.IT 2014
Year: 2014

We introduce the new concept of joint nonlinear complexity for multisequences over finite fields and we analyze the joint nonlinear complexity of two families of explicit inversive multisequences. We also establish a probabilistic result on the behavior of the joint nonlinear complexity of random multisequences over a fixed finite field.
Sparse Estimation with Generalized Beta Mixture and the Horseshoe Prior
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, the use of the Generalized Beta Mixture (GBM) and Horseshoe distributions as priors in the Bayesian Compressive Sensing framework is proposed. The distributions are considered in a two-layer hierarchical model, making the corresponding inference problem amenable to Expectation Maximization (EM). We present an explicit, algebraic EM-update rule for the models, yielding two fast and experimentally validated algorithms for signal recovery. Experimental results show that our algorithms outperform state-of-the-art methods on a wide range of sparsity levels and amplitudes in terms of reconstruction accuracy, convergence rate and sparsity. The largest improvement can be observed for sparse signals with high amplitudes.
Software and System Modeling Based on a Unified Formal Semantics
Venue: arXiv cs.SE 2014
Year: 2014

Modeling and documentation are two essential ingredients for the engineering discipline of software development. During the last twenty years a wide variety of description and modeling techniques as well as document formats has been proposed. However, often these are not integrated into a coherent methodology with well-defined dependencies between the models and documentations. This hampers focused software development as well as the provision of powerful tool-support. In this paper we present the main issues and outline solutions in the direction of a unified, formal basis for software and system modeling.
Refinement of Pipe-and-Filter Architectures
Venue: arXiv cs.SE 2014
Year: 2014

Software and hardware architectures are prone to modifications. We demonstrate how a mathematically founded powerful refinement calculus for a class of architectures, namely pipe and filter architectures, can be used to modify a system in a provably correct way. The calculus consists of basic rules to add and to remove filters (components) and pipes (channels) to a system. A networking example demonstrates some of the features of our calculus. The calculus is simple, flexible and compositional. Thus it allows us to build more complex and specific rules that e.g. embed models of existing architectures or define design patterns as transformation rules.