COMPSCI 753
COMPUTER SCIENCE
SEMESTER TWO, 2023
1 Locality-Sensitive Hashing [25 marks]
Given four documents S1 , S2 , S3 , S4 and a customized query document q:
S1 = {c, f}, S2 = {a, b}, S3 = {d, e}, S4 = {a,c, e}, q = {a,c, e};
1.1 Computing MinHash Signatures [10 marks]
(a) Generate the bit-vector representation for {S1 , S2 , S3 , S4 , q} in shingle space {a,b,c,d,e, f}. [3 marks]
(b) Generate the MinHash matrix for {S1 , S2 , S3 , q} using the following four MinHash functions. [5 marks]
h1 (x) = (2x + 1) mod 6
h2 (x) = (3x + 2) mod 6
h3 (x) = (5x + 2) mod 6
(c) Among the hash functions, h1 , h2 , h3 , which one gives the true simulated permutation? [1 marks]
(d) Consider the query q and estimate the signature-based Jaccard similarities: J(q, S1 ). [1 marks]
1.2 Tuning Parameters for rNNS [10 marks]
Recall the collision probability (i.e., S-curve) given the number of bands b and the number of rows per band r as follows:
Pr(s) = 1 - (1 - sr )b
Consider three sets of parameters (r=3,b=10), (r=6,b=20), (r=5,b=50). The collision prob- abilities for similarity s in range of [0,1] for each (r ,b) are provided accordingly in the table below. Please answer the following two questions.
(a) Which settings give at most 5% of false negatives for any 70%-similar pairs? Please briefly explain your answer. [5 marks]
(b) Which settings give at most 15% of false positives for any 30%-similar pairs? Please briefly explain your answer. [5 marks]
1.3 c-Approximate Randomized rNNS [5 marks]
Recall that a family of functions H is called (d1 , d2 , p1 , p2 )-sensitive with collision probability p1 > p2 and c > 1 if the following conditions hold for any uniformly chosen h ∈ H and 8 x, y ∈ U :
• If d(x, y) ≤ r , Pr[h(x) = h(y)] ≥ p1 for similar points, and
• If d(x, y) ≥ cr , Pr[h(x) = h(y)] ≤ p2 for dissimilar points.
(a) How can we further transform the upper bound probability approaching 1? How can we further transform the lower bound probability approaching 0? [2 marks]
(b) Consider a set of movie plot articles (D), and a set of queries (Q). You have con- structed Locality-Sensitive Hashing (LSH) frameworks for varying hash sizes with k ∈ {2, 4, 8, 16}. To evaluate the impact of k on Jaccard similarity estimation, you computed the mean absolute error (MAE) for pairs of articles (di , q), where di ∈ D and q ∈ Q, and obtained the MAE plot below. Please comment on your MAE plot. (Note: You can assume that your implementation is correct.) [3 marks]
2 Data Stream Algorithms [25 marks]
2.1 Bloom Filter [6 marks]
(a) Consider the following statement: “The Bloom filter can determine the existence of items, allowing the possibility of false positive responses and false negative responses.” Is it true, false or unknown? Please briefly explain your answer. [3 marks]
(b) Name two approaches to reduce the possibility of false positives. Please briefly explain your answer. [3 marks]
2.2 Misra-Gries Algorithm [5 marks]
(a) Consider the given data stream. Implement the Misra-Gries algorithm with k = 4 counters. Provide a comprehensive summary, including the elements and their corre- sponding counter values, once the execution of the algorithm is completed. [3 marks]
S = {45, 13, 14, 45, 7, 10, 45, 6}
(b) What would the theoretical number of decrement steps be triggered after processing the above stream in question (a)? [2 marks]
2.3 Count Sketch Algorithm [14 marks]
Consider the same data stream S and hash functions below. Using the given sign hash functions below, apply the Count Sketch algorithm and present the following:
(a) Hash Table. [5 marks]
(b) Counter Matrix. [5 marks]
(c) Final estimated frequency of each element once the execution of the algorithm is completed. Please comment on your estimated frequency against the true frequency. [4 marks]
3 Algorithms for Graphs [25 marks]
3.1 Web Graphs [12 marks]
Given the following raw adjacency matrix A:
(a) Convert A into its corresponding column-stochastic matrix M. [4 marks]
(b) In the lecture, we have shown that the PageRank r = M · r is the eigenvector of the column-stochastic matrix M corresponding to eigenvalue λ = 1. Compute the PageRank of all nodes in the above graph using the eigen-equation and report the values of the r vector. [4 marks]
(c) The power iteration algorithm is an iterative method to solve PageRank. Explain:
1) how does the algorithm perform updates in each iteration? 2) what are the stop criteria and required initializations? [4 marks]
3.2 Community Detection [8 marks]
Given the following undirected graph:
(a) Compute the edge betweeness of each edge ({ea ; eb ; ec ; ed }) using Brandes’ algorithm, only for the case when node 1 is taken as the root node. [4 marks]
(b) Apart from edge betweeness and modularity maximization, spectral graph partition- ing is another method for community detection that works by solving the problem miny∈Rn yT Ly, with L the Laplacian matrix. Explain: 1) how is the Laplacian matrix calculated, 2) how can eigenvalue decomposition be used to solve this minimization problem. [4 marks]
3.3 Influence Maximization [5 marks]
Given the following directed graph:
(a) Consider the set S = {1} as the seed set. Compute the contingency table for the graph. [3 marks]
(b) Using the contingency table calculated in the previous step, compute the influence spread under the Independent Cascade (IC) model. [2 marks]
4 Recommender Systems [25 marks]
4.1 Memory-Based Collaborative Filtering [10 marks]
Given the following user-interaction matrix of users {u1 , u2 , u3 , u4 , u5 } and items {p1 , p2 , p3 , p4 }:
(a) Based on these ratings from users to items, which user is most similar to user u2 if you consider cosine similarity? How does this information help you to provide recommendations to user u2 if you were to use the user-based collaborative filtering algorithm? [4 marks]
(b) Calculate: 1) the global bias (bg), 2) the user bias for user u2 (bu(ser)), and 3) the item bias for item p1 (bp(i1tem)). [3 marks]
(c) Suppose that you used one of the memory-based recommendation algorithms learned in lectures to calculate predicted ratings of users over item p1 . You obtained the following comparison of predicted vs. actual ratings:
Calculate the root mean squared error (RMSE) metric of the above table (report the RMSE using two decimal digits). [3 marks]
4.2 Model-based Collaborative Filtering [8 marks]
In the lectures, we discussed about the Latent Factor Model (LFM) as a model-based technique for approximating the user-interaction matrix, and therefore learning how to make predictions on unknown ratings. Considering the regularized optimization problem of LFM (without bias):
Explain, in a few sentences:
(a) What is this optimization problem of about? [3 marks]
(b) How can Stochastic Gradient Descent help solve this problem? [3 marks]
(c) What is the advantage of a model-based technique such as LFM as opposed to memory- based techniques such as user-based or item-based collaborative filtering? [2 marks]
4.3 Context-aware Recommendations [7 marks]
Suppose you are asked to build a context-aware system to recommend events. Users {u1; u2; u3; u4} attend events from {e1; e2; e3} in groups. Events are held in one of the two stadiums s1 and s2. After attending, users assign ratings to events. The following table shows the transactions:
(a) Define an encoding for groups, users, events and stadiums, and construct the input feature vectors for the factorization machine using the event transactions in the above table. [4 marks]
(b) How can the information in these feature vectors along with the information about ratings be used for prediction of future ratings? Explain your answer. [3 marks]