diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/convex_optimization.py | 73 | ||||
| -rw-r--r-- | src/make_plots.py | 77 |
2 files changed, 143 insertions, 7 deletions
diff --git a/src/convex_optimization.py b/src/convex_optimization.py index 000143f..fbfeb29 100644 --- a/src/convex_optimization.py +++ b/src/convex_optimization.py @@ -4,7 +4,7 @@ from theano import tensor, function import numpy as np import timeout import cvxopt - +import scipy @timeout.timeout(20) def sparse_recovery(lbda, n_cascades): @@ -124,28 +124,89 @@ def diff_and_opt(M_val, w_val, f_x, f_xz): return 1 - np.exp(theta), theta +def restrictedEigenvalue(M_val, w_val, theta_val, gramMatrix=False): + """ + returns the smallest restricted eigenvalue of the matrix on the set S + gramMatrix (bool) : If true, use the gram matrix instead of the Hessian + theta_val : true vector of parameters + """ + m, n = M_val.shape + + if gramMatrix: + H = 1./m * np.dot(M_val.T,M_val) + else: + #compute the Hessian + #theta = tensor.row().T + #theta_ = theta.flatten() + + #M = tensor.matrix(name='M', dtype=theano.config.floatX) + #w = tensor.vector(name='w', dtype=theano.config.floatX) + + #y = - 1./n*( (w).dot(tensor.log(1-tensor.exp(M.dot(theta_)))) + + #(1-w).dot(tensor.dot(M, theta_))) + + #f = theano.function([theta, M, w], [theano.gradient.hessian(y, + #theta_)], allow_input_downcast=True) + + #print(theta_val) + #H = f(np.atleast_2d(theta_val).T, M_val.astype('float64'), w_val) + + #print(H) + + #evals_small, evecs_small = scipy.sparse.linalg.eigsh(H.astype('float64'), 1, + #which="LM") + #print(evals_small) + + theta = tensor.vector() + + M = tensor.matrix(name='M', dtype=theano.config.floatX) + w = tensor.vector(name='w', dtype=theano.config.floatX) + + y = - 1./n*((w).dot(tensor.log(1-tensor.exp(M.dot(theta)))) + + (1-w).dot(tensor.dot(M, theta))) + + f = theano.function([theta, M, w], [theano.gradient.hessian(y, + theta)], allow_input_downcast=True) + + H = f(theta_val, M_val.astype('float32'), w_val) + + print(H) + + evals_small, evecs_small = scipy.sparse.linalg.eigsh(H, 1, + which="LM") + print(evals_small) + + def test(): """ unit test """ lbda = .0001 - G = cascade_creation.InfluenceGraph(max_proba=.9) + G = cascade_creation.InfluenceGraph(max_proba=.9, min_proba=.2) G.erdos_init(n=20, p = .3) A = cascade_creation.generate_cascades(G, .1, 500) - M_val, w_val = cascade_creation.icc_matrixvector_for_node(A, 2) - print(len(M_val)) + M_val, w_val = cascade_creation.icc_matrixvector_for_node(A, 0) + print(M_val.shape) + print(w_val.shape) #Type lasso if 0: - f_x, f_xz = type_lasso(lbda) + f_x, f_xz = type_lasso(lbda, 500) p_vec, _ = diff_and_opt(M_val, w_val, f_x, f_xz) print(G.mat[2]) #Sparse recovery - if 1: + if 0: f_x, f_xz = sparse_recovery(lbda, 500) p_vec, _ = diff_and_opt(M_val, w_val, f_x, f_xz) print(G.mat[2]) + #Restricted Eigenvalue + if 2: + node = 1 + parents = np.nonzero(G.mat[:, node])[0] + theta_val = G.logmat[:,node] + restrictedEigenvalue(M_val, w_val, theta_val) + if __name__=="__main__": test() diff --git a/src/make_plots.py b/src/make_plots.py index 8970cdf..4cbef4a 100644 --- a/src/make_plots.py +++ b/src/make_plots.py @@ -3,9 +3,72 @@ import numpy as np import cascade_creation import convex_optimization import algorithms +import timeout import rip_condition +def theoreticalGuarantees(graph_name, n_cascades, min_proba, max_proba, + sparse_edges, p_init, passed_function, *args, **kwargs): + + #creating original graph + G = cascade_creation.InfluenceGraph(max_proba = max_proba, + min_proba = min_proba, + sparse_edges = sparse_edges + ) + G.import_from_file(graph_name) + + #creating dummy graph + G_hat = cascade_creation.InfluenceGraph(max_proba=None) + G_hat.add_nodes_from(G.nodes()) + + #generating cascades + A = cascade_creation.generate_cascades(G, p_init=p_init, + n_cascades = n_cascades) + + #Value of restrictedEigenvalueList + restrictedEigenvalueList = [] + + for node in G.nodes(): + print(node) + try: + M, _ = cascade_creation.icc_matrixvector_for_node(A, node) + M_val = np.delete(M, node, axis=1) + parents = np.nonzero(G.mat[:,node])[0] + restrictedEigenvalueList.append( + convex_optimization.restrictedEigenvalue(M, S=parents, + gramMatrix=True, node=node)) + print(restrictedEigenvalueList[-1]) + except timeout.TimeoutError: + print("TimeoutError, skipping to next node") + + print(restrictedEigenvalueList) + alpha = 1 + theoreticalGuarantee = sum( + np.sqrt(len(parents)*np.log(G.number_of_nodes())/len(M))/( + alpha*gamma) for gamma in restrictedEigenvalueList if gamma >= + 1000) + print(theoreticalGuarantee) + + +def cascades_vs_measurements(graph_name, n_cascades, min_proba, max_proba, + sparse_edges=False, p_init=0.05): + """ + Compares the number of measurements within a cascade for different types of + graphs + """ + G = cascade_creation.InfluenceGraph(max_proba = max_proba, + min_proba = min_proba, + sparse_edges = sparse_edges + ) + G.import_from_file(graph_name) + A = cascade_creation.generate_cascades(G, p_init=p_init, + n_cascades = n_cascades) + + L = [len(cascade) for cascade in A] + print(L) + print("mean: {}\nstandard deviation: {}".format(np.mean(L), np.std(L))) + + def compare_greedy_and_lagrange_cs284r(): """ Compares the performance of the greedy algorithm on the @@ -36,7 +99,8 @@ def compute_graph(graph_name, n_cascades, lbda, passed_function, min_proba, min_proba=min_proba, sparse_edges=sparse_edges) G.import_from_file(graph_name) - A = cascade_creation.generate_cascades(G, p_init=p_init, n_cascades=n_cascades) + A = cascade_creation.generate_cascades(G, p_init=p_init, + n_cascades=n_cascades) if passed_function==algorithms.greedy_prediction: G_hat = algorithms.greedy_prediction(G, A) @@ -232,6 +296,17 @@ def plot_p_init_watts_strogatz(): if __name__=="__main__": if 1: + theoreticalGuarantees(graph_name = + "../datasets/powerlaw_200_30_point3.txt", + n_cascades=100, min_proba=.2, max_proba=.7, + p_init=.05, sparse_edges=False, + passed_function=convex_optimization.sparse_recovery, + lbda=.001) + + if 0: + cascades_vs_measurements("../datasets/watts_strogatz_p_init.txt", + n_cascades=1000, min_proba=.2, max_proba=.7) + if 0: compute_graph("../datasets/watts_strogatz_300_30_point3.txt", n_cascades=300, lbda=.013382, min_proba=.2, max_proba=.7, passed_function= |