A small break from thesis related posts đź™‚

Finally I found time to describe the project we (me and Zygimantas) were working on during the last semester. And here is some motivation for it:

There is an increasing interest in distributed machine learning algorithms. A gossip learningÂ algorithm was proposed that works on a random graph with fully distributed data. The goal ofÂ our research is to analyse the behaviour of this algorithm on clustered graphs. ExperimentsÂ show that this algorithm needs to be modified in order for it to work on clustered graphs. AÂ triangulation technique was introduced. It modifies the original peer sampling algorithm and isÂ used to limit model exchange between different clusters. Results show that with such algorithmÂ it is possible to find models of local objective functions.

In other words, let’s imagine a social network where people don’t want to share their private information, but they agree to locally fit their information to some kind of model generation function and then share only parameters of obtained model. However, a model parameters from only one person is not enough to make any conclusions about the network. So why not to just randomly exchange these model between friends and merge them locally. Here is where our algorithm appear with its awesome model merging. As a result, as peers are likely to exchange their models with their friends – resulting model might characterise some clusters. And Wooalia!!! If we have models for some clusters – we can make various assumptions about them. For example, you are living in Ukraine and want to move to Sweden. You are searching for a job and have no idea on what approximately you can expect as a salary. With our approach, you can put information about you (as an input) and our merged resulting function will give you an answer for Stockholm cluster đź™‚

Obviously, all above is very simplified version of what we’ve done.Â Now a bit more serious explanation:

Peer-to-peer (P2P) is a system model in which every participant (peer) is equal. Peers areÂ connected to each other in such a way that they form a graph. Moreover, P2P communication andÂ peers themselves are unreliable, i.e. peers may fail, and messages may get delayed, may get lost and

may not be delivered at any time. Systems designed for this environment are usually robust andÂ scalable, since no central servers are needed. Adding more computation resources to such systemÂ is the same as adding more peers. These systems usually consist of a large number of peers thatÂ communicate by passing messages to each other.

Furthermore, such P2P systems can offer security to some extent. They could be used to protectÂ sensitive data such as personal data, preferences, ratings, history, etc. by not disclosing it to otherÂ participants. For example, in P2P the data could be completely distributed, so that each peerÂ knows only about his data. In such case, an algorithm could be run locally and only a result of anÂ algorithm could be shared among peers. This may ensure that there is no way for peers to learnÂ about the data kept in other peers.

This security characteristic of P2P networks can be used to build machine learning algorithmsÂ on fully distributed data. Mark Jelasity et al. in their work [1] present such algorithm that usesÂ gossiping for sharing predictive models with neighbour peers. We can assume that in this algorithmÂ a random walk is performed in the P2P network. During this random walk, ensemble learning isÂ performed, that is, model built during the random walk is merged with the local model storedÂ at each peer. After merging two models, a merged model is then updated with the local dataÂ (which is stored at each peer) and then used in the next step of a random walk. Mark Jelasity et al.Â conclude that in P2P networks that form a random graph such algorithm converges. Moreover,Â they state that this algorithm is more effective than the one that gathers the data before buildingÂ the prediction model. It is so because peers exchange only models that may be considerably smallerÂ than the data.

Although, Mark Jelasity et al. proved that in random graphs this gossip learning algorithmÂ converges, it is still unclear if such convergence may be achieved in clustered graphs. Moreover, theÂ behaviour of such convergence may provide these results:

- every peer after a number of iterations will have a model that represents the data on a localÂ cluster;
- after more iterations every peer will have a model that represents the data on every peer.

Summary:

- Our gossip learning algorithm uses a framework described in [1] with Adaline gradient descent learning algorithm;
- We analysed gossip learning algorithmâ€™s convergence properties on random and clustered graphs;
- We designed and implemented a graph generating tool that generates random and clustered graphs.

[1]Â R. Ormandi, I. Heged-Hus, and M. Jelasity. Gossip learning with linear models onÂ fully distributed data. Concurrency and Computation: Practice and Experience, 2012.