This paper introduces the Generalized Naive Bayes (GNB) structure as an extension of the Naive Bayes structure. We give two new greedy algorithms to find the possible closest GNB structure to the data in terms of minimizing Kullback-Leibler divergence between the probability distribution corresponding to the GNB structure and the data. Both algorithms focus on determining the best-fitting GNB structure based on the training data. The first algorithm adopts a greedy approach to find a good-fitting GNB probability distribution. Then, we introduce a second algorithm, which we prove finds the optimal (best-fitting) GNB probability distribution on the training set under a non-restrictive condition. Based on these algorithms, new feature importance scores and feature selection methods are introduced. The algorithms are compared from theoretical and practical points of view with other probabilistic graphical model-based algorithms.

Quantifying uncertainty is an essential part of predictive modeling, especially in the context of high-stakes decision-making. While classification output includes data uncertainty by design in the form of class probabilities, the regression task generally aims only to predict the expected value of the target variable. Probabilistic extensions often assume parametric distributions around the expected value, optimizing the likelihood over the resulting explicit densities. However, using parametric distributions can limit practical applicability, making it difficult for models to capture skewed, multi-modal, or otherwise complex distributions. In this paper, we propose optimizing a novel nondeterministic neural network regression architecture for loss functions derived from a sample-based approximation of the continuous ranked probability score (CRPS), enabling a truly distribution-free approach by learning to sample from the target's aleatoric distribution, rather than predicting explicit densities. Our approach allows the model to learn well-calibrated, arbitrary uni- and multivariate output distributions. We evaluate the method on a variety of synthetic and real-world tasks, including uni- and multivariate problems, function inverse approximation, and standard regression uncertainty benchmarks. Finally, we make all experiment code publicly available.

In this work, we examine Asymmetric Shapley Values (ASV), a variant of the popular SHAP additive local explanation method. ASV proposes a way to improve model explanations incorporating known causal relations between variables, and is also considered as a way to test for unfair discrimination in model predictions. Unexplored in previous literature, relaxing symmetry in Shapley values can have counter-intuitive consequences for model explanation. To better understand the method, we first show how local contributions correspond to global contributions of variance reduction. Using variance, we demonstrate multiple cases where ASV yields counter-intuitive attributions, arguably producing incorrect results for root-cause analysis. Second, we identify generalized additive models (GAM) as a restricted class for which ASV exhibits desirable properties. We support our arguments by proving multiple theoretical results about the method. Finally, we demonstrate the use of asymmetric attributions on multiple real-world datasets, comparing the results with and without restricted model families using gradient boosting and deep learning models.

The novelty of the paper is that we introduce extended relational schemas defined by context-free languages. This allows us to specify schemas that include nested relations. The representation of regular expressions with the graph made it possible to specify both relational algebraic operations and dependencies. This paper uses extended context-free languages to define schema graphs, constructed from the regular expressions specifying the right side of the production rules. This is exploited by representing context-free grammars with recursive, increasing graphs. Next, we introduce the use of a context-free language to specify extended relational schemas with ordinary and nested attributes. In the derivation rules of the grammar, terminal symbols give ordinary attributes, while non-terminal (linguistic) symbols give nested attributes. Regular expressions can use both terminal and linguistic symbols. We can define schemas with finite derivations of rules. In the accepted symbol sequences, the terminal symbols give the ordinary attributes and the language symbols the nested attributes. For a nested attribute we must assign a schema with the appropriate rule. No embedded attribute may remain at the end. The relational row type and the finite occurrence of rows of this type can be defined as instance for the resulting schema. We define set operations and nested database operations as well. Functional dependencies can be defined and examined at multiple depths.

Recommender systems have to serve in online environments that can be non-stationary. Traditional recommender algorithms may periodically rebuild their models, but they cannot adjust to quick changes in trends caused by timely information. In contrast, online learning models can adopt to temporal effects, hence they may overcome the effect of concept drift.

We analyze the fine-grained connections between the average degree and the power-law degree distribution exponent in growing information networks. Our starting observation is a power-law degree distribution with a decreasing exponent and increasing average degree as a function of the network size. Our experiments are based on three Twitter at-mention networks and three more from the Koblenz Network Collection. We observe that popular network models cannot explain decreasing power-law degree distribution exponent and increasing average degree at the same time.

The 2016 ACM Recommender Systems Challenge focused on the problem of job recommendations. Given a large dataset from XING that consisted of anonymized user profiles, job postings, and interactions between them, the participating teams had to predict postings that a user will interact with. The challenge ran for four months with 366 registered teams. 119 of those teams actively participated and submitted together 4,232 solutions yielding in an impressive neck-and-neck race that was decided within the last days of the challenge.

This paper introduces a generalized data base concept that unites relational and semi structured data models. As an important theoretical result we could find a quadratic decision algorithm for the implication problem of functional and join dependencies defined on the united data model. As practical contribution we presented a normal form for the new data model as a tool for data base design. With our novel representations of regular expressions, a more effective searching method could be developed. XML elements are described by XML schema languages such as a DTD or an XML Schema definition. The instances of these elements are semi-structured tuples. A semi-structured tuple is an ordered list of (attribute: value) pairs. We may think of a semi-structured tuple as a sentence of a formal language, where the values are the terminal symbols and the attribute names are the non-terminal symbols. In the authors' former work (Szabó and Benczúr, 2015) they introduced the notion of the extended tuple as a sentence from a regular language generated by a grammar where the non-terminal symbols of the grammar are the attribute names of the tuple. Sets of extended tuples are the extended relations. The authors then introduced the dual language, which generates the tuple types allowed to occur in extended relations. They defined functional dependencies (regular FD - RFD) over extended relations. In this paper they rephrase the RFD concept by directly using regular expressions over attribute names to define extended tuples. By the help of a special vertex labeled graph associated to regular expressions the specification of substring selection for the projection operation can be defined. The normalization for regular schemas is more complex than it is in the relational model, because the schema of an extended relation can contain an infinite number of tuple types. However, the authors can define selection, projection and join operations on extended relations too, so a lossless-join decomposition can be performed. They extended their previous model to deal with XML schema indicators too, e.g., with numerical constraints. They added line and set constructors too, in order to extend their model with more general projection and selection operators. This model establishes a query language with table join functionality for collected XML element data.

Low-rank matrix approximation is an important tool in data mining with a wide range of applications, including recommender systems, clustering, and identifying topics in documents. When the matrix to be approximated originates from a large distributed system, such as a network of mobile phones or smart meters, a challenging problem arises due to the strongly conflicting yet essential requirements of efficiency, robustness, and privacy preservation. We argue that although collecting sensitive data in a centralized fashion may be efficient, it is not an option when considering privacy and efficiency at the same time. Thus, we do not allow any sensitive data to leave the nodes of the network. The local information at each node (personal attributes, documents, media ratings, etc.) defines one row in the matrix. This means that all computations have to be performed at the edge of the network. Known parallel methods that respect the locality constraint, such as synchronized parallel gradient search or distributed iterative methods, require synchronized rounds or have inherent issues with load balancing, and thus they are not robust to failure. Our distributed stochastic gradient descent algorithm overcomes these limitations. During the execution, any sensitive information remains local, whereas the global features (e.g., the factor model of movies) converge to the correct value at all nodes. We present a theoretical derivation and a thorough experimental evaluation of our algorithm. We demonstrate that the convergence speed of our method is competitive while not relying on synchronization and being robust to extreme and realistic failure scenarios. To demonstrate the feasibility of our approach, we present trace-based simulations, real smartphone user behavior analysis, and tests over real movie recommender system data.

Abnormal bearer session release (i.e. bearer session drop) in cellular telecommunication networks may seriously impact the quality of experience of mobile users. The latest mobile technologies enable high granularity real-time reporting of all conditions of individual sessions, which gives rise to use data analytics methods to process and monetize this data for network optimization. One such example for analytics is Machine Learning (ML) to predict session drops well before the end of session. In this paper a novel ML method is presented that is able to predict session drops with higher accuracy than using traditional models. The method is applied and tested on live LTE data offline. The high accuracy predictor can be part of a SON function in order to eliminate the session drops or mitigate their effects.

We describe random sampling techniques for approximately solving problems that involve cuts and flows in graphs. We give a near-linear-time randomized combinatorial construction that transforms any graph on $n$ vertices into an $O(n\log n)$-edge graph on the same vertices whose cuts have approximately the same value as the original graph's. In this new graph, for example, we can run the $\tilde{O}(m^{3/2})$-time maximum flow algorithm of Goldberg and Rao to find an $s$-$t$ minimum cut in $\tilde{O}(n^{3/2})$ time. This corresponds to a $(1+\epsilon)$-times minimum $s$-$t$ cut in the original graph. A related approach leads to a randomized divide-and-conquer algorithm producing an approximately maximum flow in $\tilde{O}(m\sqrt{n})$ time. Our algorithm can also be used to improve the running time of sparsest cut approximation algorithms from $\tilde{O}(mn)$ to $\tilde{O}(n^2)$ and to accelerate several other recent cut and flow algorithms. Our algorithms are based on a general theorem analyzing the concentration of random graphs' cut values near their expectations. Our work draws only on elementary probability and graph theory.

Low-rank matrix approximation is an important tool in data mining with a wide range of applications including recommender systems, clustering, and identifying topics in documents. The problem we tackle is implementing singular value decomposition (SVD)-a popular method for low rank approximation in large fully distributed P2P systems in a robust and scalable manner. We assume that the matrix to be approximated is stored in a large network where each node knows one row of the matrix (personal attributes, documents, media ratings, etc). In our P2P model, we do not allow this personal information to leave the node, yet we want the nodes to collaboratively compute the SVD. Methods applied in large scale distributed systems such as synchronized parallel gradient search or distributed iterative methods are not preferable in our system model due to their requirements of synchronized rounds or their inherent issues with load balancing. Our approach overcomes these limitations with the help of a distributed stochastic gradient search in which the personal part of the decomposition remains local, and the global part (e.g., movie features) converges at all nodes to the correct value. We present a theoretical derivation of our algorithm, as well as a thorough experimental evaluation of real and synthetic data as well. We demonstrate that the convergence speed of our method is competitive while not relying on synchronization and being robust to extreme failure scenarios.

In this paper we give methods for time-aware music recommendation in a social media service with the potential of exploiting immediate temporal influences between users. We consider events when a user listens to an artist the first time and this event follows some friend listening to the same artist short time before. We train a blend of matrix factorization methods that model the relation of the influencer, the influenced and the artist, both the individual factor decompositions and their weight learned by variants of stochastic gradient descent (SGD). Special care is taken since events of influence form a subset of the positive implicit feedback data and hence we have to cope with two different definitions of the positive and negative implicit training data. In addition, in the time-aware setting we have to use online learning and evaluation methods. While SGD can easily be trained online, evaluation is cumbersome by traditional measures since we will have potentially different top recommendations at different times. Our experiments are carried over the two-year "scrobble" history of 70,000 Last.fm users and show a 5% increase in recommendation quality by predicting temporal influences.

Several recent results show the influence of social contacts to spread certain properties over the network, but others question the methodology of these experiments by proposing that the measured effects may be due to homophily or a shared environment. In this paper we justify the existence of the social influence by considering the temporal behavior of Last.fm users. In order to clearly distinguish between friends sharing the same interest, especially since Last.fm recommends friends based on similarity of taste, we separated the timeless effect of similar taste from the temporal impulses of immediately listening to the same artist after a friend. We measured strong increase of listening to a completely new artist in a few hours period after a friend compared to non-friends representing a simple trend or external influence. In our experiment to eliminate network independent elements of taste, we improved collaborative filtering and trend based methods by blending with simple time aware recommendations based on the influence of friends. Our experiments are carried over the two-year "scrobble" history of 70,000 Last.fm users.

Location prediction over mobility traces may find applications in navigation, traffic optimization, city planning and smart cities. Due to the scale of the mobility in a metropolis, real time processing is one of the major Big Data challenges. In this paper we deploy distributed streaming algorithms and infrastructures to process large scale mobility data for fast reaction time prediction. We evaluate our methods on a data set derived from the Orange D4D Challenge data representing sample traces of Ivory Coast mobile phone users. Our results open the possibility for efficient real time mobility predictions of even large metropolitan areas.

In their seminal paper, Frank and Jordán [1995] show that a large class of optimization problems, including certain directed graph augmentation, fall into the class of covering supermodular functions over pairs of sets. They also give an algorithm for such problems, however, it relies on the ellipsoid method. Prior to our result, combinatorial algorithms existed only for the 0--1 valued problem. Our key result is a combinatorial algorithm for the general problem that includes directed vertex or S − T connectivity augmentation. The algorithm is based on Benczúr's previous algorithm for the 0--1 valued case [Benczúr 2003]. Our algorithm uses a primal-dual scheme for finding covers of partially ordered sets that satisfy natural abstract properties as in Frank and Jordán. For an initial (possibly greedy) cover, the algorithm searches for witnesses for the necessity of each element in the cover. If no two (weighted) witnesses have a common cover, the solution is optimal. As long as this is not the case, the witnesses are gradually exchanged for smaller ones. Each witness change defines an appropriate change in the solution; these changes are finally unwound in a shortest-path manner to obtain a solution of size one less.

In this short note we demonstrate the applicability of hyperlink downweighting by means of language model disagreement. The method filters out hyperlinks with no relevance to the target page without the need of white and blacklists or human interaction. We fight various forms of nepotism such as common maintainers, ads, link exchanges or misused affiliate programs. Our method is tested on a 31 M page crawl of the .de domain with a manually classified 1000-page random sample.

Personalized PageRank expresses link-based page quality around user selected pages. The only previous personalized PageRank algorithm that can serve on-line queries for an unrestricted choice of pages on large graphs is our Monte Carlo algorithm [WAW 2004]. In this paper we achieve unrestricted personalization by combining rounding and randomized sketching techniques in the dynamic programming algorithm of Jeh and Widom [WWW 2003]. We evaluate the precision of approximation experimentally on large scale real-world data and find significant improvement over previous results. As a key theoretical contribution we show that our algorithms use an optimal amount of space by also improving earlier asymptotic worst-case lower bounds. Our lower bounds and algorithms apply to the SimRank as well; of independent interest is the reduction of the SimRank computation to personalized PageRank.

Feature selection proved to improve both the speed and the quality of classification. Methods such as mutual information, information gain or chi-square are all based on the joint distribution of classes and words; there exist only a few methods which exploit contextual information for feature selection. We introduce an algorithm based on word and word pair frequencies that reduces both vocabulary and total word size prior to classification. We measure the effectiveness of our algorithm by clustering Ken Lang's 20 newsgroups corpus and obtain significantly better size reduction than the state-of-the-art methods. We perform keyword selection by identifying correlated word pairs within sentences; measuring how strongly a word in a given document takes part in such pairs; finally selecting those keywords that take part in several such pairs in several documents.

We improve on random sampling techniques for approximately solving problems that involve cuts in graphs. We give a linear-time construction that transforms any graph on n vertices into an O(n log n)-edge graph on the same vertices whose cuts have approximately the same value as the original graph’s. In this new graph, for example, we can run the Õ(mn)-time maximum flow algorithm of Goldberg and Tarjan to find an s–t minimum cut in Õ(n²) time. This corresponds to a(1+)-times minimum s–t cut in the original graph. In a similar way, we can approximate a sparsest cut in Õ(n²) time.

Let G be an undirected c-edge connected graph. In this paper we give an O(n/sup 2/)-sized planar geometric representation for all edge cuts with capacity less than 6/5c. The representation can be very efficiently built, by using a single run of the Karger-Stein algorithm for finding near-mincuts. We demonstrate that the representation provides an efficient query structure for near-mincuts, as well as a new proof technique through geometric arguments. We show that in algorithms based on edge splitting, computing our representation O(log n) times substitute for one, or sometimes even /spl Omega/(n), u-/spl nu/ mincut computations; this can lead to significant savings, since our representation can be computed /spl theta//spl tilde/(m/n) times faster than the currently best known u-/spl nu/ mincut algorithm. We also improve the running time of the edge augmentation problem, provided the initial edge weights are polynomially bounded.

We show that there is no cut-tree for various connectivity concepts, hence pointing out errors in the papers of Schnorr [SIAM J. Comput., 8 (1979), pp. 265–275] and Gusfield and Naor [Networks, 21 (1991), pp. 505–520]. Gomory and Hu [SIAM J. Appl. Math., 9 (1961), pp. 551–560] constructed a cut-tree for undirected graphs which compactly represents a minimum cut for each pair of vertices. This has a straightforward generalization to directed Eulerian graphs, cf. Gupta [SIAM J. Appl. Math., 15 (1967), pp. 168–171]. A generalization for arbitrary directed graphs was given by Schnorr. There is a well-known transformation of vertex connectivity to directed edge connectivity; directed edge cuts correspond to vertex cuts in some weak sense. The result of Schnorr was later applied by Gusfield and Naor for such a cut-tree construction. In this paper counterexamples are described to show that for directed graphs there is no cut-tree and therefore the cut-tree results of Schnorr and Gusfield and Naor are incorrect. Our final example shows that, without weakening the notion of vertex connectivity, it is impossible to construct vertex cut-trees for undirected graphs in general.

Article Free Access Share on Augmenting undirected connectivity in RNC and in randomized Õ(n3) time Author: András A. Benczúr Department of Mathematics, MIT, Cambridge MA Department of Mathematics, MIT, Cambridge MAView Profile Authors Info & Claims STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of ComputingMay 1994 Pages 658–667https://doi.org/10.1145/195058.195425Online:23 May 1994Publication History 10citation198DownloadsMetricsTotal Citations10Total Downloads198Last 12 Months11Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF