Multiscale representation of hexahedral meshes & compression

Companion pages:

• HexaShrink, an exact scalable framework for hexahedral meshes with attributes and discontinuities: multiresolution rendering and storage of geoscience models

• HexaShrink 4 Mesh, Decomposition tool for Hexahedral meshes used in Geosciences: Multi-resolution decomposition of the grid geometry and associated properties
• HAL page

A full-scale geological grid (or 3D Hexahedral mesh in Corner-Point grid) structure is decomposed onto embedded wavelet-like scales while preserving discontinuities, here geological faults (red), using a morphological 2D wavelet:

Geological grid structures and discontinuities preservation (red painted faults)

Categorical properties like rock types (sandstone, limestone, shale)  can be upscaled according to a dedicated non-linear decomposition called modelet (patent #20170344676: Method of exploitation of hydrocarbons of an underground formation by means of optimized scaling):

Hexahedral mesh categorical property: rock type

Continuous properties (saturation, porosity, permeability, temperature) can be homogenized with a 3D Haar wavelet:

Hexahedral mesh continuous property: porosity

The HexaShrink methodology described above is detailed in the recently published paper: 

• HexaShrink, an exact scalable framework for hexahedral meshes with attributes and discontinuities: multiresolution rendering and storage of geoscience models, Jean-Luc Peyrot, Laurent Duval, Frédéric Payan, Lauriane Bouard, Lénaïc Chizat (now at INRIA, ENS, PSL Research University Paris), Sébastien Schneider (now at HoloMake), Marc Antonini. Computational Geosciences, May2019

With huge data acquisition progresses realized in the past decades and acquisition systems now able to produce high resolution point clouds, the digitization of physical terrains becomes increasingly more precise. Such extreme quantities of generated and modeled data greatly impact computational performances on many levels: storage media, memory requirements, transfer capability, and finally simulation interactivity, necessary to exploit this instance of big data. Efficient representations and storage are thus becoming "enabling technologies" in simulation science. We propose HexaShrink, an original decomposition scheme for structured hexahedral volume meshes. The latter are used for instance in biomedical engineering, materials science, or geosciences. HexaShrink provides a comprehensive framework allowing efficient mesh visualization and storage. Its exactly reversible multiresolution decomposition yields a hierarchy of meshes of increasing levels of details, in terms of either geometry, continuous or categorical properties of cells. Starting with an overview of volume meshes compression techniques, our contribution blends coherently different multiresolution wavelet schemes. It results in a global framework preserving discontinuities (faults) across scales, implemented as a fully reversible upscaling. Experimental results are provided on meshes of varying complexity. They emphasize the consistency of the proposed representation, in terms of visualization, attribute downsampling and distribution at different resolutions. Finally, HexaShrink yields gains in storage space when combined to lossless compression techniques.

And there is a patent associated to HexaShrink, Method of exploitation of hydrocarbons of an underground formation by means of optimized scaling:

Method of exploitation of hydrocarbons of an underground formation by means of optimized scaling

Big data, fishes and cooking: fourteen shades of "V"

[At this short post, you can access the 14 "V" often glued to Bug Data, including vacuity]

To Lao Tzu is often attributed (I cannot access the original meaning):

Govern a great nation as you would cook a small fish. Do not overdo it.

Today's wisdom could be:

Deal with Big data as you would process a small signal. Do not over-expect from it, do not over-fit it, do not-overinterpret it.

Luckily, Big data does not exist, where Making The Most Of Small Data is advocated. This is a bit like teenage sex:

“Big Data is like teenage sex: everyone talks about it, nobody really knows how to do it, everyone thinks everyone else is doing it, so everyone claims they are doing it.”

In the What exactly is Big Data StackExchange question, I have listed all 14 "V" that could describe big data, including... vacuity. They are: Validity, Value, Variability/Variance, Variety, Velocity, Veracity/Veraciousness, Viability, Virtuality, Visualization, Volatility, Volume and Vacuity.

Facebook FAIR(ies) in Paris

Paris is buzzing about the announcement of the new european research center of Facebook in Paris. This was already known around April/May. Six  "fairies" are supposed to have joined Facebook FAIR, or Facebook Artificial Intelligence (AI) Research center. They will do some magical data science (or dédoménologie), under the guidance of Yann LeCun. He was the host of the day "Data Science and Massive Data Analysis" on the campus of ESIEE Paris, Ecole des Ponts ParisTech and Université Paris-Est Marne-la-Vallée (Paris at large) on June 12th 2014. It's not eerie, it's ESIEE.

After Menlo Park and New York, this center, the third and the first outside the US, has been attracted to City of lights.  Where they will bring their TORCH for our enlightenment. Attracted by  moths around a flame, by the local talents and excellent education facilities in artificial intelligence and computer science, and probably substantial financial incentives.They are also nearing Google headquarters in Paris. Google's HQ inauguration enjoyed the presence of former rightist président Nicolas Sarkozy. Will there be a people appearance of leftist François Hollande? Internet giants (GAFA, ABTX) are waging wars in our data. Remember Bertrand Russell, for who "War does not determine who is right - only who is left".

Real fairy

Those first  fairies could be (provisional, from Facebook choisit Paris pour installer sa nouvelle équipe de recherche européenne sur l’intelligence artificielle):

Camille Couprie (NYU, on leave from IFPEN)

Florent Perronnin (form. Panasonic and Xerox)

Hervé Jégou (INRIA)

Holger Schwenk (DeepLingo, université du Maine). Nota: the Facebook link is not active (201506032340), and points to G. Synnaeve's as if Holger was not in charge yet. His other page.

Gabriel Synnaeve (Ecole normale supérieure)

Nicolas Usunier (UTC)

So a large portion of the fairies are male, which may not be fair to the magical creatures, knowing that female fairies usually have more power. Two handful more talents would joint by the end of the year, 25 to 50 in the years to come. Figures vary with sources, depending on permanent positions or PhD and post-doctorants. That is big data.

Sources:
Google news full coverage
Facebook opens an artificial intelligence research lab in Paris

Facebook ouvre un laboratoire d’intelligence artificielle à Paris

Intelligence artificielle : Facebook écrit une partie du futur à Paris.
Facebook mise sur Paris 
Intelligence Artificielle : Facebook ouvre un centre de recherche à Paris

The law of excessive gardening in education

Once upon a time. the term proletarian (or a Latin equivalent) used refer to  a Roman citizen who was so poor that he only had his children considered as his property. The term proles stands here for descendants (or litter). The term evolved through Marxism, to workers without capital or production means, who should sell their own work-force. The term can be somehow extended to the loss of knowledge of the production tools. An example lies in the comparison between the craftsman or artisan, who masters his tools, and may even be able to repair them, and manages a series of processes, as opposed to the factory worker, whose work has been taylorized and who lacks of knowledge in the whole meaning of the chain, or the functioning of the robots he "controls".

The concept of proletarianization has been used more recently by Bernard Stiegler (Ars Indutrialis), to describe a pauperization, not in terms of wealth, but in terms of ability to do, to make and to live. An externalization and therefore a loss of knowledge and memory. 

I believe proletarianization, in that sense, is rampant, and pervades all strata of the society: at every level of work, at least in institutions or companies, there is a loss of sense and understanding about the way stuff works. A corollary to Peter's principle. To make a long story short, strategic visions have progressively been replaced by indicator-based management. In science evaluation, the infamous impact factor or h-index are examples of such indicators. Stock-value and quality-based management are other examples. 

Peter's principle: (success>advancement)^n>failure

The top of proletarianization spread was given by Alan Greenspan, the former chairman of the Federal Reserve, who once told the CNBC that he did not fully understand the scope of the subprime mortgage market until well into 2005 and could not make sense of the complex derivative products created out of mortgages. Alan Greenspan, the chief banker of the world, was mystified... [EDIT 2021/0410: ThinkProgress archive : Greenspan: I Was ‘Mystified’ By The Subprime Mortgage Market]

So what's got the maths to do with it?

About two years ago, in April 2012, there was a conference called Fixing mathematical education. There i learned the effective law of excessive learning in mathematics from Alexandre V. Borovik:

To be able to use maths at certain level it is necessary to learn it at the next level

A week ago, Alexandre Borovik sent me a link to his preprint, Calling a spade a spade: Mathematics in the new pattern of division of labour:

The growing disconnection of the majority of population from mathematics is becoming a phenomenon that is increasingly difficult to ignore. This paper attempts to point to deeper roots of this cultural and social phenomenon. It concentrates on mathematics education, as the most important and better documented area of interaction of mathematics with the rest of human culture.
    I argue that new patterns of division of labour have dramatically changed the nature and role of mathematical skills needed for the labour force and correspondingly changed the place of mathematics in popular culture and in the mainstream education. The forces that drive these changes come from the tension between the ever deepening specialisation of labour and ever increasing length of specialised training required for jobs at the increasingly sharp cutting edge of technology.
    Unfortunately these deeper socio-economic origins of the current systemic crisis of mathematics education are not clearly spelt out, neither in cultural studies nor, even more worryingly, in the education policy discourse; at the best, they are only euphemistically hinted at.
    This paper is an attempt to describe the socio-economic landscape of mathematics education without resorting to euphemisms. 

The pdf is here. Alexandre claims that "The communist block was destroyed by a simple sentiment: If they think they pay me let them think I am working. Mathematics education in the West is being destroyed by a quiet thought (or even a subconscious impulse): If they think they teach me something useful, let them think I am learning." My experience as a part-time teacher is that it is increasingly difficult to have students learn things. Most of them are especially disgusted by the concept of "learning by heart" (wait, everything is in the Internet, isn't it?). While they could just try to understand. 

For a long time,  people could have proudly claimed that "I have never been good at mathematics, but I live happily without it". The XXth century has been rich in discoveries that have both pervaded the society (basically, from the transistor to the mp3). The pitfall is many users have no idea about the way these technologies work, and happily put their agenda, thoughts, entertainment time and finally life (pictures, films) in those hands. 

The world seemingly grows a local era where data becomes important (a new gold, a novel oil?) and big data or data science are slowly emerging as potentially disruptive technologies. Then, Alexandre states that "the West is losing the ability to produce competitively educated workers for mathematically intensive industries". It is high times to rethink (mathematical) education, as its changes may be much slower than the present evolution of technologies. 

Nota bene: and Igor, just for you, there is a phase transition ("The crystallisation of a mathematical concept (say, of a fraction), in a child's mind could be like a phase transition in a crystal") and an aha moment ("An aha! moment is a sudden jump to another level of abstraction")

Learning meets compression: small-data-science internship (IFPEN)

We (Camille Couprie/Laurent Duval) are looking for a higly motivated master/engineering school student for an internship on the "Compatibility between sparse machine learning and lossy compression" at IFPEN.

Internship subject: [french/english]

Many experimental designs acquire continuous or salve signals or images. Those are characteristic of a specific phenomenon. One may find examples at IFPEN in seismic data/images, NDT/NDE acoustic emissions (corrosion, battery diagnosis) engine benches (cylinder pressure data, fast camera), high-thoughput screening in chemistry. Very often, such data is analyzed with standardized, a priori indices. Comparisons between different experiments (difference- or classification-based) are often based on the same indices, without resorting to initial measurements.

The increasing data volume, the variability in sensor and sampling, the possibility of different pre-processing yield two problems: the management and access to data (« big data ») and their optimal exploitation by dimension reduction methods, supervised or unsupervised learning (« data science »). This project aims at the analysis of the possibility of a joint compressed representation of data and the extraction of pertinent indicators, at different characteristic scales, and the relative impact of the first aspect (lossy compression degradation) over the second aspect (precision and robustness of extracted feature indicators).

The internship possesses a dual goal. The first aspect will be dealing with scientific research on sparse signal/image representations with convolution networks based on multiscale wavelet techniques, called scattering networks. Their descriptors (or footprints) possess fine translation, rotation and scale invariance. Those descriptors will be employed for classification and detection. The second aspect will carry on the impact of lossy compression on the preceeding results, and the development of novel sparse representations for joint compression and learning.

J. Bruna, S. Mallat. Invariant scattering convolution networks. IEEE Trans. on Patt. Anal. and Mach. Int., 2010
L. Jacques, L. Duval, C. Chaux, G. Peyré, A Panorama on Multiscale Geometric Representations, Intertwining Spatial, Directional and Frequency Selectivity, Signal Processing, 2011
C. Couprie, C. Farabet, L. Najman, Y. LeCun, Convolutional Nets and Watershed Cuts for Real-Time Semantic Labeling of RGBD Videos, Journal of Machine Learning Research, 2014

A PhD thesis (Characteristic fingerprint computation and storage for high-throughput data flows and their on-line analysis, with J.-C. Pesquet, Univ. Paris-Est) is proposed, starting September 2015.

Information update: http://www.laurent-duval.eu/lcd-2015-intern-learning-compression.html

Big data and Data science: LIX colloquium 2014

Sketch of the Hype Cycle for Emerging Technologies

Data science and Big data are two concepts at the tip of the tongue and the top of the Gartner Hype Cycle for Emerging Technologies. Close to the peak of inflated expectations. The Data science LIX colloquium 2014 at Ecole Polytechnique, organized by Michalis Vazirgiannis from DaSciM was held yesterday on the Plateau de Saclay, which may have prevented some to attend the event. Fortunately, it was webcast.

The talks covered a wide range of topics pertaining to Datacy (data + literacy). The community detection in graphs (with survey) keynote promoted local optimization (OSLOM, with order statistics). It was said than "We should define validation procedures even before starting developing algorithms", including negative tests; on random graphs, a clustering method should find non prominent cluster (except the whole graph), in other words no signal in noise. But there was no mention to phase transition in clustering. The variety of text data (SMS, tweets, chats, emails, news web pages, books, 100 languages, OCR and spelling mistakes) and its veracity was questioned with Facebook estimating that between 5% and 11% of accounts are fake, and 68.8 percent of the Internet is spam (how did they get the 3 figures precision?). News-hungry people would be interested in EMM News, a media watch tool aggregating 10000 RSS flux and 4000 news aggregators. With all these sources, some communities are concerned with virtual ghost town effects, and look for way to spark discussions (retweets and the likes) to keep social activity alive. Flat approaches or hierarchical grouping are still debated challenges in large-scale classification and web-scale taxonomies. Potentially novel graph structures (hypernode graphs, related to hypergraphs or maybe n-polygraphs) with convex stability and spectral theory are also proposed in the first part of the colloquium.

Big Data Cap Gap: the space between all and relevant data

While Paris-Saclay center for data science has opened its website, the unbalanced data was exposed around the HiggsML data-driven challenge. Less than 100 Higgs bosons (expected) to be detected in 10^10 yearly. Big-data analogs of the greek Pythia, as well as efficient indexing and mining methods would necessary to harness the data beast. More industrials talks concluded the colloquium, given by AXA, Amazon and Google representatives, which i could not attend, left with the so-called "crap gap" in mind, i. e. the gap between Relevant Data and Big Data. 

Innovation driven by large data sets still requires, at least, vague goals in mind. In Latin, "Ignoranti quem portum petat nullus suus uentus (ventus) est", wrote Sénèque in his 71th letter to Lucilius. A possible translation in English: "When a man does not know what harbour he is making for, no wind is the right wind". In German, "Dem weht kein Wind, der keinen Hafen hat, nach dem er segelt". And "Il n'y a point de vent favorable pour celui qui ne sait dans quel port il veut arriver" in French.

All of the information, and possibly information you need, may be found in the following program and videos. As the videos are not split into talks, the time codes are provided, thanks to the excellent suggestion (and typos corrections) by Igor Carron.

LIX colloquium 2014 on Data Science LIVE part 1

• 00:00:00 > 00:22:22: Introduction and program
• 00:22:22 > 01:22:18: Keynote speech: Community detection in networks, Santo Fortunato, Aalto University
• 01:22:18 > 01:57:30: Text and Big Data, Gregory Grefenstette, Inria Saclay - Île de France
• 01:57:30 > 02:29:23: Accessing Information in Large Document Collections: classification in web-scale taxonomies, Eric Gaussier, Université Joseph Fourier (Grenoble I)
• 02:29:23 > 03:01:32: Shaping Social Activity by Incentivizing Users, Manuel Gomez Rodriguez, Max Planck Institute for Software Systems
• 03:01:32 > 03:38:00: Machine Learning on Graphs and Beyond, Marc Tommasi, Inria Lille

LIX colloquium 2014 on Data Science LIVE part 2

• 00:00:00 > 00:33:57: Learning to discover: data science in high-energy physics and the HiggsML challenge, Balázs Kégl, CNRS
• 00:34:11 > 01:06:15: Big Data on Big Systems: Busting a Few Myths, Peter Triantafillou, University of Glasgow
• 01:06:15 > 01:38:29: Big Sequence Management, Themis Palpanas, Paris Descartes University

LIX colloquium 2014 on Data Science LIVE part 3 

• 00:00:00 > 00:38:11: Understanding Videos at YouTube Scale, Richard Washington, Google
• 00:38:11 > 01:05:48: AWS's big data/HPC innovations, Stephan Hadinger, Amazon Web Services
• 01:05:48 > 02:02:41: Big Data in Insurance - Evolution or disruption? Stéphane Guinet, AXA 
• 02:02:41 > 02:06:35: Closing words on a word cloud (with time, series, graph and classification are the big four)

Information overload - And no more trivia, fool!

[Update 2014/05/20 with Ann Blair publications] There is a recent concern about information overload. Or is there? According to the following independent sources:

• Science 2.0 Approach to Research, by Erik Duval (not family)
• Academic publishing is archaic, by Daniel Lemire

the problem is not so recent. Ann Blair already informed us in 2003 that there were Reading Strategies for Coping with Information Overload ca. 1550-1700:

The "multitude of books" was a subject of wonder and anxiety for authors who reflected on the scholarly condition in the sixteenth through the eighteenth centuries. In the preface to his massive project of cataloguing all known books in the Bibliotheca univeralis (1545) Conrad Gesner complained of that "confusing and harmful abundance of books," a problem which he called on kings and princes and the learned to solve.  By 1685 the situation seemed absolutely dire to Adrien Baillet, who warned:

"We have reason to fear that the multitude of books which grows every day in a prodigious fashion will make the following centuries fall into a state as barbarous as that of the centuries that followed the fall of the Roman Empire. Unless we try to prevent this danger by separating those books which we must throw out or leave in oblivion from those which one should save and within the latter between what is useful and what is not."

In this way Baillet claimed to have warded off barbarity itself with his collection of judgments on the learned in his nine-volume (and still only half-completed) Jugemens des sçavans

The "information overload" or "scholar big data" is push further in: Too Much to Know. Managing Scholarly Information before the Modern Age (2010):

The flood of information brought to us by advancing technology is often accompanied by a distressing sense of “information overload,” yet this experience is not unique to modern times. In fact, says Ann M. Blair in this intriguing book, the invention of the printing press and the ensuing abundance of books provoked sixteenth- and seventeenth-century European scholars to register complaints very similar to our own. Blair examines methods of information management in ancient and medieval Europe as well as the Islamic world and China, then focuses particular attention on the organization, composition, and reception of Latin reference books in print in early modern Europe. She explores in detail the sophisticated and sometimes idiosyncratic techniques that scholars and readers developed in an era of new technology and exploding information.

Listen to 23' of Clay Shirky at Web 2.0 Expo NY, 19 September 2008, where you learn, along  the movie narration flood, "It's Not Information Overload. It's Filter Failure":

In Reading Strategies for Coping With Information Overload ca. 1550-1700, Ann Blair teaches us that:

The "multitude of books" was a subject of wonder and anxiety for authors who reflected on the scholarly condition in the sixteenth through the eighteenth centuries. In the preface to his massive project of cataloguing all known books in the Bibliotheca univeralis (1545) Conrad Gesner complained of that "confusing and harmful abundance of books," a problem which he called on kings and princes and the learned to solve.1 By 1685 the situation seemed absolutely dire to Adrien Baillet, who warned [...]

So apparently, the information overload problem is no novelty. Looks like information is riding an exponential wave, as in the standard chart (left), whose derivative is just about an exponential. Reminds me of the following joke: $1$ and $e^x$ sit in an old favorite room of a restaurant. Waiting for food arrival - noontime. Suddenly, $1$ gets terrified and cry at $e^x$: "hide me, hide me, here enters a derivative operator!". Proud and fierce,  $e^x$ hides the constant behind her back, and defies the operator: "i am $e^x$, i don't fear you". "Sure!" the operator replies, "i am $\frac{\partial}{\partial y}$". 

As Clay Shirky says, "If you have a problem for a long time, it's not a problem... Maybe it's a fact!" (IMHO probably emphasized by the Internet/media mode of "content creation", more than often a mere duplication (pure redundancy) or basic distorsion (jamming) of pre-existing content, with reduced added value), to fill the media tubes and pipes (forlorn media ovation). Since more and more people write, blog, tweet and buzz about IO, further adding low valued load. IO might just be neither a true problem nor a false one. René Thom (in Paraboles et Catastrophes, Champs Flammarion, p. 127) reminds us that "Ce qui limite le vrai n’est pas le faux, mais l’insignifiant", approximately translated to "What limits truth, it is not forgery but trifle/insignificance" (quote courtesy of Olivier Rey, whose Itinéraire de l'égarement deserves close reading, admiration of no lover). IO as an inane vomit flood roar (sounds like a death metal song title, but only an anagram).

Yet still assuming that "more data = better decisions", some argue that the "real problem is the lack of efficient strategies to index, summarize, filter, cross-reference and archive information", or propose "A Framework for Information Overload Research in Organizations Insights from Organization Science, Accounting, Marketing, MIS, and Related Disciplines" (Eppler, Mengis, 2003). But more insignificant data may as well lead to zero decisions, as gaussian disturbances may vanish as the square root on the number of observations. Second thought, not so much with rounding, see Statistical Analysis for Rounding Data (Zhidong Bai, 2006). The current trend in signal or image processing is generally similar: acquire more data, at higher frequency, with more precision (watch out, formation on evil road), hoping signal processing, statistics and data mining will cope with the flood and deliver precious information. An extreme example arises in seismic processing, where petabytes of data ("but also storage systems that can handle petabytes of data daily") are gathered. Yet, due to the computational burden and memory footprint, the relative time spent on "fine processing" with respect to data reading, loading, handling, sorting seems tiny.

Thank to the availability of low cost sensors and band-width, the data overload plague is spreading. More and more data, less and less time to process it properly, massive low-quality batch filtering are favored. Signal and image processing enter the dark area of weak signals and information overlook. I pray everyday (no variation of me, Lord) for my colleagues to tell me: next step, we are going to acquire much less signals (and favor no more dilation of disk space), to spend the remaining time on their processing.