Multi-instance learning belongs to one of re- their work significantly by deciding about whole clusters cently fast developing areas of machine learning. It is a su- of servers instead of each one individually. pervised learning method and this paper reports research A key prerequisite for the application of multi-instance into its unsupervised counterpart, multi-instance cluster-learning to clustering is that loss functions for clustering, ing. Whereas traditional clustering clusters points, multio-riginally proposed for points, are adapted for bags. In this instance clustering clusters bags, i.e. multisets of points orpaper, such an adaptation is outlined for three sophisticated of other kinds of objects. The paper focuses on the problem loss functions: contrastive predictive coding, triplet loss of loss functions for clustering. Three sophisticated lossand magnet loss. functions used for clustering of points, contrastive predic- Of the three proposed methods, triplet loss and magnet tive coding, triplet loss and magnet loss, are elaborated forloss utilize some labels as part of the training process and multi-instance clustering. Finally, they are compared on 18so are not truly unsupervised. As such, the authors expect benchmark datasets, as well as on a real-world dataset. them to outperform the method based on contrastive predictive coding, which on the other hand is the most promising and innovative approach from the theoretical point of 1 Introduction view. In the next section, basic properties of multi-instance Multi-instance learning (MIL) belongs to recently fast de-learning and clustering are briefly introduced. The adaptaveloping areas of machine learning. Though it is a super- tion of the three considered loss functions is explained in vised learning method, this paper addresses its application Section 3. A comprehensive comparison of them is then to unsupervised learning - clustering. Whereas traditionalpresented in Section 4. clustering is one of points, multi-instance clustering clusters multisets of points, also known as bags. Such a grouping of the points into bags is considered a property of the 2 Multi-instance Learning and Clustering problem at hand and therefore sourced from the input data. While there have been some previous attempts at multi- Multi-instance learning (MIL) was first described by [7]. instance clustering, they use pairwise relations between allIn its original form, it was developed and used fsourpoints in all bags, quickly becoming unwieldy and compu- pervised learning. Some prior art also exists fournsutationally infeasible. Our work uses multi-instance learnp-ervised learning, such as [5, 31], however, it uses pairing as a general toolkit for learning representations of bagswise instance distances as a basis for clustering, which and then clusters the bags using those representations. This doesn't properly utilize the inherent structure of the data builds on previous works by the authors and enables clus-and quickly becomes computationally infeasible. tering of arbitrary data-structures by expressing them as The MIL paradigm is a type of representation learning hierarchies of multi-instance problems and then using the on data which has some internal structure. Therefore, it internal structure to better solve the problems at hand. views a sample as abag (i.e. a multiset) of an arbitrary Multi-instance clustering is evaluated in Section 4 in number of objects. The basic elements of MIL are samthe application domain of computer and network security. ples from a spaceX and their corresponding labels from a While this is only one of many possible applications of space Y (a space of classes). Compared to usual supervised MIL due to its general expressive power for structured data,learning, MIL replaces individual instances with bags of it is the domain of choice for the authors. Here, MIL is instances from the spaceX such that every instance inX used to represent user activity as a bag of network con- belongs to at least one bag from the bag-spacBe. nections for each user in a fixed time window. For clus- [7] provides an example of a multi-instance problem tering, this enables detection of compromised users based where each bag represents a key chain with some keys (inon their complex behaviours. Clustering opens a new win- stances). To solve the problem of finding which key opens dow of opportunity here by e.g. grouping servers with sim- a particular lock, a “proxy” MIL problem is presented - deilar behaviour together, allowing a human analyst to boosttermining which key chain opens that particular lock. This
Copyright ©2020 for this paper by its authors. Use permitted under line of thinking leads to the pivotal definition of the label
Creative Commons License Attribution 4.0 International (CC BY 4.0). of a bag as being positive if the bag contains at least one
positive instance. In later works such as [
Let for the spaceX exist a measurable space(X ; A), then be broken down even further. In the end, the model
where A is a -algebra onX . Let PX denote the set of consists of 5 nested MIL problems.
all probability measures o(Xn ; A). A bag B is viewed as A benefit of MIL is also its easy use for explainability
a random sample with replacement of a random variable and interpretability. The authors of [
B = fxijxi pB; i 2 f1; : : : ; mgg wherem 2 N: (1)
2.2 Embedded-space paradigm for solving Clustering is a prime example of a problem typically
assomulti-instance problems ciated with unsupervised learning. The problem at hand,
however, is not one of clustering ordinary number vectors
While it is possible to use several approaches to solv- in a linear space. Instead, a clustering of objects
repreing multi-instance problems, in this work, the embedded- sented by bags is explored, as that is the problem solved for
space paradigm was used. For an overview of the other datasets introduced later in Section 4. While [
In the embedded space paradigm, labels are only defined bags and [17] present a clustering using maximum mean
on the level of bags. In order for these bag labels to bediscrepancy, a diferent approach to clustering of bags is
learned, an embedding function of the form: B ! X used in this work. Among the main reasons for this choice
must be defined, where X is a latent space, which may or is the prohibitively high computational complexity of the
may not be identical toX . Using this function, each bag previously mentioned approaches on large datasets and the
can be represented by an object (B) 2 X , which makes it possibility of utilizing the representations previously
intropossible to use any of-the-shelf supervised learning algo- duced in [
Specifically to the experiments presented in Section 4, The embedding function can be actually written as
[
L ( ; ) = LC (f (B; )jB 2 Bg) : (2) If the cluster-losLsC is chosen correctly, minimizinLg high-quality embeddings would need only a small amount over the learning period will yield a latent spXacine which of seed data points to reach relatively high accuracy. For the bags are already naturally clustered according to thethis measure, the kNN algorithm was run thrice and the redesign of the cluster-loss function. Applying any of-the- sults averaged to compensate for high dependence on the shelf clustering algorithm Xonwill then give good results. particular seed points chosen.
How to choose the cluster-loss functioLnC is the focus of Section 3.
2.4 Clustering evaluation metrics In Section 2.4, a method for learning a representatiownas described. In order to learn the parameters of the represenIn our research, several clustering evaluation metrics havetation, a clustering-loss function is required in the form been used. The primary metrics are based on the Silhouette coeficient, the secondary ones on the kNN algorithm. LC : PM X ! R: The metrics are somewhat diferent to the ones traditionally used in evaluating clustering methods as all the datasets In this section, three ways of constructing such a clusteringused in this work are originally classification datasets and loss function are explored. First, an unsupervised method therefore have classes available. Each class can then be constructing a clustering loss-function is presented, folviewed as a cluster target and the learned clustering evalu-lowed by two supervised methods. ated against these targets.
The first two metrics measure thehomogeneity of clus- 3.1 Contrastive Predictive Coding
ters (that is the property of instances of one cluster being
close to one another) and thesireparation (that is the prop- Contrastive predictive codingC(PC) is a technique first
erty of instances of diferent clusters being far apart), see introduced by [
the InfoNCE loss is defined as with jCij being the number of instances in the baCgi.
To measure the separation of clusters, the average distance between cluster centres was taken: sep (C1; : : : ; Cn) =
2 n (n 1) i;j2n^ i<j X k (Ci)
(Cj)k :
2 EX 4logfk (xt+k; ct) log X fk (xj; ct)5 : xj2X
3 Optimizing this value will resultfink modelling the density ratio fk (xt+k; ct) / p (xt+kjct) p (xt+k) sep (C1; : : : ; Cn) and therefore in maximizing the mutual information besilhouette(C1; : : : ; Cn) = nonhomo(C1; : : : ; Cn) : (3) tween xt+k and ct.
The actual application to MIL is based on the following
For the secondary metrics, the kNN algorithm in the rep- idea. If a bag is split into two parts, it is reasonable to exresentation space is used and its accuracy measured. While pect that the representations of these two parts would be the primary metric measures the quality of the clustering close to one another. On the other hand, if a random bag in general, this metric focuses on the utility of the learned were to be drawn from the data (assaimple random sample representation to a specific and useful task - classification. with replacement), it is reasonable to expect it to be relaThe training data of the kNN classifier is chosen randomly tively far from any actual bag present in the data. These asand is in this work referred to saesed data to avoid confu- sumptions can be proven correct by using the probabilistic sion with the data used to train the embedding. The value formalism for MIL (see Subsection 2.1). Given that each of k = 3 was chosen by experimental evaluation. This bag Bk is viewed as a set of realizations of a probability gives an insight into the robustness of the clustering, as distributionPk 2 PX , it follows that the two parts of the
K logX j=1
B(1) k
B0 j
:
bag, B(1) and Bk(2), are sets of realizations from the same Euclidean distance is used. However, ideally, the metric
k
distributionPk and therefore should be statistically indis- should adapt to the problem at hand. [
1 n n wherec > 0 is a hyper-parameter of this method.
LCPC = n1 Xi=1 @BBlog(Dii) logXj=1 DijACC ; (5) moTdoifieaddatoptltehveeroargigeitnhaelbmagegthinogd,otfhtehededfinaittai.onTshenemeadtrtoixybe j6=i is defined in the same way, only with labels on the level of wheren is the number of bags. bags. The value ij = 1 if the bag Bj is a target neigh
Out of the three methods presented in this section, the bour for the bagBi. Then, using the matrixD defined in approach based on contrastive predictive coding seems the equation 4 directly instead of the linear transformation, the most promising, as it is the only unsupervised method and loss function can be expressed as could therefore be used in a broader class of applications.
This, however, also has its drawbacks – unsupervised methods are generally harder to learn correctly. For that reasonL,triplet= X ijDij+ ij the two supervised methods were selected as a safer option.
where c > 0 is again a hyper-parameter of the method.
The performance of thek-nearest neighbour algorithm de- Although [
B(1)
i where the valueK 2 N is a hyper-parameter of this method. The first term of the loss function depicts the notion that the representations of the two parts of the bag distances as should be close to one another and corresponds to the first term of InfoNCE, which maximizes the prediction of a D (xi; xj) = kL (xi xj)k2 : matching future sample from the current context. The sec- A helper matrixy is used such that ond term depicts the notion that a random bag should be far from all the bag1sand corresponds to the second term (0 for yi 6= yj of InfoNCE, which minimizes the prediction of a random yij = 1 for yi = yj : sample from the current context. Choosing to only use the ifrst part of the bag in the second term has no efect as the In addition to this, for each inpuxti, k target neighbours two parts are chosen randomly. are defined that are supposed to be close toxi. Euclidean
This method can be further modified to make it less com- distance may be used to find the target neighbours. A maputationally complex. In order not to have to draw a lot oftrix is used to indicate target neighbours whereij = 1 random bags, it can be reasonably expected that, on aver- if xj is a target neighbour oxfi and 0 else. age, the representations of two parts of two mismatched The cost function features two competing terms. The bags Bk(11) andBk(22) should be far apart. A matrDix is con- ifrst term depicts the notion that an input should be close structed as to its target neighbours. The second term depicts the no2 tion that inputs of a diferent class should be far from one Dij = : (4) another. The loss is of the form
B(2) j
diagonal ofD, whereas the distances of mismatched halves are in the rest of the matrix. Under this assumption the final loss for the CPC method is n X i;j=1 ij kL (xi
n xj)k2 + c X i;j;l=1 ij (1
yil) max 0; 1 + kL (xi xj)k2 kL (xi
xl)k2 ;
L : Rd ! Rd: +c X ijl ij (1 yil) max (0; 1 + Dij
Dil) ; (6)
The magnet loss is then defined as tlMroiaspgslnefetutlnlocostsisos, nifirsseatsnsineenntrhtoiaadnlucleycmedgeonbetyso[fo2tv6he]er.parWlelvhieotrrueispalslyetthdseesotcfrriapibldeedattaLmagnet = n1 Xi=n1 max 0; 1 + logexp 2M12iNi !(7); point, its target neighbour and a point from a diferent class where 2 R is a hyper-parameter of the method. Since and optimizes their distances, magnet loss maintains an the method standardizes both of the terms of the innermost explicit model of the distributions of diferent classes in fraction by 2, is the desired cluster separation gap exthe representation space. To capture the distributions, the pressed in the units of the variance. model uses simple clustering models for each class. Dif- The magnet loss is taken almost verbatim from the origferently to triplet loss, for which the target neighbourhoodinal article. The only change needed is a diferent way to is set a priori and is based on similarity in the original in- obtain the representation space by taking put space, magnet loss uses similarity in the space of representations and updates it periodically. Magnet loss also ri = (Bi) : pursues local separation instead of global – representations of diferent classes should be separated, but can be inter- In this usage, yi is the class label assigned to the baBgi leaved. (making magnet loss a supervised method) annd is the
Let f(xi; yi)gin=1 be a training dataset wherexi 2 Rd number of bags in the dataset. and yi are one ofC discrete class labels. A general param- Due to the choice of the hyper-parameteKr being noneterized mapf ( ; ) embeds the inputs into a representa- obvious for most problems, alternative clustering methtion space: ods that would not need hyper-parameter tuning were exri = f (xi; ) : plored. One such methods,elf-tuning spectral clustering
[
I1c;:::;IKc k=1 r2Ikc jIkcj s2Ikc in order for the method to work correctly. This problem is
The centre of each cluster is denotedck: partially solved by the introduction of self-tuning spectral
clustering [
X r: Ni = kri
ik2 :
sentation falls is denoted as The three loss functions presented in Section 3 were experimentally evaluated on 18 publicly available datasets and i = argcminkri ckk on a corporate dataset from the domain of computer secuk rity. The 2 metrics presented in Section 2.4 were used, i.e. and the squared distance of its representation from the cen- the Silhouette coeficient and the accuracy of a kNN clastre of the cluster is denoted as sifier built on the embedding. Both of these metrics were tracked over the learning period to also evaluate how the models are learning in addition to their final performance.
The variance of the distance of the representations from 4.1 Datasets their respective centres can then be calculated as
2 = 1 Xn Ni: datasets, listed in Table 1. All the datasets as used were n 1 i=1 alsTohemmadoedpelusblwi2ec.re also evaluated on a proprietary dataset Forri, the dissimilarity to all the inputs of diferent classes provided by Cisco Cognitive Intelligence, consisting of is calculated as records of network connections from clients (e.g. user computers or mobile devices) to some on-line services.
K
Mi = X X exp
c6=yi k=1
Source Datasets of a bag. This is a natural embedding of a bag as its
expected value. This model is referred to as tmhean model
[4] BrownCreeper, WinterWren in the rest of this work. A classification model has been
[1] Elephant, Fox, Tiger introduced as a target to beat. This model was realised by
[7] Musk1, Musk2 a MIL neural network identical to the previously described
[
Some of the three proposed clustering-losses have some The dataset represents HTTP trafic of more than 100 com- hyper-parameters which need to be tuned. A range of valpanies. Two datasets were collected, each spanning 1 day ues was tried for each hyper-parameter in order to select of trafic. The training data was trafic from 2019-11-18, the best configuration for each on each of the datasets. while the data used for testing was collected the follow- For Ltriple,t the values c 2 f0:01; 0:1; 1; 10; 100g have ing day, 2019-11-19. For each connection, a proprietary been tested. ForLmagnet, the valuesK 2 f2; 3; 8; 16g, classification system based on [14] provided labels, clas- 2 f0; 0:1; 0:5g and the cluster index update frequency sifying the connections either as legitimate or malicious in f5; 10; 25; 70g have been tested. (connected to malware activity). The data was sampled to include 90 % of negative bags and 10 % of positive bags. 4.3 Comparison of Results For each connection, 20 connection features were used, as well as a MIL model of the server URL, which is visualized Table 2 lists the accuracy of a kNN classifier build on the in Figure 1. embedding for all of the methods and all of the datasets.
Figure 2 shows the value of the Silhouette coeficient and the accuracy on 3 selected datasets. As can be seen, CPC 4.2 Experimental Design is the worst performing of the methods overall, and, more significantly, shows no clear improvement over the learnThe models for evaluation were implemented in the Julia ing periods for both the Silhouette coeficient and the kNN programming language [3] using the Flux.jl framework forclassifier accuracy. Between triplet loss and magnet loss, machine learning [13] and the Mill.jl framework for multi-magnet loss is somewhat better in the classification accuinstance learnin3g. racy, whereas triplet loss is somewhat better in the Silhou
The particular architecture of the models was chosen ette coeficient, indicating better separation of individual
based upon previous experience with using neural net- clusters. Of note is also the difering behaviour for
varworks in multi-instance setting [
For each of the datasets, 80 % of bags were randomly than CPC at a 5 % level of significance by the post-hoc
chosen as the training data, with the rest being testing data. Nemenyi pairwise test [
jected at the 5 % significance level by this test. This further
In order to provide some baseline against which the supports the difering results between these two methods as models could be compared (as there is no prior art formentioned in the previous subsection. this problem), two other models were introduced. A non-machine-learning model was introduced as a baseline, which all models should surpass. This model implements4.5 HTTP dataset the embedding as an element-wise mean of all instances Table 3 compares the three methods on the proprietary 3https://github.com/pevnak/Mill.jl dataset from Cisco Cognitive Intelligence. Here, magnet designed token features learned features of URL parts learned features of an URL learned features of a SLD evil com path ifle key=val get=exploit.js
instance clustering was investigated. Three methods for clustering of bags were introduced, of which one is unsupervised (CPC) and two are supervised (Triplet loss and Magnet loss). For each of the methods, the prior art it builds on was presented, along with its modification for the purposes of multi-instance clustering. All three methods were theoretically and experimentally evaluated and compared. The experiments were conducted first on publicly available datasets in a reproducible fashion. Following that, a corporate dataset of network security data was used as it is the intended application domain for this work.
Comparing the methods on the publicly available datasets shows the method based on contrastive predictive coding to perform the worst, with the other having no statistically significant diference between them. Similar results were also obtained on the corporate dataset of HTTP trafic, albeit none of the results were as good as anticipated. The method based on contrastive predictive coding performed Table 2: The accuracy of the final models for the publicly poorly on both the publicly available datasets and the coravailable datasets. porate one, however, the comparison might not be fair as the CPC method is unsupervised, whereas the other two Variant CPC Triplet loss Magnet loss can utilize labels on the training data, giving them a strong advantage. 2 classes 0.920 0.910 0.930 The initial expectation of CPC being outperformed 20 classes 0.893 0.868 0.904 proved to be true. Even as such, the result is interesting and has a value of its own in providing a baseline and a Table 3: The accuracy of the final models for the corporate comparison for these and future methods. datasets.
Acknowledgement loss is the best of the three methods, however, only by a The research reported in this paper has been supported by small margin over the other 2 methods. Since the datasets the Czech Science Foundation (GAČR) grant 18-21409S consisted of 90 % of negative samples however, none of the and partially supported by the GAČR grant 18-18080S. results is particularly remarkable and some further tuning would be needed if any of the methods were to be used in real environment.
50 Learning step 75
100 (a) Musk2, Silhouette coef.
50
Learning step (b) Musk2, accuracy 50 Learning step 75 100
50 Learning step (c) UCSBBreastCancer, Silhouette coef. (d) UCSBBreastCancer, accuracy
CPC Triplet
Magnet Classification model 75
100 CPC Triplet
Magnet Classification model 75 100 1:5 io1:0 t a R 0:5 0:0 2:0 1:5 o i t aR1:0 0:5 0:0 100 75 o i t a R 50 25 0 0 0 [3] J. Bezanson et al. “Julia: A Fresh Approach to Numerical Computing”. In:SIAM Review 59.1 (Jan. 2017), pp. 65–98. issn: 0036-1445. doi: 10.1137/ 141000671. url: https : / / epubs . siam . org / doi / 10 . 1137 / 141000671 (visited on 09/01/2018). [13] Mike Innes. “Flux: Elegant machine learning with
Julia”. In:Journal of Open Source Software (2018). doi: 10.21105/joss.00602. [4] Forrest Briggs, Xiaoli Fern, and Raviv Raich. [14] Ján Jusko. “Graph-based Detection of Malicious “Rank-loss support instance machines for MIML Network Communities”. PhD thesis. Prague: Czech instance annotation”. In:Proceedings of the ACM Technical University in Prague, 2017u.rl: https: SIGKDD International Conference on Knowledge //dspace.cvut.cz/handle/10467/73702 (visDiscovery and Data Mining. Aug. 2012. doi: 10 . ited on 04/02/2019). 1145/2339530.2339616.
[15] Melih Kandemir, Chong Zhang, and Fred A. [5] Ying Chen and Ou Wu. “Contextual Hausdorf Hamprecht. “Empowering Multiple Instance dissimilarity for multi-instance clustering”. In: Histopathology Cancer Diagnosis by Cell Graphs”. Fuzzy Systems and Knowledge Discovery (FSKD). In: Medical Image Computing and ComputerSichuan, China: IEEE Computer Society Press, May Assisted Intervention – MICCAI 2014. Ed. by 2012, pp. 870–873. isbn: 978-1-4673-0024-7. doi: Polina Golland et al. Lecture Notes in Computer 10.1109/FSKD.2012.6233889. url: https:// Science. Cham: Springer International Publishing, ieeexplore.ieee.org/abstract/document/ 2014, pp. 228–235. isbn: 978-3-319-10470-6. doi: 6233889/ (visited on 05/14/2018). 10.1007/978-3-319-10470-6_29. [6] Marek Dědič. “Optimalization of distances for [16] Diederik P. Kingma and Jimmy Ba. “Adam: multi-instance clustering”. MA thesis. Prague: A Method for Stochastic Optimization”. In: Czech Technical University in Prague, Jan. 2020. arXiv:1412.6980 [cs] (Jan. 2017). arXiv: [7] Thomas G. Dietterich, Richard H. Lathrop, and 1412.6980. url: http : / / arxiv . org / abs / Tomás Lozano-Pérez. “Solving the multiple in- 1412.6980 (visited on 06/25/2020). stance problem with axis-parallel rectangles”. In:[17] J. Kohout and T. Pevný. “Network Trafic FinArtificial Intelligence 89.1 (Jan. 1997), pp. 31–71. gerprinting Based on Approximated Kernel Twoissn: 0004-3702. doi: 10.1016/S0004-3702(96) Sample Test”. In:IEEE Transactions on Information 00034-3. (Visited on 05/31/2017). Forensics and Security 13.3 (Mar. 2018), pp. 788– 801. issn: 1556-6013. doi: 10.1109/TIFS.2017. 2768018. [18] J. MacQueen. “Some methods for classification and analysis of multivariate observations”. IPnr:oceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability. Vol. 1. Berkeley, California: University of California Press, 1967, pp. 281–297. [8] P. Elias. “Predictive coding–I”. InI:RE Transactions on Information Theory 1.1 (Mar. 1955), pp. 16– 24. issn: 2168-2712. doi: 10 . 1109 / TIT . 1955 .
1055126. [9] Brian S. Everitt, Sabine Landau, and Morven Leese.
Cluster Analysis. 4th ed. Taylor & Francis, 2001.
isbn: 978-0-340-76119-9. [10] Milton Friedman. “The Use of Ranks to Avoid the
Assumption of Normality Implicit in the Analysis of [19] Krikamol Muandet et al. “Learning from DistriVariance”. In:Journal of the American Statistical butions via Support Measure Machines”. InA:dAssociation 32.200 (Dec. 1937). Publisher: Taylor vances in neural information processing systems. & Francis, pp. 675–701.issn: 0162-1459. doi: 10. 2012, pp. 10–18. url: http://papers.nips.cc/ 1080/01621459.1937.10503522. url: https: paper/4825-learning-from-distributions