Machine Learning/Kaggle Social Network Contest/Problem Representation - Revision history

Jared at 05:26, 22 November 2010

2010-11-22T05:26:57Z

← Older revision		Revision as of 22:26, 21 November 2010
Line 31:		Line 31:
	If both types of data are in one datafile, we'd be probably be duplicating any single-node-centric data points for every single edge row. I understand we might need to ultimately need to create such a single file, but I feel like two files will help keep it manageable as we identify and calculate feature data in the short term.		If both types of data are in one datafile, we'd be probably be duplicating any single-node-centric data points for every single edge row. I understand we might need to ultimately need to create such a single file, but I feel like two files will help keep it manageable as we identify and calculate feature data in the short term.

	UPDATE: Network Size is definitely going to be an issue. Traversing the network to calculate shortest_distance crashed and burned with memory shortfalls. Initially I thought it was manageable until I allowed my code to use the entire adjacency list. Even without outputting data for edges with no path between them, I think the data dump storage itself would also be a problem. I am going to try rerunning the shortest_distance search with a max depth limit of <strike>six</strike> <strike>three<strike> two to see if that makes it more manageable.<br/>		UPDATE: Network Size is definitely going to be an issue. Traversing the network to calculate shortest_distance crashed and burned with memory shortfalls. Initially I thought it was manageable until I allowed my code to use the entire adjacency list. Even without outputting data for edges with no path between them, I think the data dump storage itself would also be a problem. I am going to try rerunning the shortest_distance search with a max depth limit of <strike>six</strike> <strike>three</strike> two to see if that makes it more manageable.<br/>
	UPDATE 2: The BFS search approach I was taking to path finding was too slow since I kept retracing the data, so I just tried scripting a dump of all "friend-of-friends" edges. After 5.5 hours computation time I have "friend-of-friend" edge dump but it's a 6.5GB file. That said, I accidentally included duplicate edges, so hopefully after deduping it will be um smaller.		UPDATE 2: The BFS search approach I was taking to path finding was too slow since I kept retracing the data, so I just tried scripting a dump of all "friend-of-friends" edges. After 5.5 hours computation time I have "friend-of-friend" edge dump but it's a 6.5GB file. That said, I accidentally included duplicate edges, so hopefully after deduping it will be um smaller.

Jared: /* Idea A - huge CSV */

2010-11-22T05:25:28Z

Idea A - huge CSV

← Older revision		Revision as of 22:25, 21 November 2010
Line 31:		Line 31:
	If both types of data are in one datafile, we'd be probably be duplicating any single-node-centric data points for every single edge row. I understand we might need to ultimately need to create such a single file, but I feel like two files will help keep it manageable as we identify and calculate feature data in the short term.		If both types of data are in one datafile, we'd be probably be duplicating any single-node-centric data points for every single edge row. I understand we might need to ultimately need to create such a single file, but I feel like two files will help keep it manageable as we identify and calculate feature data in the short term.

	UPDATE: Network Size is definitely going to be an issue. Traversing the network to calculate shortest_distance crashed and burned with memory shortfalls. Initially I thought it was manageable until I allowed my code to use the entire adjacency list. Even without outputting data for edges with no path between them, I think the data dump storage itself would also be a problem. I am going to try rerunning the shortest_distance search with a max depth limit of <strike>six</strike> three to see if that makes it more manageable.		UPDATE: Network Size is definitely going to be an issue. Traversing the network to calculate shortest_distance crashed and burned with memory shortfalls. Initially I thought it was manageable until I allowed my code to use the entire adjacency list. Even without outputting data for edges with no path between them, I think the data dump storage itself would also be a problem. I am going to try rerunning the shortest_distance search with a max depth limit of <strike>six</strike> <strike>three<strike> two to see if that makes it more manageable.<br/>
	UPDATE 2: The BFS search approach I was taking to path finding was too slow since I kept retracing the data, so I just tried scripting a dump of all "friend-of-friends" edges. After 5.5 hours computation time I have "friend-of-friend" edge dump but it's a 6.5GB file. That said, I accidentally included duplicate edges, so hopefully after deduping it will be um smaller.		UPDATE 2: The BFS search approach I was taking to path finding was too slow since I kept retracing the data, so I just tried scripting a dump of all "friend-of-friends" edges. After 5.5 hours computation time I have "friend-of-friend" edge dump but it's a 6.5GB file. That said, I accidentally included duplicate edges, so hopefully after deduping it will be um smaller.

Jared: /* Idea A - huge CSV */

2010-11-22T05:23:20Z

Idea A - huge CSV

← Older revision		Revision as of 22:23, 21 November 2010
Line 31:		Line 31:
	If both types of data are in one datafile, we'd be probably be duplicating any single-node-centric data points for every single edge row. I understand we might need to ultimately need to create such a single file, but I feel like two files will help keep it manageable as we identify and calculate feature data in the short term.		If both types of data are in one datafile, we'd be probably be duplicating any single-node-centric data points for every single edge row. I understand we might need to ultimately need to create such a single file, but I feel like two files will help keep it manageable as we identify and calculate feature data in the short term.

	UPDATE: Network Size is definitely going to be an issue. Traversing the network to calculate shortest_distance crashed and burned with memory shortfalls. Initially I thought it was manageable until I allowed my code to use the entire adjacency list. Even without ~~outputing~~ data for edges with no path between them, I think the data dump storage itself would also be a problem. I am going to try rerunning the shortest_distance search with a max depth limit of <strike>six</strike> three to see if that makes it more manageable.		UPDATE: Network Size is definitely going to be an issue. Traversing the network to calculate shortest_distance crashed and burned with memory shortfalls. Initially I thought it was manageable until I allowed my code to use the entire adjacency list. Even without outputting data for edges with no path between them, I think the data dump storage itself would also be a problem. I am going to try rerunning the shortest_distance search with a max depth limit of <strike>six</strike> three to see if that makes it more manageable.
			UPDATE 2: The BFS search approach I was taking to path finding was too slow since I kept retracing the data, so I just tried scripting a dump of all "friend-of-friends" edges. After 5.5 hours computation time I have "friend-of-friend" edge dump but it's a 6.5GB file. That said, I accidentally included duplicate edges, so hopefully after deduping it will be um smaller.

	== Idea B - online learning ==		== Idea B - online learning ==

Jared: /* Idea A - huge CSV */

2010-11-20T21:54:24Z

Idea A - huge CSV

← Older revision		Revision as of 14:54, 20 November 2010
Line 31:		Line 31:
	If both types of data are in one datafile, we'd be probably be duplicating any single-node-centric data points for every single edge row. I understand we might need to ultimately need to create such a single file, but I feel like two files will help keep it manageable as we identify and calculate feature data in the short term.		If both types of data are in one datafile, we'd be probably be duplicating any single-node-centric data points for every single edge row. I understand we might need to ultimately need to create such a single file, but I feel like two files will help keep it manageable as we identify and calculate feature data in the short term.

	UPDATE: Network Size is definitely going to be an issue. Traversing the network to calculate shortest_distance crashed and burned with memory shortfalls. Initially I thought it was manageable until I allowed my code to use the entire adjacency list. Even without outputing data for edges with no path between them, I think the data dump storage itself would also be a problem. I am going to try rerunning the shortest_distance search with a max depth limit of 6 to see if that makes it more manageable.		UPDATE: Network Size is definitely going to be an issue. Traversing the network to calculate shortest_distance crashed and burned with memory shortfalls. Initially I thought it was manageable until I allowed my code to use the entire adjacency list. Even without outputing data for edges with no path between them, I think the data dump storage itself would also be a problem. I am going to try rerunning the shortest_distance search with a max depth limit of <strike>six</strike> three to see if that makes it more manageable.

	== Idea B - online learning ==		== Idea B - online learning ==

Jared: /* Idea A - huge CSV */

2010-11-20T20:34:46Z

Idea A - huge CSV

← Older revision		Revision as of 13:34, 20 November 2010
Line 31:		Line 31:
	If both types of data are in one datafile, we'd be probably be duplicating any single-node-centric data points for every single edge row. I understand we might need to ultimately need to create such a single file, but I feel like two files will help keep it manageable as we identify and calculate feature data in the short term.		If both types of data are in one datafile, we'd be probably be duplicating any single-node-centric data points for every single edge row. I understand we might need to ultimately need to create such a single file, but I feel like two files will help keep it manageable as we identify and calculate feature data in the short term.

	UPDATE: ~~Jared~~ is ~~working on~~ an ~~initial edge_features~~.~~csv with just 3 columns (node_i, node_j,~~ shortest_distance) and ~~is already hitting some~~ memory ~~and storage limits~~. ~~Traversing the graph isn't the hard part~~ it's the ~~shear number of total possible edges to output data for (as noted above)~~. ~~Rerunning now after some code improvements...crossing fingers. Might be ok on memory now but I'll possibly not have enough disk space on this machine~~ for ~~even shortest~~ path ~~feature~~. ~~We might need~~ to ~~set up Hadoop or something~~ if ~~we wanna take this approach! ;)~~		UPDATE: Network Size is definitely going to be an issue. Traversing the network to calculate shortest_distance crashed and burned with memory shortfalls. Initially I thought it was manageable until I allowed my code to use the entire adjacency list. Even without outputing data for edges with no path between them, I think the data dump storage itself would also be a problem. I am going to try rerunning the shortest_distance search with a max depth limit of 6 to see if that makes it more manageable.

	== Idea B - online learning ==		== Idea B - online learning ==

Jared: /* Idea A - huge CSV */

2010-11-20T10:23:24Z

Idea A - huge CSV

← Older revision		Revision as of 03:23, 20 November 2010
Line 30:		Line 30:
	* edge_features.csv: node_i, node_j, shortest_distance, density, etc, etc		* edge_features.csv: node_i, node_j, shortest_distance, density, etc, etc
	If both types of data are in one datafile, we'd be probably be duplicating any single-node-centric data points for every single edge row. I understand we might need to ultimately need to create such a single file, but I feel like two files will help keep it manageable as we identify and calculate feature data in the short term.		If both types of data are in one datafile, we'd be probably be duplicating any single-node-centric data points for every single edge row. I understand we might need to ultimately need to create such a single file, but I feel like two files will help keep it manageable as we identify and calculate feature data in the short term.

			UPDATE: Jared is working on an initial edge_features.csv with just 3 columns (node_i, node_j, shortest_distance) and is already hitting some memory and storage limits. Traversing the graph isn't the hard part it's the shear number of total possible edges to output data for (as noted above). Rerunning now after some code improvements...crossing fingers. Might be ok on memory now but I'll possibly not have enough disk space on this machine for even shortest path feature. We might need to set up Hadoop or something if we wanna take this approach! ;)

	== Idea B - online learning ==		== Idea B - online learning ==

Jjhale at 05:02, 20 November 2010

2010-11-20T05:02:08Z

← Older revision		Revision as of 22:02, 19 November 2010
Line 2:		Line 2:
	* come up with a plan of attack.		* come up with a plan of attack.

	== Idea A ==		== Idea C - two hop neighbourhood ==
			For each node of 38k sampled individuals calculate features based on the a two hop neighbourhood -ie friends of friends.
			* these neighbourhoods should make the problem a little more tractable.


			== Idea A - huge CSV==
	Construct a huge csv file containing each possible directed link and a bunch of features associated with it, then do some supervised learning on it.		Construct a huge csv file containing each possible directed link and a bunch of features associated with it, then do some supervised learning on it.

Line 26:		Line 31:
	If both types of data are in one datafile, we'd be probably be duplicating any single-node-centric data points for every single edge row. I understand we might need to ultimately need to create such a single file, but I feel like two files will help keep it manageable as we identify and calculate feature data in the short term.		If both types of data are in one datafile, we'd be probably be duplicating any single-node-centric data points for every single edge row. I understand we might need to ultimately need to create such a single file, but I feel like two files will help keep it manageable as we identify and calculate feature data in the short term.

	== Idea B ==		== Idea B - online learning ==
	We could perform some kind of online learning on the network where compute features based on a pair of nodes and then update of parameters. This would take 42 billion steps - which sounds like a lot.		We could perform some kind of online learning on the network where compute features based on a pair of nodes and then update of parameters. This would take 42 billion steps - which sounds like a lot.

	Can whoever added/proposed this please flesh this out more? Curious to explore alternative approaches for sure, even if they seem computationally difficult.		Can whoever added/proposed this please flesh this out more? Curious to explore alternative approaches for sure, even if they seem computationally difficult.

Jared at 01:53, 20 November 2010

2010-11-20T01:53:41Z

← Older revision		Revision as of 18:53, 19 November 2010
Line 25:		Line 25:
	* edge_features.csv: node_i, node_j, shortest_distance, density, etc, etc		* edge_features.csv: node_i, node_j, shortest_distance, density, etc, etc
	If both types of data are in one datafile, we'd be probably be duplicating any single-node-centric data points for every single edge row. I understand we might need to ultimately need to create such a single file, but I feel like two files will help keep it manageable as we identify and calculate feature data in the short term.		If both types of data are in one datafile, we'd be probably be duplicating any single-node-centric data points for every single edge row. I understand we might need to ultimately need to create such a single file, but I feel like two files will help keep it manageable as we identify and calculate feature data in the short term.

	~~== Idea B ==~~
	~~We could perform some kind of online learning on the network where compute features based on a pair of nodes and then update of parameters. This would take 42 billion steps - which sounds like a lot.~~

	== Idea B ==		== Idea B ==

Jared at 01:53, 20 November 2010

2010-11-20T01:53:24Z

← Older revision		Revision as of 18:53, 19 November 2010
Line 28:		Line 28:
	== Idea B ==		== Idea B ==
	We could perform some kind of online learning on the network where compute features based on a pair of nodes and then update of parameters. This would take 42 billion steps - which sounds like a lot.		We could perform some kind of online learning on the network where compute features based on a pair of nodes and then update of parameters. This would take 42 billion steps - which sounds like a lot.

			== Idea B ==
			We could perform some kind of online learning on the network where compute features based on a pair of nodes and then update of parameters. This would take 42 billion steps - which sounds like a lot.

			Can whoever added/proposed this please flesh this out more? Curious to explore alternative approaches for sure, even if they seem computationally difficult.

SpammerHellDontDelete: /* Idea A */

2010-11-20T01:49:21Z

Idea A

← Older revision		Revision as of 18:49, 19 November 2010
Line 19:		Line 19:

	This number could be culled by considering just the nodes in some neighbourhood - but I figure that would only provide us with information about nodes which are connected.		This number could be culled by considering just the nodes in some neighbourhood - but I figure that would only provide us with information about nodes which are connected.


			Suggestion on how to tame the size: Perhaps breaking into two csvs with one for data columns about nodes and another for columns about edges. For example:
			* node_features.csv: node_id, inbound_degree, outbound_degree, clustering coefficient, etc, etc.
			* edge_features.csv: node_i, node_j, shortest_distance, density, etc, etc
			If both types of data are in one datafile, we'd be probably be duplicating any single-node-centric data points for every single edge row. I understand we might need to ultimately need to create such a single file, but I feel like two files will help keep it manageable as we identify and calculate feature data in the short term.

	== Idea B ==		== Idea B ==
	We could perform some kind of online learning on the network where compute features based on a pair of nodes and then update of parameters. This would take 42 billion steps - which sounds like a lot.		We could perform some kind of online learning on the network where compute features based on a pair of nodes and then update of parameters. This would take 42 billion steps - which sounds like a lot.