Wellcome to Sergey Kirgizov's library,

  You can find here all papers liked or uploaded by Sergey Kirgizov
  together with brief user bio and description of her/his academic activity.


Browse to my personsal site http://kirgizov.link if you wish so.

Comments:

Continuing the series of articles (... well actually is just the second one) on restricted combinatorial objects constrained by a recursively defined statistic and initiated by [this work](https://papers-gamma.link/paper/38/Dyck%20paths%20with%20a%20first%20return%20decomposition%20constrained%20by%20height) we submitted to review a new paper of subject.
Read the paper, add your comments…

Comments:

##To take away:## - This paper is about a slight improvement of the $k$-clique Algorithm of Chiba and Nishizeki - The performance in practice on sparse graphs is impressive - The parallelization is non-trivial and the speedup is nearly optimal up to 40 threads - Authors generate a stream of k-cliques to compute "compact" subgraphs - A parallel C code is available here: https://github.com/maxdan94/kClist ##Suggestions to extend this work:## - Can we find a node ordering better than the core ordering? - Generate a stream of $k$-cliques to compute other quantities? - Generalize the algorithm to $k$-motifs? - Parallelization on higher order $k$-cliques if more threads are available?
Slides of the talk: https://drive.google.com/file/d/15MVJ2TzkdsHcyF6tE4VeYQqH8bU0kzDE/view
Another extension: can we guarantee a given order on the output stream? that it is uniformly random, for instance?
> Another extension: can we guarantee a given order on the output stream? that it is uniformly random, for instance? I think that this is a very interesting and open question! I have tried to generate a stream of k-cliques such that the order is random by modifying the kClist algorithm. But I was not able to do so. I wanted to do that in order to optimize a function depending on the k-cliques using stochastic gradient descent. I have found that using a random ordering lead to a faster convergence than using the order the k-cliques are outputed by the kClist algorithm. Here is what I've tried: - If you have enough RAM, then you can of course store all k-cliques and do a [random permutation](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle). But, since you mention "steam", I do not think that this is the case for you. - You can use another node-ordering (different from the core-ordering) to form the DAG. You can use, for instance, a random node ordering. You may lose the theoretical upperbound on the running time, but you will see that, in practice, the algorithm is still very fast (say twice slower than with the core ordering (but this depends on the input graph and k, you may also find some settings where it is actually faster than with the core ordering)). The order the k-cliques are stream will then change, but it will not be uniform at random. - Once you have formed the DAG using the node ordering (core ordering or any other ordering), you do not need to process the nodes in that same order. You can use another random ordering for that. It will add some randomness in the stream, but the order will still not be uniform at random. Please let me know if you have any better ideas.
Read the paper, add your comments…

Comments:

The paper describes the architecture of YouTube current recommendation system (as of 2016), based on Deep Learning, which replaced the previous Matrix Factorization based architecture (ref 23). The architecture uses Google Brain's TensorFlow tool and achieves significantly better than the former one (see fig6 for example). The paper is a high-level description of the architecture, and sometimes lack the technical details which would allow a precise understanding. However, it provides very interesting ideas about the problems faced and solutions contemplated by YouTube engineers and of actual constraints with industrial recommendation systems. It also helps realizing that there is as much craft as science in the process. Overall, the architecture consists of two main phases : - a coarse candidate generation (creating a set of a few hundred videos per user from the corpus of several million videos available), - precise ranking of the candidates. Both steps use a DNN architecture. Some technical details : - user profile is summarized as a heterogeneous embedding of identifiers of videos watched, demographic information, search tokens, etc. - a decisive advantage of DNN put into light in the paper is their ability to deal with heterogeneous signal (sources of information of various nature), another is that it (partly) circumvents feature manufacturing - while development of the method calls to offline evaluation metrics (precision, recall, etc.), the final evaluation relies on live A/B testing experiments, the discussion related to this point in Sec 3.4 is very interesting - for candidate generation, YouTube uses implicit feedback information (e.g. watch times) rather than explicit feedback (e.g. thumb up) because there is more information available - taking into account the "freshness" of a video has an important impact on the efficacy of the candidate generation (fig 4) - taking into account the context of a watch (meaning the sequence of watch) is also important as co-watch distribution probability is very asymmetric, in particular taking into account the previous action of a user related to similar items matters
There is no 👍-style explicit feedback for the comments yet. So, I'll use the implicit one. Alt-Tab's comment is a very condensed one, it matters, I even think that this comment is better than the orignal article abstract. Now I really want to drop everything, sit down and read this article in details.
Read the paper, add your comments…
Pages: 1 2 3 4 5 6 7