Author name cluster

Rami Puzis

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers

2 author rows

SoCS Conference 2018 Conference Paper

Focused SANA: Speeding Up Network Alignment

Ilia Leybovich
Rami Puzis
Roni Stern
Maor Reuben

Network Alignment (NA) is a generalization of the graph isomorphism problem for non-isomorphic graphs, where the goal is to find a node mapping as close as possible to isomorphism. Recent successful NA algorithms follow a search-based approach, such as simulated annealing. We propose to speed up search-based NA algorithms by pruning the search-space based on heuristic rules derived from the topological features of the aligned nodes. We define several desirable properties of such pruning rules, analyze them theoretically, and propose a pruning rule based on nodes

Details

IS Journal 2018 Journal Article

Transfer Learning for User Action Identication in Mobile Apps via Encrypted Trafc Analysis

Edita Grolman
Andrey Finkelshtein
Rami Puzis
Asaf Shabtai
Gershon Celniker
Ziv Katzir
Liron Rosenfeld

Recent academic studies have demonstrated the possibility of inferring user actions performed in mobile apps by analyzing the resulting encrypted network traffic. Due to the multitude of app versions, mobile operating systems, and device models (collectively referred to in this paper as configurations) previous approaches are not applicable to real life settings. In this work, we ex-tend the ability of these approaches to generalize across different configurations. We treat the different configurations as a case for transfer learning, and adapt the co-training method to sup-port the transfer learning process. Our approach leverages a small number of labeled instances of encrypted traffic from a source configuration, in order to construct a classifier capable of identi-fying a users actions in a different (target) configuration which is completely unlabeled. Experi-ments on real datasets collected from different applications on Android devices show that the proposed method achieves F1 measures over 0. 8 for most of the considered user actions.

Details DOI

SoCS Conference 2015 Conference Paper

Confidence Backup Updates for Aggregating MDP State Values in Monte-Carlo Tree Search

Zahy Bnaya
Alon Palombo
Rami Puzis
Ariel Felner

Monte-Carlo Tree Search (MCTS) algorithms estimate the value of MDP states based on rewards received by performing multiple random simulations. MCTS algorithms can use different strategies to aggregate these rewards and provide an estimation for the states’ values. The most common aggregation method is to store the mean reward of all simulations. Another common approach stores the best observed reward from each state. Both of these methods have complementary benefits and drawbacks. In this paper, we show that both of these methods are biased estimators for the real expected value of MDP states. We propose an hybrid approach that uses the best reward for states with low noise, and otherwise uses the mean. Experimental results on the Sailing MDP domain show that our method has a considerable advantage when the rewards are drawn from a noisy distribution.

Details

IJCAI Conference 2015 Conference Paper

Max Is More than Min: Solving Maximization Problems with Heuristic Search

Roni Stern
Scott Kiesel
Rami Puzis
Ariel Felner
Wheeler Ruml

Most work in heuristic search considers problems where a low cost solution is preferred (MIN problems). In this paper, we investigate the complementary setting where a solution of high reward is preferred (MAX problems). Example MAX problems include finding a longest simple path in a graph, maximal coverage, and various constraint optimization problems. We examine several popular search algorithms for MIN problems and discover the curious ways in which they misbehave on MAX problems. We propose modifications that preserve the original intentions behind the algorithms but allow them to solve MAX problems, and compare them theoretically and empirically. Interesting results include the failure of bidirectional search and close relationships between Dijkstra’s algorithm, weighted A*, and depth-first search.

PDF Details

SoCS Conference 2015 Conference Paper

Solving the Snake in the Box Problem with Heuristic Search: First Results

Alon Palombo
Roni Stern
Rami Puzis
Ariel Felner
Scott Kiesel
Wheeler Ruml

Snake in the Box (SIB) is the problem of finding the longest simple path along the edges of an n-dimensional cube, subject to certain constraints. SIB has important applications in coding theory and communications. State of the art algorithms for solving SIB apply uninformed search with symmetry breaking techniques. We formalize this problem as a search problem and propose several admissible heuristics to solve it. Using the proposed heuristics is shown to have a huge impact on the number of nodes expanded and, in some configurations, on runtime. These results encourage further research in using heuristic search to solve SIB, and to solve maximization problems more generally.

Details

SoCS Conference 2014 Conference Paper

Extended Framework for Target Oriented Network Intelligence Collection

Liron Samama-Kachko
Rami Puzis
Roni Stern
Ariel Felner

The Target Oriented Network Intelligence Collection (TONIC) problem is the problem of finding profiles in a social network that contain publicly available information about a given target profile via automated crawling. Such profiles are called leads. Leads can be found by crawling the network using the profiles

Details

SoCS Conference 2014 Conference Paper

Max is More than Min: Solving Maximization Problems with Heuristic Search

Roni Stern
Scott Kiesel
Rami Puzis
Ariel Felner
Wheeler Ruml

Most work in heuristic search considers problems where a low cost solution is preferred (MIN problems). In this paper, we investigate the complementary setting where a solution of high reward is preferred (MAX problems). Example MAX problems include finding the longest simple path in a graph, maximal coverage, and various constraint optimization problems. We examine several popular search algorithms for MIN problems — optimal, suboptimal, and bounded suboptimal - and discover the curious ways in which they misbehave on MAX problems. We propose modifications that preserve the original intentions behind the algorithms but allow them to solve MAX problems, and compare them theoretically and empirically. Interesting results include the failure of bidirectional search and a discovered close relationships between Dijkstra

Details

AIJ Journal 2014 Journal Article

Potential-based bounded-cost search and Anytime Non-Parametric A ⁎

Roni Stern
Ariel Felner
Jur van den Berg
Rami Puzis
Rajat Shah
Ken Goldberg

This paper presents two new search algorithms: Potential Search (PTS) and Anytime Potential Search/Anytime Non-Parametric A ⁎ ( APTS/ANA ⁎ ). Both algorithms are based on a new evaluation function that is easy to implement and does not require user-tuned parameters. PTS is designed to solve bounded-cost search problems, which are problems where the task is to find as fast as possible a solution under a given cost bound. APTS/ANA ⁎ is a non-parametric anytime search algorithm discovered independently by two research groups via two very different derivations. In this paper, co-authored by researchers from both groups, we present these derivations: as a sequence of calls to PTS and as a non-parametric greedy variant of Anytime Repairing A ⁎. We describe experiments that evaluate the new algorithms in the 15-puzzle, KPP-COM, robot motion planning, gridworld navigation, and multiple sequence alignment search domains. Our results suggest that when compared with previous anytime algorithms, APTS/ANA ⁎: (1) does not require user-set parameters, (2) finds an initial solution faster, (3) spends less time between solution improvements, (4) decreases the suboptimality bound of the current-best solution more gradually, and (5) converges faster to an optimal solution when reachable.

Details DOI

TIST Journal 2013 Journal Article

Computationally efficient link prediction in a variety of social networks

Michael Fire
Lena Tenenboim-Chekina
Rami Puzis
Ofrit Lesser
Lior Rokach
Yuval Elovici

Online social networking sites have become increasingly popular over the last few years. As a result, new interdisciplinary research directions have emerged in which social network analysis methods are applied to networks containing hundreds of millions of users. Unfortunately, links between individuals may be missing either due to an imperfect acquirement process or because they are not yet reflected in the online network (i.e., friends in the real world did not form a virtual connection). The primary bottleneck in link prediction techniques is extracting the structural features required for classifying links. In this article, we propose a set of simple, easy-to-compute structural features that can be analyzed to identify missing links. We show that by using simple structural features, a machine learning classifier can successfully identify missing links, even when applied to a predicament of classifying links between individuals with at least one common friend. We also present a method for calculating the amount of data needed in order to build more accurate classifiers. The new Friends measure and Same community features we developed are shown to be good predictors for missing links. An evaluation experiment was performed on ten large social networks datasets: Academia.edu, DBLP, Facebook, Flickr, Flixster, Google+, Gowalla, TheMarker, Twitter, and YouTube. Our methods can provide social network site operators with the capability of helping users to find known, offline contacts and to discover new friends online. They may also be used for exposing hidden links in online social networks.

Details DOI

AAAI Conference 2013 Conference Paper

TONIC: Target Oriented Network Intelligence Collection for the Social Web

Roni Stern
Liron Samama
Rami Puzis
Tal Beja
Zahy Bnaya
Ariel Felner

In this paper we introduce the Target Oriented Network Intelligence Collection (TONIC) problem, which is the problem of finding profiles in a social network that contain information about a given target via automated crawling. We formalize TONIC as a search problem and a best-first approach is proposed for solving it. Several heuristics are presented to guide this search. These heuristics are based on the topology of the currently known part of the social network. The efficiency of the proposed heuristics and the effect of the graph topology on their performance is experimentally evaluated on the Google+ social network.

PDF Details

ICAPS Conference 2011 Conference Paper

Potential Search: A Bounded-Cost Search Algorithm

Roni Stern
Rami Puzis
Ariel Felner

In this paper we address the following search task: find a goal with cost smaller than or equal to a given fixed constant. This task is relevant in scenarios where a fixed budget is available to execute a plan and we would like to find such a plan with minimum search effort. We introduce an algorithm called Potential search (PTS) which is specifically designed to solve this problem. PTS is a best-first search that expands nodes according to the probability that they will be part of a plan whose cost is less than or equal to the given budget. We show that it is possible to implement PTS even without explicitly calculating these probabilities, when a heuristic function and knowledge about the error of this heuristic function are given. In addition, we also show that PTS can be modified to an anytime search algorithm. Experimental results show that PTS outperforms other relevant algorithms in most cases, and is more robust.

Details

SoCS Conference 2010 Conference Paper

Potential Search: A New Greedy Anytime Heuristic Search

Roni Stern
Rami Puzis
Ariel Felner

In this paper we explore a novel approach for anytime heuristic search, in which the node that is most probable to improve the incumbent solution is expanded first. This is especially suited for the "anytime aspect" of anytime algorithms - the possibility that the algorithm will be be halted anytime throughout the search. The potential of a node to improve the incumbent solution is estimated by a custom cost function, resulting in Potential Search, an anytime best-first search. Experimental results on the 15-puzzle and on the key player problem in communication networks (KPP-COM) show that this approach is competitive with state-of-the-art anytime heuristic search algorithms, and is more robust.

Details