waashk/dblp huggingface dataset:
mixture models for learning low-dimensional roles in high-dimensional data. archived data often describe entities that participate in multiple roles. each of these roles may influence various aspects of the data. for example, a register transaction collected at a retail store may have been initiated by a person who is a woman, a mother, an avid reader, and an action movie fan. each of these roles can influence various aspects of the customer's purchase: the fact that the customer is a mother may greatly influence the purchase of a toddler-sized pair of pants, but have no influence on the purchase of an action-adventure novel. the fact that the customer is an action move fan and an avid reader may influence the purchase of the novel, but will have no effect on the purchase of a shirt. in this paper, we present a generic, bayesian framework for capturing exactly this situation. in our framework, it is assumed that multiple roles exist, and each data point corresponds to an entity (such as a retail customer, or an email, or a news article) that selects various roles which compete to influence the various attributes associated with the data point. we develop robust, mcmc algorithms for learning the models under the framework.
generative models for ticket resolution in expert networks. ticket resolution is a critical, yet challenging, aspect of the delivery of it services. a large service provider needs to handle, on a daily basis, thousands of tickets that report various types of problems. many of those tickets bounce among multiple expert groups before being transferred to the group with the right expertise to solve the problem. finding a methodology that reduces such bouncing and hence shortens ticket resolution time is a long-standing challenge. in this paper, we present a unified generative model, the optimized network model (onm), that characterizes the lifecycle of a ticket, using both the content and the routing sequence of the ticket. onm uses maximum likelihood estimation, to represent how the information contained in a ticket is used by human experts to make ticket routing decisions. based on onm, we develop a probabilistic algorithm to generate ticket routing recommendations for new tickets in a network of expert groups. our algorithm calculates all possible routes to potential resolvers and makes globally optimal recommendations, in contrast to existing classification methods that make static and locally optimal recommendations. experiments show that our method significantly outperforms existing solutions.
on the quality of inferring interests from social neighbors. this paper intends to provide some insights of a scientific problem: how likely one's interests can be inferred from his/her social connections -- friends, friends' friends, 3-degree friends, etc? is "birds of a feather flocks together" a norm? we do not consider the friending activity on online social networking sites. instead, we conduct this study by implementing a privacy-preserving large distribute social sensor system in a large global it company to capture the multifaceted activities of 30,000+ people, including communications (e.g., emails, instant messaging, etc) and web 2.0 activities (e.g., social bookmarking, file sharing, blogging, etc). these activities occupy the majority of employees' time in work, and thus, provide a high quality approximation to the real social connections of employees in the workplace context. in addition to such "informal networks", we investigated the "formal networks", such as their hierarchical structure, as well as the demographic profile data such as geography, job role, self-specified interests, etc. because user id matching across multiple sources on the internet is very difficult, and most user activity logs have to be anonymized before they are processed, no prior studies could collect comparable multifaceted activity data of individuals. that makes this study unique. in this paper, we present a technique to predict the inference quality by utilizing (1) network analysis and network autocorrelation modeling of informal and formal networks, and (2) regression models to predict user interest inference quality from network characteristics. we verify our findings with experiments on both implicit user interests indicated by the content of communications or web 2.0 activities, and explicit user interests specified in user profiles. we demonstrate that the inference quality prediction increases the inference quality of implicit interests by 42.8%, and inference quality of explicit interests by up to 101%.
exploitation and exploration in a performance based contextual advertising system. the dynamic marketplace in online advertising calls for ranking systems that are optimized to consistently promote and capitalize better performing ads. the streaming nature of online data inevitably makes an advertising system choose between maximizing its expected revenue according to its current knowledge in short term (exploitation) and trying to learn more about the unknown to improve its knowledge (exploration), since the latter might increase its revenue in the future. the exploitation and exploration (ee) tradeoff has been extensively studied in the reinforcement learning community, however, not been paid much attention in online advertising until recently. in this paper, we develop two novel ee strategies for online advertising. specifically, our methods can adaptively balance the two aspects of ee by automatically learning the optimal tradeoff and incorporating confidence metrics of historical performance. within a deliberately designed offline simulation framework we apply our algorithms to an industry leading performance based contextual advertising system and conduct extensive evaluations with real online event log data. the experimental results and detailed analysis reveal several important findings of ee behaviors in online advertising and demonstrate that our algorithms perform superiorly in terms of ad reach and click-through-rate (ctr).
user browsing models: relevance versus examination. there has been considerable work on user browsing models for search engine results, both organic and sponsored. the click-through rate (ctr) of a result is the product of the probability of examination (will the user look at the result) times the perceived relevance of the result (probability of a click given examination). past papers have assumed that when the ctr of a result varies based on the pattern of clicks in prior positions, this variation is solely due to changes in the probability of examination. we show that, for sponsored search results, a substantial portion of the change in ctr when conditioned on prior clicks is in fact due to a change in the relevance of results for that query instance, not just due to a change in the probability of examination. we then propose three new user browsing models, which attribute ctr changes solely to changes in relevance, solely to changes in examination (with an enhanced model of user behavior), or to both changes in relevance and examination. the model that attributes all the ctr change to relevance yields substantially better predictors of ctr than models that attribute all the change to examination, and does only slightly worse than the model that attributes ctr change to both relevance and examination. for predicting relevance, the model that attributes all the ctr change to relevance again does better than the model that attributes the change to examination. surprisingly, we also find that one model might do better than another in predicting ctr, but worse in predicting relevance. thus it is essential to evaluate user browsing models with respect to accuracy in predicting relevance, not just ctr.
learning incoherent sparse and low-rank patterns from multiple tasks. we consider the problem of learning incoherent sparse and low-rank patterns from multiple tasks. our approach is based on a linear multi-task learning formulation, in which the sparse and low-rank patterns are induced by a cardinality regularization term and a low-rank constraint, respectively. this formulation is non-convex; we convert it into its convex surrogate, which can be routinely solved via semidefinite programming for small-size problems. we propose to employ the general projected gradient scheme to efficiently solve such a convex surrogate; however, in the optimization formulation, the objective function is non-differentiable and the feasible domain is non-trivial. we present the procedures for computing the projected gradient and ensuring the global convergence of the projected gradient scheme. the computation of projected gradient involves a constrained optimization problem; we show that the optimal solution to such a problem can be obtained via solving an unconstrained optimization subproblem and an euclidean projection subproblem. in addition, we present two projected gradient algorithms and discuss their rates of convergence. experimental results on benchmark data sets demonstrate the effectiveness of the proposed multi-task learning formulation and the efficiency of the proposed projected gradient algorithms.
designing efficient cascaded classifiers: tradeoff between accuracy and cost. we propose a method to train a cascade of classifiers by simultaneously optimizing all its stages. the approach relies on the idea of optimizing soft cascades. in particular, instead of optimizing a deterministic hard cascade, we optimize a stochastic soft cascade where each stage accepts or rejects samples according to a probability distribution induced by the previous stage-specific classifier. the overall system accuracy is maximized while explicitly controlling the expected cost for feature acquisition. experimental results on three clinically relevant problems show the effectiveness of our proposed approach in achieving the desired tradeoff between accuracy and feature acquisition cost.
a scalable two-stage approach for a class of dimensionality reduction techniques. dimensionality reduction plays an important role in many data mining applications involving high-dimensional data. many existing dimensionality reduction techniques can be formulated as a generalized eigenvalue problem, which does not scale to large-size problems. prior work transforms the generalized eigenvalue problem into an equivalent least squares formulation, which can then be solved efficiently. however, the equivalence relationship only holds under certain assumptions without regularization, which severely limits their applicability in practice. in this paper, an efficient two-stage approach is proposed to solve a class of dimensionality reduction techniques, including canonical correlation analysis, orthonormal partial least squares, linear discriminant analysis, and hypergraph spectral learning. the proposed two-stage approach scales linearly in terms of both the sample size and data dimensionality. the main contributions of this paper include (1) we rigorously establish the equivalence relationship between the proposed two-stage approach and the original formulation without any assumption; and (2) we show that the equivalence relationship still holds in the regularization setting. we have conducted extensive experiments using both synthetic and real-world data sets. our experimental results confirm the equivalence relationship established in this paper. results also demonstrate the scalability of the proposed two-stage approach.
redefining class definitions using constraint-based clustering: an application to remote sensing of the earth's surface. two aspects are crucial when constructing any real world supervised classification task: the set of classes whose distinction might be useful for the domain expert, and the set of classifications that can actually be distinguished by the data. often a set of labels is defined with some initial intuition but these are not the best match for the task. for example, labels have been assigned for land cover classification of the earth but it has been suspected that these labels are not ideal and some classes may be best split into subclasses whereas others should be merged. this paper formalizes this problem using three ingredients: the existing class labels, the underlying separability in the data, and a special type of input from the domain expert. we require a domain expert to specify an l × l matrix of pairwise probabilistic constraints expressing their beliefs as to whether the l classes should be kept separate, merged, or split. this type of input is intuitive and easy for experts to supply. we then show that the problem can be solved by casting it as an instance of penalized probabilistic clustering (ppc). our method, class-level ppc (cppc) extends ppc showing how its time complexity can be reduced from o(n2) to o(nl) for the problem of class re-definition. we further extend the algorithm by presenting a heuristic to measure adherence to constraints, and providing a criterion for determining the model complexity (number of classes) for constraint-based clustering. we demonstrate and evaluate cppc on artificial data and on our motivating domain of land cover classification. for the latter, an evaluation by domain experts shows that the algorithm discovers novel class definitions that are better suited to land cover classification than the original set of labels.
new perspectives and methods in link prediction. this paper examines important factors for link prediction in networks and provides a general, high-performance framework for the prediction task. link prediction in sparse networks presents a significant challenge due to the inherent disproportion of links that can form to links that do form. previous research has typically approached this as an unsupervised problem. while this is not the first work to explore supervised learning, many factors significant in influencing and guiding classification remain unexplored. in this paper, we consider these factors by first motivating the use of a supervised framework through a careful investigation of issues such as network observational period, generality of existing methods, variance reduction, topological causes and degrees of imbalance, and sampling approaches. we also present an effective flow-based predicting algorithm, offer formal bounds on imbalance in sparse network link prediction, and employ an evaluation method appropriate for the observed imbalance. our careful consideration of the above issues ultimately leads to a completely general framework that outperforms unsupervised link prediction methods by more than 30% auc.
universal multi-dimensional scaling. in this paper, we propose a unified algorithmic framework for solving many known variants of mds. our algorithm is a simple iterative scheme with guaranteed convergence, and is modular; by changing the internals of a single subroutine in the algorithm, we can switch cost functions and target spaces easily. in addition to the formal guarantees of convergence, our algorithms are accurate; in most cases, they converge to better quality solutions than existing methods in comparable time. moreover, they have a small memory footprint and scale effectively for large data sets. we expect that this framework will be useful for a number of mds variants that have not yet been studied. our framework extends to embedding high-dimensional points lying on a sphere to points on a lower dimensional sphere, preserving geodesic distances. as a complement to this result, we also extend the johnson-lindenstrauss lemma to this spherical setting, by showing that projecting to a random o((1/µ2) log n)-dimensional sphere causes only an eps-distortion in the geodesic distances.
mining periodic behaviors for moving objects. periodicity is a frequently happening phenomenon for moving objects. finding periodic behaviors is essential to understanding object movements. however, periodic behaviors could be complicated, involving multiple interleaving periods, partial time span, and spatiotemporal noises and outliers. in this paper, we address the problem of mining periodic behaviors for moving objects. it involves two sub-problems: how to detect the periods in complex movement, and how to mine periodic movement behaviors. our main assumption is that the observed movement is generated from multiple interleaved periodic behaviors associated with certain reference locations. based on this assumption, we propose a two-stage algorithm, periodica, to solve the problem. at the first stage, the notion of observation spot is proposed to capture the reference locations. through observation spots, multiple periods in the movement can be retrieved using a method that combines fourier transform and autocorrelation. at the second stage, a probabilistic model is proposed to characterize the periodic behaviors. for a specific period, periodic behaviors are statistically generalized from partial movement sequences through hierarchical clustering. empirical studies on both synthetic and real data sets demonstrate the effectiveness of our method.
collusion-resistant privacy-preserving data mining. recent research in privacy-preserving data mining (ppdm) has become increasingly popular due to the wide application of data mining and the increased concern regarding the protection of private and personal information. lately, numerous methods of privacy-preserving data mining have been proposed. most of these methods are based on an assumption that semi-honest is and collusion is not present. in other words, every party follows such protocol properly with the exception that it keeps a record of all its intermediate computations without sharing the record with others. in this paper, we focus our attention on the problem of collusions, in which some parties may collude and share their record to deduce the private information of other parties. in particular, we consider a general problem in ppdm - multiparty secure computation of some functions of secure summations of data spreading around multiple parties. to solve such a problem, we propose a new method that entails a high level of security - full-privacy. with this method, no sensitive information of a party will be revealed even when all other parties collude. in addition, this method is efficient with a running time of o(m). we will also show that by applying this general method, a large number of problems in ppdm can be solved with enhanced security.
detecting inefficiently-used containers to avoid bloat. runtime bloat degrades significantly the performance and scalability of software systems. an important source of bloat is the inefficient use of containers. it is expensive to create inefficiently-used containers and to invoke their associated methods, as this may ultimately execute large volumes of code, with call stacks dozens deep, and allocate many temporary objects. this paper presents practical static and dynamic tools that can find inappropriate use of containers in java programs. at the core of these tools is a base static analysis that identifies, for each container, the objects that are added to this container and the key statements (i.e., heap loads and stores) that achieve the semantics of common container operations such as add and get. the static tool finds problematic uses of containers by considering the nesting relationships among the loops where these semantics-achieving statements are located, while the dynamic tool can instrument these statements and find inefficiencies by profiling their execution frequencies. the high precision of the base analysis is achieved by taking advantage of a context-free language (cfl)-reachability formulation of points-to analysis and by accounting for container-specific properties. it is demand-driven and client-driven, facilitating refinement specific to each queried container object and increasing scalability. the tools built with the help of this analysis can be used both to avoid the creation of container-related performance problems early during development, and to help with diagnosis when problems are observed during tuning. our experimental results show that the static tool has a low false positive rate and produces more relevant information than its dynamic counterpart. further case studies suggest that significant optimization opportunities can be found by focusing on statically-identified containers for which high allocation frequency is observed at run time.
a context-free markup language for semi-structured text. an ad hoc data format is any nonstandard, semi-structured data format for which robust data processing tools are not easily available. in this paper, we present anne, a new kind of markup language designed to help users generate documentation and data processing tools for ad hoc text data. more specifically, given a new ad hoc data source, an anne programmer edits the document to add a number of simple annotations, which serve to specify its syntactic structure. annotations include elements that specify constants, optional data, alternatives, enumerations, sequences, tabular data, and recursive patterns. the anne system uses a combination of user annotations and the raw data itself to extract a context-free grammar from the document. this context-free grammar can then be used to parse the data and transform it into an xml parse tree, which may be viewed through a browser for analysis or debugging purposes. in addition, the anne system generates a pads/ml description, which may be saved as lasting documentation of the data format or compiled into a host of useful data processing tools. in addition to designing and implementing anne, we have devised a semantic theory for the core elements of the language. this semantic theory describes the editing process, which translates a raw, unannotated text document into an annotated document, and the grammar extraction process, which generates a context-free grammar from an annotated document. we also present an alternative characterization of system behavior by drawing upon ideas from the field of relevance logic. this secondary characterization, which we call relevance analysis, specifies a direct relationship between unannotated documents and the context-free grammars that our system can generate from them. relevance analysis allows us to prove important theorems concerning the expressiveness and utility of our system.
decoupled lifeguards: enabling path optimizations for dynamic correctness checking tools. dynamic correctness checking tools (a.k.a. lifeguards) can detect a wide array of correctness issues, such as memory, security, and concurrency misbehavior, in unmodified executables at run time. however, lifeguards that are implemented using dynamic binary instrumentation (dbi) often slow down the monitored application by 10-50x, while proposals that replace dbi with hardware still see 3-8x slowdowns. the remaining overhead is the cost of performing the lifeguard analysis itself. in this paper, we explore compiler optimization techniques to reduce this overhead. the lifeguard software is typically structured as a set of event-driven handlers, where the events are individual instructions in the monitored application's dynamic instruction stream. we propose to decouple the lifeguard checking code from the application that it is monitoring so that the lifeguard analysis can be invoked at the granularity of hot paths in the monitored application. in this way, we are able to find many more opportunities for eliminating redundant work in the lifeguard analysis, even starting with well-optimized applications and hand-tuned lifeguard handlers. experimental results with two lifeguard frameworks - one dbi-based and one hardware-assisted - show significant reduction in monitoring overhead.