September 2017 - petsc-dev - mailman3.cels.anl.gov

Re: [petsc-dev] Question about linesearch
by Munson, Todd 22 Sep '17

22 Sep '17

Hi, I am not sure that this linesearch is implemented in PETSc itself. To implement it, you would need the ability to perform projections onto your feasible region, which is what I am assuming you mean by undershoot or overshoot. Once the projections are involved, however, there are lots of potential problems to consider in the general case. Here I am assuming that x_k is feasible with respect to your feasible region. If not, then there are even more options. For the particular form of line search you have (sufficient decrease conditions) you will want the projection in two places: f(\Pi_C(x_k + \lambda d_k) < f(x_k) + \alpha grad f(x_k)^T (\Pi_C(x_k + \lambda d_k) - x_k) where \Pi_C is the projection of the argument onto the feasible region C, a convex set. The last term makes sure you measure descent against the projected direction, rather than the full direction. The projected direction may not be a descent direction, so you need a fix when \alpha grad f(x_k)^T (\Pi_C(x_k + \lambda d_k) - x_k) >= 0. I would need to dig out some papers for the appropriate fix, which if I recall correctly involves the \min operation. Unless your direction is the steepest descent direction for f(x_k), there is no guarantee that you will satisfy the sufficient decrease condition for any value of \lambda and you would need to impose a finite lower bound on \lambda and have a backup that uses the steepest descent direction. I recall an alternative line search that uses a convex combination of the steepest descent direction and d_k, but would have to find the papers on it. Second order sufficiency (e.g., the equivalent of the strong Wolfe conditions) is probably off the table for now when you have projections. As you can see, there are lots of options (even before adding monotone versus non monotone considerations); the PETSc developers would have to say which ones are relevant and whether or not the projected line searches are separate from the normal line searches. Todd. > On Sep 22, 2017, at 8:22 AM, Lulu Liu <lulu.liu(a)kaust.edu.sa> wrote: > > Hi, > > I am trying to find a lambda by the linesearch such that > f([x_{k}+\lambda d_{k}])<f(x_{k})+\alpha\lambda grad f(x_{k})^{T}d_{k} > where [x_{k}+lambda d_{k}] means the projection that cuts off the undershoot or overshoot of x_{k}+lambda d_{k}. > > How to add the above projection into the linesearch in PETSc? > > Thanks! > > This message and its contents, including attachments are intended solely for the original recipient. If you are not the intended recipient or have received this message in error, please notify me immediately and delete this message from your computer system. Any unauthorized use or distribution is prohibited. Please consider the environment before printing this email.

1 0

Re: [petsc-dev] MatTransposeMatMult
by Hong 22 Sep '17

22 Sep '17

Jed : New implementation for seqaij is in branch hzhang/opt-mattransposematmult. petsc/src/mat/examples/tests/ex209.c is a test. Please give it a try and let me know if you have any comment. I'll remove previous implementation and optimize MatTransposeMatMult() for mpiaij matrices. Hong Hong <hzhang(a)mcs.anl.gov> writes: > > > It was implemented a decade ago for small to medium matrices. > > Your matrix structure reveals the worst part of outer product. > > > > After discussing it with Barry, we decided to replace the algorithm (not > > API) using At=A^T and C=At*B for sequential implementation. > > In parallel, I'll do local MatTranspose (used for PtAP). > > I'll give you this new implementation in few days. > > Perfect, thanks! >

1 0

Question about linesearch
by Lulu Liu 22 Sep '17

22 Sep '17

Hi, I am trying to find a lambda by the linesearch such that f([x_{k}+\lambda d_{k}])<f(x_{k})+\alpha\lambda grad f(x_{k})^{T}d_{k} where [x_{k}+lambda d_{k}] means the projection that cuts off the undershoot or overshoot of x_{k}+lambda d_{k}. How to add the above projection into the linesearch in PETSc? Thanks! -- ------------------------------ This message and its contents, including attachments are intended solely for the original recipient. If you are not the intended recipient or have received this message in error, please notify me immediately and delete this message from your computer system. Any unauthorized use or distribution is prohibited. Please consider the environment before printing this email.

1 0

Re: [petsc-dev] (no subject)
by Munson, Todd 22 Sep '17

22 Sep '17

> On Sep 22, 2017, at 7:35 AM, Matthew Knepley <knepley(a)gmail.com> wrote: > > On Fri, Sep 22, 2017 at 12:06 AM, Richard Tran Mills <rtmills(a)anl.gov> wrote: > Thanks for sharing this, Barry. I haven't had time to read their paper, but it looks worth a read. > > Hong, since many machine-learning or data-mining problems can be cast as linear algebra problems (several examples involving eigenproblems come to mind), I'm guessing that there must be several people using PETSc (with SLEPc, likely) in this this area, but I don't think I've come across any published examples. What have others seen? > > http://epubs.siam.org/doi/abs/10.1137/S1052623400374379 Alas, we did not use PETSc for it. There is another semismooth version we wrote using similar concepts that is better, but alas that one also did not use PETSc. All could be written using PETsc though. (We make an assumption that the data is a dense, tall, and skinny matrix.) Mike Gertz wrote a similar version using OOQP, but I do not think it was published. I recently ran across some recent parallel clustering methods based on DBSCAN and KD-trees, but that does not seem suitable for using PETSc. There should be lots of data analysis computations that might written using PETSc as well, but I do not know of any group that writes them specifically using PETSc. As some point, we may want to think about how to hijack the data being output for some online analysis. Its unclear if we need PETSc support or if its up to the user. Todd. > Most of the machine learning and data-mining papers I read seem employ sequential algorithms or, at most, algorithms targeted at on-node parallelism only. With available data sets getting as large and easily available as they are, I'm surprised that there isn't more focus on doing things with distributed parallelism. One of my cited papers is on a distributed parallel k-means implementation I worked on some years ago: we didn't do anything especially clever with it, but today it is still one of the *only* parallel clustering publications I've seen. > > I'd love to 1) hear about what other machine-learning or data-mining applications using PETSc that others have come across and 2) hear about applications in this area where people aren't using PETSc but it looks like they should! > > Cheers, > Richard > > On Thu, Sep 21, 2017 at 12:51 PM, Zhang, Hong <hongzhang(a)anl.gov> wrote: > Great news! According to their papers, MLSVM works only in serial. I am not sure what is stopping them using PETSc in parallel. > > Btw, are there any other cases that use PETSc for machine learning? > > Hong (Mr.) > > > On Sep 21, 2017, at 1:02 PM, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > > > > > > From: Ilya Safro isafro(a)g.clemson.edu > > Date: September 17, 2017 > > Subject: MLSVM 1.0, Multilevel Support Vector Machines > > > > We are pleased to announce the release of MLSVM 1.0, a library of fast > > multilevel algorithms for training nonlinear support vector machine > > models on large-scale datasets. The library is developed as an > > extension of PETSc to support, among other applications, the analysis > > of datasets in scientific computing. > > > > Highlights: > > - The best quality/performance trade-off is achieved with algebraic > > multigrid coarsening > > - Tested on academic, industrial, and healthcare datasets > > - Generates multiple models for each training > > - Effective on imbalanced datasets > > > > Download MLSVM at https://github.com/esadr/mlsvm > > > > Corresponding paper: Sadrfaridpour, Razzaghi and Safro "Engineering > > multilevel support vector machines", 2017, > > https://arxiv.org/pdf/1707.07657.pdf > > > > > > > > -- > What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead. > -- Norbert Wiener > > http://www.caam.rice.edu/~mk51/

1 0

Re: [petsc-dev] (no subject)
by Matthew Knepley 22 Sep '17

22 Sep '17

On Thu, Sep 21, 2017 at 3:51 PM, Zhang, Hong <hongzhang(a)anl.gov> wrote: > Great news! According to their papers, MLSVM works only in serial. I am > not sure what is stopping them using PETSc in parallel. > I think its because they use FLANN (http://www.cs.ubc.ca/research/flann/) which appears to be serial. Richard, it looks like your parallel clustering could get you another few papers :) Matt > Btw, are there any other cases that use PETSc for machine learning? > > Hong (Mr.) > > > On Sep 21, 2017, at 1:02 PM, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > > > > > > From: Ilya Safro isafro(a)g.clemson.edu > > Date: September 17, 2017 > > Subject: MLSVM 1.0, Multilevel Support Vector Machines > > > > We are pleased to announce the release of MLSVM 1.0, a library of fast > > multilevel algorithms for training nonlinear support vector machine > > models on large-scale datasets. The library is developed as an > > extension of PETSc to support, among other applications, the analysis > > of datasets in scientific computing. > > > > Highlights: > > - The best quality/performance trade-off is achieved with algebraic > > multigrid coarsening > > - Tested on academic, industrial, and healthcare datasets > > - Generates multiple models for each training > > - Effective on imbalanced datasets > > > > Download MLSVM at https://github.com/esadr/mlsvm > > > > Corresponding paper: Sadrfaridpour, Razzaghi and Safro "Engineering > > multilevel support vector machines", 2017, > > https://arxiv.org/pdf/1707.07657.pdf > > > > -- What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead. -- Norbert Wiener http://www.caam.rice.edu/~mk51/

1 0

Re: [petsc-dev] (no subject)
by Matthew Knepley 22 Sep '17

22 Sep '17

On Fri, Sep 22, 2017 at 12:06 AM, Richard Tran Mills <rtmills(a)anl.gov> wrote: > Thanks for sharing this, Barry. I haven't had time to read their paper, > but it looks worth a read. > > Hong, since many machine-learning or data-mining problems can be cast as > linear algebra problems (several examples involving eigenproblems come to > mind), I'm guessing that there must be several people using PETSc (with > SLEPc, likely) in this this area, but I don't think I've come across any > published examples. What have others seen? > http://epubs.siam.org/doi/abs/10.1137/S1052623400374379 Matt > Most of the machine learning and data-mining papers I read seem employ > sequential algorithms or, at most, algorithms targeted at on-node > parallelism only. With available data sets getting as large and easily > available as they are, I'm surprised that there isn't more focus on doing > things with distributed parallelism. One of my cited papers is on a > distributed parallel k-means implementation I worked on some years ago: we > didn't do anything especially clever with it, but today it is still one of > the *only* parallel clustering publications I've seen. > > I'd love to 1) hear about what other machine-learning or data-mining > applications using PETSc that others have come across and 2) hear about > applications in this area where people aren't using PETSc but it looks like > they should! > > Cheers, > Richard > > On Thu, Sep 21, 2017 at 12:51 PM, Zhang, Hong <hongzhang(a)anl.gov> wrote: > >> Great news! According to their papers, MLSVM works only in serial. I am >> not sure what is stopping them using PETSc in parallel. >> >> Btw, are there any other cases that use PETSc for machine learning? >> >> Hong (Mr.) >> >> > On Sep 21, 2017, at 1:02 PM, Barry Smith <bsmith(a)mcs.anl.gov> wrote: >> > >> > >> > From: Ilya Safro isafro(a)g.clemson.edu >> > Date: September 17, 2017 >> > Subject: MLSVM 1.0, Multilevel Support Vector Machines >> > >> > We are pleased to announce the release of MLSVM 1.0, a library of fast >> > multilevel algorithms for training nonlinear support vector machine >> > models on large-scale datasets. The library is developed as an >> > extension of PETSc to support, among other applications, the analysis >> > of datasets in scientific computing. >> > >> > Highlights: >> > - The best quality/performance trade-off is achieved with algebraic >> > multigrid coarsening >> > - Tested on academic, industrial, and healthcare datasets >> > - Generates multiple models for each training >> > - Effective on imbalanced datasets >> > >> > Download MLSVM at https://github.com/esadr/mlsvm >> > >> > Corresponding paper: Sadrfaridpour, Razzaghi and Safro "Engineering >> > multilevel support vector machines", 2017, >> > https://arxiv.org/pdf/1707.07657.pdf >> > >> >> > -- What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead. -- Norbert Wiener http://www.caam.rice.edu/~mk51/

1 0

Re: [petsc-dev] (no subject)
by Jose E. Roman 22 Sep '17

22 Sep '17

> El 22 sept 2017, a las 6:06, Richard Tran Mills <rtmills(a)anl.gov> escribió: > > Thanks for sharing this, Barry. I haven't had time to read their paper, but it looks worth a read. > > Hong, since many machine-learning or data-mining problems can be cast as linear algebra problems (several examples involving eigenproblems come to mind), I'm guessing that there must be several people using PETSc (with SLEPc, likely) in this this area, but I don't think I've come across any published examples. What have others seen? In the SLEPc applications page there are 21 citations in the section "Information Retrieval, Machine Learning, Graph Algorithms, Complex Networks". Don't know which ones are actually related to machine learning. http://slepc.upv.es/material/appli.htm#Information Jose > > Most of the machine learning and data-mining papers I read seem employ sequential algorithms or, at most, algorithms targeted at on-node parallelism only. With available data sets getting as large and easily available as they are, I'm surprised that there isn't more focus on doing things with distributed parallelism. One of my cited papers is on a distributed parallel k-means implementation I worked on some years ago: we didn't do anything especially clever with it, but today it is still one of the *only* parallel clustering publications I've seen. > > I'd love to 1) hear about what other machine-learning or data-mining applications using PETSc that others have come across and 2) hear about applications in this area where people aren't using PETSc but it looks like they should! > > Cheers, > Richard > > On Thu, Sep 21, 2017 at 12:51 PM, Zhang, Hong <hongzhang(a)anl.gov> wrote: > Great news! According to their papers, MLSVM works only in serial. I am not sure what is stopping them using PETSc in parallel. > > Btw, are there any other cases that use PETSc for machine learning? > > Hong (Mr.) > > > On Sep 21, 2017, at 1:02 PM, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > > > > > > From: Ilya Safro isafro(a)g.clemson.edu > > Date: September 17, 2017 > > Subject: MLSVM 1.0, Multilevel Support Vector Machines > > > > We are pleased to announce the release of MLSVM 1.0, a library of fast > > multilevel algorithms for training nonlinear support vector machine > > models on large-scale datasets. The library is developed as an > > extension of PETSc to support, among other applications, the analysis > > of datasets in scientific computing. > > > > Highlights: > > - The best quality/performance trade-off is achieved with algebraic > > multigrid coarsening > > - Tested on academic, industrial, and healthcare datasets > > - Generates multiple models for each training > > - Effective on imbalanced datasets > > > > Download MLSVM at https://github.com/esadr/mlsvm > > > > Corresponding paper: Sadrfaridpour, Razzaghi and Safro "Engineering > > multilevel support vector machines", 2017, > > https://arxiv.org/pdf/1707.07657.pdf > > > >

1 0

Re: [petsc-dev] (no subject)
by Richard Tran Mills 21 Sep '17

21 Sep '17

Thanks for sharing this, Barry. I haven't had time to read their paper, but it looks worth a read. Hong, since many machine-learning or data-mining problems can be cast as linear algebra problems (several examples involving eigenproblems come to mind), I'm guessing that there must be several people using PETSc (with SLEPc, likely) in this this area, but I don't think I've come across any published examples. What have others seen? Most of the machine learning and data-mining papers I read seem employ sequential algorithms or, at most, algorithms targeted at on-node parallelism only. With available data sets getting as large and easily available as they are, I'm surprised that there isn't more focus on doing things with distributed parallelism. One of my cited papers is on a distributed parallel k-means implementation I worked on some years ago: we didn't do anything especially clever with it, but today it is still one of the *only* parallel clustering publications I've seen. I'd love to 1) hear about what other machine-learning or data-mining applications using PETSc that others have come across and 2) hear about applications in this area where people aren't using PETSc but it looks like they should! Cheers, Richard On Thu, Sep 21, 2017 at 12:51 PM, Zhang, Hong <hongzhang(a)anl.gov> wrote: > Great news! According to their papers, MLSVM works only in serial. I am > not sure what is stopping them using PETSc in parallel. > > Btw, are there any other cases that use PETSc for machine learning? > > Hong (Mr.) > > > On Sep 21, 2017, at 1:02 PM, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > > > > > > From: Ilya Safro isafro(a)g.clemson.edu > > Date: September 17, 2017 > > Subject: MLSVM 1.0, Multilevel Support Vector Machines > > > > We are pleased to announce the release of MLSVM 1.0, a library of fast > > multilevel algorithms for training nonlinear support vector machine > > models on large-scale datasets. The library is developed as an > > extension of PETSc to support, among other applications, the analysis > > of datasets in scientific computing. > > > > Highlights: > > - The best quality/performance trade-off is achieved with algebraic > > multigrid coarsening > > - Tested on academic, industrial, and healthcare datasets > > - Generates multiple models for each training > > - Effective on imbalanced datasets > > > > Download MLSVM at https://github.com/esadr/mlsvm > > > > Corresponding paper: Sadrfaridpour, Razzaghi and Safro "Engineering > > multilevel support vector machines", 2017, > > https://arxiv.org/pdf/1707.07657.pdf > > > >

1 0

Re: [petsc-dev] MatTransposeMatMult
by Jed Brown 21 Sep '17

21 Sep '17

Hong <hzhang(a)mcs.anl.gov> writes: > It was implemented a decade ago for small to medium matrices. > Your matrix structure reveals the worst part of outer product. > > After discussing it with Barry, we decided to replace the algorithm (not > API) using At=A^T and C=At*B for sequential implementation. > In parallel, I'll do local MatTranspose (used for PtAP). > I'll give you this new implementation in few days. Perfect, thanks!

1 0

Re: [petsc-dev] MatTransposeMatMult
by Hong 21 Sep '17

21 Sep '17

Jed: > Hong <hzhang(a)mcs.anl.gov> writes: > > > Jed, > > I reproduced what you observed. > > 30x time is spent on numerical C = At*B. > > We compute A^T*B using outer product C=(A^T)[:,i]*B[i,:]. > > For your large matrix A: rows=574902, cols=184446, > > outer product takes long long time to insert values to C. > > > > We may use At=A^T and C=At*B instead. > > Right. My point is that users call MatTransposeMatMult and conclude > that PETSc is super slow compared to other software. The could call > MatTranspose then MatMatMult and get fast results, but that's a sucky > and confusing interface. Is there a compelling reason to keep the outer > product implementation around? Are there any matrices for which it is > competitive? > It was implemented a decade ago for small to medium matrices. Your matrix structure reveals the worst part of outer product. After discussing it with Barry, we decided to replace the algorithm (not API) using At=A^T and C=At*B for sequential implementation. In parallel, I'll do local MatTranspose (used for PtAP). I'll give you this new implementation in few days. Hong

1 0