C++ Logo


Advanced search

Subject: Re: Jan 9 SG19 Zoom
From: Michael Wong (fraggamuffin_at_[hidden])
Date: 2020-01-09 13:55:20

Meeting notes by Michael W

On Thu, Jan 9, 2020 at 12:03 PM Michael Wong <fraggamuffin_at_[hidden]> wrote:

> SG19 Machine Learning 2 hours
> Hi,
> Michael Wong is inviting you to a scheduled Zoom meeting.
> Topic: SG19 monthly Dec 2019-Mar 2020
> Time: Jan 9 , 2019 01:00 PM Eastern Time (US and Canada)
> Every month on the Second Thu, until Mar 12, 2020, 4 occurrence(s)
> Dec 12, 2019 01:00 PM
> Jan 9, 2020 01:00 PM
> Feb 13, 2020 01:00 PM
> Mar 12, 2020 01:00 PM
> Please download and import the following iCalendar (.ics) files to
> your
> calendar system.
> Monthly:
> https://iso.zoom.us/meeting/u5IudOyrrD0o6QfidlHRJTh2cH9H6gRuPA/ics?icsToken=98tyKu-urTgvGdaTslyCe7MtOZX_bN-xjSd_rKpZkDfXKRRbMADeb8oUNYBqIPmB
> Join from PC, Mac, Linux, iOS or Android: https://iso.zoom.us/j/663353262
> Or iPhone one-tap :
> US: +14086380968,,663353262# or +16468769923,,663353262#
> Or Telephone:
> Dial(for higher quality, dial a number based on your current
> location):
> US: +1 408 638 0968 or +1 646 876 9923 or +1 669 900 6833 or 877
> 369 0926 (Toll Free) or 877 853 5247 (Toll Free)
> Meeting ID: 663 353 262
> International numbers available: https://iso.zoom.us/u/abhaIjFKLZ
> Or Skype for Business (Lync):
> https://iso.zoom.us/skype/663353262
> Agenda:
> 1. Opening and introductions
> 1.1 Roll call of participants
Phil Ratsloff, Marco Foco, Andrew Lumsdaine, jesun Firoz, Kdeweese,
Michael Wong, Matthew Galati, Vaibhav, william tambellini, Jens Maurer

> 1.2 Adopt agenda
> 1.3 Approve minutes from previous meeting, and approve publishing
> previously approved minutes to ISOCPP.org
> 1.4 Action items from previous meetings
> 2. Main issues (125 min)
> 2.1 General logistics
> All C++ reflector are now moved to listserv
> https://lists.isocpp.org/mailman/listinfo.cgi/sg19
Lists of features we are working on:

> 2.2 Paper reviews
> Review Belfast results.
> 2.2.1: ML topics
> Richard Dosselman
> P1708R1: Math proposal for Machine Learning
> https://docs.google.com/document/d/1VAgcyvL1riMdGz7tQIT9eTtSSfV3CoCEMWKk8GvVuFY/edit
> P1709R1: Graph Proposal for Machine Learning
R2 proposal
 have 2 graph data structures
1 for directed and 1 for ordered graph
last telecon we show DFS and BFS implemented as ranges

what we have done
also have undirected graphs - what is the difference between directed and
 - both have vertex and edges, but undirected edges are edges, for directed
there are out and in edges, was trying to use a uniform api to remove that
 - still one place we use in and out where edge refers to 2 vertices
implemented shortest paths,
also have transitive closure
I have added category types, on whether we have sparse or dense graph,
a directed graph is a uniform graph and an out directed graph
bidirected, and unidirected follows
a sparse graph and a vertex range
request definition of dense (a matrix, random access inner, forward
iterator outter) vs sparse graph (random access outter, forward iterator to
we already have existing algo in library for textsearches
propose remove sparse and dense graph as it is implementation details
why integral vertex key? internal implementation requires we have integer
key to look up vertex, vector in this case, want to relax overtime
the less restrictive one is random access iterator, so a DAG has random
access iterators
what is teh key? -a DAG the key is from the vertex of container, for a map
the key is defined by user
should contrain on OutIter result_iter please
need to specify restrictions on G and so use concepts, same with OutIter

shortest path has arbitrary list so has to do memory allocation
shortest distance has no memory allocation
BGL17 approach didnt really have shortest path or BFS do anything other
then go through the graph
when u get to last vertex for the path, want to iterate each vertexes of
the path, so have inner and outer loop you need to walk through

will you output distance to targets with a filter? No there is no filter
shortest distance and shortest paths give you the same opotion with
leaves_only, so if you want mre sophisticated filters, it is possible
Do you really need leaves_only as a parameter; shortest_paths would only
need the parent, any partial path is also the shortest path, for Dijkstra,
just store the parent pointer instead of constructing the paths
so give them a range of what we have now, with the distance may be a better
way of doing that
another output u may want is an edge iterator, using a pair , along with a
vertex iterator

parent and distance, may want a path of vertexes directly; instead of
returning a vector of things, we just return a range
ok I will go back and work on getting both, implementation later after the
mailing deadline

what examples of graph data structure should we have?
compressed sparse row (CSR) is useful, for the user to build their own
concern that we are interpreting graph as ranges of ranges,notion of
dereferecing can be cumbersome, - that depends on on what algorithm
actually needs, so a compressed data structure is useful to meet the need
of the algorithm, so you can use MKL under the hood, may need to sync with
Intel, graph-BLAS as an extension of MKL, using CSR optimizing for AVX
sparse LA or graphs are memory bound, theer is not any optimization you can
apply to move things in memory any faster
CSR and adjacency edge list discussion
approach Intel Moscow team to see how they want to participate

in our case, we are not distinguishign dense vs sparse graph based on Jens

adapting this to their own data structues, - yes Jens mention wantign
interface to be minimal ,if std library has equivalent things, then we
shoudl reuse them.
I will look at CSR options

R1 proposal

> https://docs.google.com/document/d/1QkfDzGyfNQKs86y053M0YHOLP6frzhTJqzg1Ug_vkkE/edit?usp=sharing
> <
> https://nam02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdocs.google.com%2Fdocument%2Fd%2F1QkfDzGyfNQKs86y053M0YHOLP6frzhTJqzg1Ug_vkkE%2Fedit%3Fusp%3Dsharing&data=02%7C01%7CPhil.Ratzloff%40sas.com%7C729b2cf8502641e4ae5e08d749064578%7Cb1c14d5c362545b3a4309552373a0c2f%7C0%7C0%7C637058163592253027&sdata=4UQm8tqrcUbiZsr200UMrOaEModJYGNgP1oNot9PbAg%3D&reserved=0>
> P1707R0: Differentiable Programming by Marco Foco
explain differences automatic, vs symbolic differentiation
- auto works on algorithm ,and uses teh structure of the algorithm
- sym only works on expressions
also motivate why we want langage solution and not a library solution
-performance example demonstrate benefits
-but mainly you cannot do many things with library, need to use a specially
named type as in Enoki
want to enable this auto diff tool kit for other things like matrices
matrix and vector types support is very important
assume people using this library is different then the library writer - so
we will often combine multiple libraries together
prompt Andrew L on Tulsa library
example: https://joelcfd.com/automatic-differentiation/

a fork of Eigen "aimed at Algorithmic Differentiation (AD) ":
A recent paper:

Numerical Differentiation - a new paper
Could be a library solution which can land earlier
limit and choosing h
sqrt in C++20 is still not constexpr
is there a bets practice for moving instead of copying a function when it
is a pure function: let lewg decide
e.g. matrix solver ,so good to memoize f(x), and repeatedly call it with
different h
AL to send reference
complex step is not really a numerical solution

> P1416R1: SG19 - Linear Algebra for Data Science and Machine Learning
> https://docs.google.com/document/d/1IKUNiUhBgRURW-UkspK7fAAyIhfXuMxjk7xKikK4Yp8/edit#heading=h.tj9hitg7dbtr
> P1415: Machine Learning Layered list
> https://docs.google.com/document/d/1elNFdIXWoetbxjO1OKol_Wj8fyi4Z4hogfj5tLVSj64/edit#heading=h.tj9hitg7dbtr
> 2.2.2 SG14 Linear Algebra progress:
> Different layers of proposal
> https://docs.google.com/document/d/1poXfr7mUPovJC9ZQ5SDVM_1Nb6oYAXlK_d0ljdUAtSQ/edit
> 2.2.3 any other proposal for reviews?
> 2.3 Other Papers and proposals
> 2.5 Future F2F meetings:
Paper submission:

> 2.6 future C++ Standard meetings:
> https://isocpp.org/std/meetings-and-participation/upcoming-meetings
> -2020-02-10 to 15: Prague, Czech Republic
> - 2020-06-01 to 06: Bulgaria
> - 2020-11: (New York, tentative)
> - 2021-02-22 to 27: Kona, HI, USA
> 3. Any other business
> New reflector
> http://lists.isocpp.org/mailman/listinfo.cgi/sg19
> Old Reflector
> https://groups.google.com/a/isocpp.org/forum/#!newtopic/sg19
> <https://groups.google.com/a/isocpp.org/forum/?fromgroups=#!forum/sg14>
> Code and proposal Staging area
> 4. Review
> 4.1 Review and approve resolutions and issues [e.g., changes to SG's
> working draft]
> 4.2 Review action items (5 min)
> 5. Closing process
> 5.1 Establish next agenda
> 5.2 Future meeting
> Dec 12, 2019 01:00 PM
> Jan 9, 2020 01:00 PM: Jan 12 is mailing deadline
> Feb 13, 2020 01:00 PM
> Mar 12, 2020 01:00 PM

SG19 list run by sg19-owner@lists.isocpp.org

SG19 Archives on Google Groups