BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Steven Skiena

Steven Skiena appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computation and LanguageMachine LearningSocial and Information NetworksInformation Retrievalphysics.soc-phComputational GeometryDiscrete MathematicsPopulations and Evolution

Catalog footprint

What is connected

16works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

16 published item(s)

preprint2022arXiv

Time Window Frechet and Metric-Based Edit Distance for Passively Collected Trajectories

The advances of modern localization techniques and the wide spread of mobile devices have provided us great opportunities to collect and mine human mobility trajectories. In this work, we focus on passively collected trajectories, which are sequences of time-stamped locations that mobile entities visit. To analyse such trajectories, a crucial part is a measure of similarity between two trajectories. We propose the time-window Frechet distance, which enforces the maximum temporal separation between points of two trajectories that can be paired in the calculation of the Frechet distance, and the metric-based edit distance which incorporates the underlying metric in the computation of the insertion and deletion costs. Using these measures, we can cluster trajectories to infer group motion patterns. We look at the $k$-gather problem which requires each cluster to have at least $k$ trajectories. We prove that k-gather remains NP-hard under edit distance, metric-based edit distance and Jaccard distance. Finally, we improve over previous results on discrete Frechet distance and show that there is no strongly sub-quadratic time with approximation factor less than $1.61$ in two dimensional setting unless SETH fails.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Maximizing the Expected Value of a Lottery Ticket: How to Sell and When to Buy

Unusually large prize pools in lotteries like Mega Millions and Powerball attract additional bettors, which increases the likelihood that multiple winners will have to share the pool. Thus, the expected value of a lottery ticket decreases as the probability of collisions (two or more bettors with identical winning tickets) increase. We propose a way to increase the expected value of lottery tickets by minimizing collisions, while preserving the independent generation necessary in a distributed point-of-sales environment. Our approach involves partitioning the ticket space among different vendors and pairing them off to ensure no collisions among pairs. Our analysis demonstrates that this approach increases the expected value each ticket, without increasing the size of the prize pool. We also analyze when ticket sales have maximal expected value, and show that they provide positive returns when the jackpot is between \$775.2 million and \$1.67 billion dollars.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

False-Friend Detection and Entity Matching via Unsupervised Transliteration

Transliterations play an important role in multilingual entity reference resolution, because proper names increasingly travel between languages in news and social media. Previous work associated with machine translation targets transliteration only single between language pairs, focuses on specific classes of entities (such as cities and celebrities) and relies on manual curation, which limits the expression power of transliteration in multilingual environment. By contrast, we present an unsupervised transliteration model covering 69 major languages that can generate good transliterations for arbitrary strings between any language pair. Our model yields top-(1, 20, 100) averages of (32.85%, 60.44%, 83.20%) in matching gold standard transliteration compared to results from a recently-published system of (26.71%, 50.27%, 72.79%). We also show the quality of our model in detecting true and false friends from Wikipedia high frequency lexicons. Our method indicates a strong signal of pronunciation similarity and boosts the probability of finding true friends in 68 out of 69 languages.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Freshman or Fresher? Quantifying the Geographic Variation of Internet Language

We present a new computational technique to detect and analyze statistically significant geographic variation in language. Our meta-analysis approach captures statistical properties of word usage across geographical regions and uses statistical methods to identify significant changes specific to regions. While previous approaches have primarily focused on lexical variation between regions, our method identifies words that demonstrate semantic and syntactic variation as well. We extend recently developed techniques for neural language models to learn word representations which capture differing semantics across geographical regions. In order to quantify this variation and ensure robust detection of true regional differences, we formulate a null model to determine whether observed changes are statistically significant. Our method is the first such approach to explicitly account for random variation due to chance while detecting regional variation in word meaning. To validate our model, we study and analyze two different massive online data sets: millions of tweets from Twitter spanning not only four different countries but also fifty states, as well as millions of phrases contained in the Google Book Ngrams. Our analysis reveals interesting facets of language change at multiple scales of geographic resolution -- from neighboring states to distant continents. Finally, using our model, we propose a measure of semantic distance between languages. Our analysis of British and American English over a period of 100 years reveals that semantic variation between these dialects is shrinking.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the Convergent Properties of Word Embedding Methods

Do word embeddings converge to learn similar things over different initializations? How repeatable are experiments with word embeddings? Are all word embedding techniques equally reliable? In this paper we propose evaluating methods for learning word representations by their consistency across initializations. We propose a measure to quantify the similarity of the learned word representations under this setting (where they are subject to different random initializations). Our preliminary results illustrate that our metric not only measures a intrinsic property of word embedding methods but also correlates well with other evaluation metrics on downstream tasks. We believe our methods are is useful in characterizing robustness -- an important property to consider when developing new word embedding methods.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Marking Streets to Improve Parking Density

Street parking spots for automobiles are a scarce commodity in most urban environments. The heterogeneity of car sizes makes it inefficient to rigidly define fixed-sized spots. Instead, unmarked streets in cities like New York leave placement decisions to individual drivers, who have no direct incentive to maximize street utilization. In this paper, we explore the effectiveness of two different behavioral interventions designed to encourage better parking, namely (1) educational campaigns to encourage parkers to "kiss the bumper" and reduce the distance between themselves and their neighbors, or (2) painting appropriately-spaced markings on the street and urging drivers to "hit the line". Through analysis and simulation, we establish that the greatest densities are achieved when lines are painted to create spots roughly twice the length of average-sized cars. Kiss-the-bumper campaigns are in principle more effective than hit-the-line for equal degrees of compliance, although we believe that the visual cues of painted lines induce better parking behavior.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

DeepWalk: Online Learning of Social Representations

We present DeepWalk, a novel approach for learning latent representations of vertices in a network. These latent representations encode social relations in a continuous vector space, which is easily exploited by statistical models. DeepWalk generalizes recent advancements in language modeling and unsupervised feature learning (or deep learning) from sequences of words to graphs. DeepWalk uses local information obtained from truncated random walks to learn latent representations by treating walks as the equivalent of sentences. We demonstrate DeepWalk's latent representations on several multi-label network classification tasks for social networks such as BlogCatalog, Flickr, and YouTube. Our results show that DeepWalk outperforms challenging baselines which are allowed a global view of the network, especially in the presence of missing information. DeepWalk's representations can provide $F_1$ scores up to 10% higher than competing methods when labeled data is sparse. In some experiments, DeepWalk's representations are able to outperform all baseline methods while using 60% less training data. DeepWalk is also scalable. It is an online learning algorithm which builds useful incremental results, and is trivially parallelizable. These qualities make it suitable for a broad class of real world applications such as network classification, and anomaly detection.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Exploring the power of GPU's for training Polyglot language models

One of the major research trends currently is the evolution of heterogeneous parallel computing. GP-GPU computing is being widely used and several applications have been designed to exploit the massive parallelism that GP-GPU's have to offer. While GPU's have always been widely used in areas of computer vision for image processing, little has been done to investigate whether the massive parallelism provided by GP-GPU's can be utilized effectively for Natural Language Processing(NLP) tasks. In this work, we investigate and explore the power of GP-GPU's in the task of learning language models. More specifically, we investigate the performance of training Polyglot language models using deep belief neural networks. We evaluate the performance of training the model on the GPU and present optimizations that boost the performance on the GPU.One of the key optimizations, we propose increases the performance of a function involved in calculating and updating the gradient by approximately 50 times on the GPU for sufficiently large batch sizes. We show that with the above optimizations, the GP-GPU's performance on the task increases by factor of approximately 3-4. The optimizations we made are generic Theano optimizations and hence potentially boost the performance of other models which rely on these operations.We also show that these optimizations result in the GPU's performance at this task being now comparable to that on the CPU. We conclude by presenting a thorough evaluation of the applicability of GP-GPU's for this task and highlight the factors limiting the performance of training a Polyglot model on the GPU.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Inducing Language Networks from Continuous Space Word Representations

Recent advancements in unsupervised feature learning have developed powerful latent representations of words. However, it is still not clear what makes one representation better than another and how we can learn the ideal representation. Understanding the structure of latent spaces attained is key to any future advancement in unsupervised learning. In this work, we introduce a new view of continuous space word representations as language networks. We explore two techniques to create language networks from learned features by inducing them for two popular word representation methods and examining the properties of their resulting networks. We find that the induced networks differ from other methods of creating language networks, and that they contain meaningful community structure.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

News-Based Group Modeling and Forecasting

In this paper, we study news group modeling and forecasting methods using quantitative data generated by our large-scale natural language processing (NLP) text analysis system. A news group is a set of news entities, like top U.S. cities, governors, senators, golfers, or movie actors. Our fame distribution analysis of news groups shows that log-normal and power-law distributions generally could describe news groups in many aspects. We use several real news groups including cities, politicians, and CS professors, to evaluate our news group models in terms of time series data distribution analysis, group-fame probability analysis, and fame-changing analysis over long time. We also build a practical news generation model using a HMM (Hidden Markov Model) based approach. Most importantly, our analysis shows the future entity fame distribution has a power-law tail. That is, only a small number of news entities in a group could become famous in the future. Based on these analysis we are able to answer some interesting forecasting problems - for example, what is the future average fame (or maximum fame) of a specific news group? And what is the probability that some news entity become very famous within a certain future time range? We also give concrete examples to illustrate our forecasting approaches.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

POLYGLOT-NER: Massive Multilingual Named Entity Recognition

The increasing diversity of languages used on the web introduces a new level of complexity to Information Retrieval (IR) systems. We can no longer assume that textual content is written in one language or even the same language family. In this paper, we demonstrate how to build massive multilingual annotators with minimal human expertise and intervention. We describe a system that builds Named Entity Recognition (NER) annotators for 40 major languages using Wikipedia and Freebase. Our approach does not require NER human annotated datasets or language specific resources like treebanks, parallel corpora, and orthographic rules. The novelty of approach lies therein - using only language agnostic techniques, while achieving competitive performance. Our method learns distributed word representations (word embeddings) which encode semantic and syntactic features of words in each language. Then, we automatically generate datasets from Wikipedia link structure and Freebase attributes. Finally, we apply two preprocessing stages (oversampling and exact surface form matching) which do not require any linguistic expertise. Our evaluation is two fold: First, we demonstrate the system performance on human annotated datasets. Second, for languages where no gold-standard benchmarks are available, we propose a new method, distant evaluation, based on statistical machine translation.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Polyglot: Distributed Word Representations for Multilingual NLP

Distributed word representations (word embeddings) have recently contributed to competitive performance in language modeling and several NLP tasks. In this work, we train word embeddings for more than 100 languages using their corresponding Wikipedias. We quantitatively demonstrate the utility of our word embeddings by using them as the sole features for training a part of speech tagger for a subset of these languages. We find their performance to be competitive with near state-of-art methods in English, Danish and Swedish. Moreover, we investigate the semantic features captured by these embeddings through the proximity of word groupings. We will release these embeddings publicly to help researchers in the development and enhancement of multilingual applications.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Statistically Significant Detection of Linguistic Change

We propose a new computational approach for tracking and detecting statistically significant linguistic shifts in the meaning and usage of words. Such linguistic shifts are especially prevalent on the Internet, where the rapid exchange of ideas can quickly change a word's meaning. Our meta-analysis approach constructs property time series of word usage, and then uses statistically sound change point detection algorithms to identify significant linguistic shifts. We consider and analyze three approaches of increasing complexity to generate such linguistic property time series, the culmination of which uses distributional characteristics inferred from word co-occurrences. Using recently proposed deep neural language models, we first train vector representations of words for each time period. Second, we warp the vector spaces into one unified coordinate system. Finally, we construct a distance-based distributional time series for each word to track it's linguistic displacement over time. We demonstrate that our approach is scalable by tracking linguistic change across years of micro-blogging using Twitter, a decade of product reviews using a corpus of movie reviews from Amazon, and a century of written books using the Google Book-ngrams. Our analysis reveals interesting patterns of language usage change commensurate with each medium.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

SpeedRead: A Fast Named Entity Recognition Pipeline

Online content analysis employs algorithmic methods to identify entities in unstructured text. Both machine learning and knowledge-base approaches lie at the foundation of contemporary named entities extraction systems. However, the progress in deploying these approaches on web-scale has been been hampered by the computational cost of NLP over massive text corpora. We present SpeedRead (SR), a named entity recognition pipeline that runs at least 10 times faster than Stanford NLP pipeline. This pipeline consists of a high performance Penn Treebank- compliant tokenizer, close to state-of-art part-of-speech (POS) tagger and knowledge-based named entity recognizer.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The Expressive Power of Word Embeddings

We seek to better understand the difference in quality of the several publicly released embeddings. We propose several tasks that help to distinguish the characteristics of different embeddings. Our evaluation of sentiment polarity and synonym/antonym relations shows that embeddings are able to capture surprisingly nuanced semantics even in the absence of sentence structure. Moreover, benchmarking the embeddings shows great variance in quality and characteristics of the semantics captured by the tested embeddings. Finally, we show the impact of varying the number of dimensions and the resolution of each dimension on the effective useful features captured by the embedding space. Our contributions highlight the importance of embeddings for NLP tasks and the effect of their quality on the final results.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Towards a Taxonomical Consensus: Diversity and Richness Inference from Large Scale rRNA gene Analysis

Population analysis is persistently challenging but important, leading to the determination of diversity and function prediction of microbial community members. Here we detail our bioinformatics methods for analyzing population distribution and diversity in large microbial communities. This was achieved via (i) a homology based method for robust phylotype determination, equaling the classification accuracy of the Ribosomal Database Project (RDP) classifier, but providing improved associations of closely related sequences; (ii) a comparison of different clustering methods for achieving more accurate richness estimations. Our methodology, which we developed using the RDP vetted 16S rRNA gene sequence set, was validated by testing it on a large 16S rRNA gene dataset of approximately 2300 sequences, which we obtained from a soil microbial community study. We concluded that the best approach to obtain accurate phylogenetics profile of large microbial communities, based on 16S rRNA gene sequence information, is to apply an optimized blast classifier. This approach is complemented by the grouping of closely related sequences, using complete linkage clustering, in order to calculate richness and evenness indices for the communities.

0 citations0 reviewsNo code linkedOpen access