Enabling and Optimizing Non-linear Feature Interactions in Factorized Linear Algebra
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Li, Side
Chen, Lingjiao
Kumar, Arun
Accelerating machine learning (ML) over relational data is a key focus of the database community. While many real-world datasets are multi-table, most ML tools expect single-table inputs, forcing users to materialize joins before ML, leading to data redundancy and runtime waste. Recent works on 'factorized ML' address such issues by pushing ML through joins. However, they have hitherto been restricted to ML models linear in the feature space, rendering them less effective when users construct non-linear feature interactions such as pairwise products to boost ML accuracy. In this work, we take a first step towards closing this gap by introducing a new abstraction to enable pairwise feature interactions in multi-table data and present an extensive framework of algebraic rewrite rules for factorized LA operators over feature interactions. Our rewrite rules carefully exploit the interplay of the redundancy caused by both joins and interactions. We prototype our framework in Python to build a tool we call MorpheusFI. An extensive empirical evaluation with both synthetic and real datasets shows that MorpheusFI yields up to 5x speedups over materialized execution for a popular second-order gradient method and even an order of magnitude speedups over a popular stochastic gradient method.
 I might talk today's organizing three parts, motivation and background, the technical detail about our new framework, as well as some experiment results. And first of all, I'm going to talk about our motivation. Machine learning is being rapidly adopted everywhere, such as data analytics and online recognition systems. For example, a data scientist at Netflix will leverage machine learning techniques to determine whether to recommend a movie to users or not. And she might get two tables. One is a long-growing work history table with features such as user name and movie IDs. Well, another is a movie catalog table. Two tables are stored independently but connected by movie IDs. And like what she got, many real-world data sets are also multi-table. But most machine learning tools only expect a single table as input. Therefore, the data scientist must put a former drawing to materialize a single table from that it is after a single drawing table is obtained can she train machine learning models with it. Some problem arises from drawings. The drawing table created often has many entries that are simply duplicates of other roles. Later in the process of ML training, those duplicated entries will still be treated as the same ones leading to fewer effective flops in computations. And in recent years, there's a long-out work centered on the previous problem about ML overjoins, also known as factorized machine learning. They focus on avoiding the materialization of the drawing table and, instead, do the machine learning training directly on top of multi-table data. In particular, one of the most updated projects in the office explores this idea by coupling linear algebra with factorized ML. Their work is based on observations that many popular machine learning algorithms such as logistic regression are essentially made up of L.A. operations. So the idea of their work is basically hookup normalized data in abstraction called normalized matrix, which is similar to non-piles matrix class, but under the hood, Muffin has done some logical rewrite optimized for normalized data on an operator level. Then through it, L.A. rewrite rules and imports L.A. based machine learning algorithms and outputs factorized machine learning execution automatically. Because Muffin pushes machine learning through drawings, it provides better system efficiency and at the same time, it provides users an intuitive way to factorize their machine learning cause users only need to write their machine learning algorithms using L.A. And to go a little deeper into that, to formally represent Muffin's, suppose we have factor table S and dimension table R1, the project is equal to 0 for T. And the materialized wheel of T is basically the concatenation of X, S and X1. Whereas in Muffin's, the normalized matrix is a logic group of three elements, S, K1 and R1, where K1 is an indicator matrix encoding the primary key, primary key, foreign key dependency. So Muffin is so good, but though Muffin's is promising for performing L.A. based machine learning anomalous data, it is restricted by its linearity over feature space. For example, L.A. based generalized linear models offer unlawful data because they always try to create linear happening on data, but data might entail some nonlinear relationships. For this issue, we could employ a technique called feature interactions to answer if it's nonlineality among features. Here's an example. On the left, we have a matrix. After applying feature interactions, we get a much larger matrix on the right. The third column on the right comes from the multiplication of the first column on the left with itself. The first column on the right comes from the second column on the left with itself. And the last column comes from the multiplication across two columns on the left. All of those new features are created nonlinearly associating feature vectors with each other. And because of this nonlineality, feature interactions often boost model accuracy. But at the same time, since we have much more data, it might impact the system efficiency. And when applying feature interactions with L.A. based algorithms on normalized data, things could become much more complex and messy. Because a great portion of interaction features are actually created nonlinearly from the joint redundant data, we have a new type of joint interaction, interplayed redundancy. So how could we deal with that? Existing factorized machine learning frameworks doesn't seem to be helpful here, as this new redundancy is simply nonlinear. So this leads to our work. We wanted to have a factorized machine learning framework that can delineate double redundancy created by feature interactions and joints. To do a brief recap, most machine learning tools materialize both joints and interactions, whereas Mophias can factorize joints but can't really help with feature interactions. Our new framework, Mophias 5, can factorize both linear joint and nonlinear feature interactions. So let's dive into Mophias 5 framework. To integrate feature interactions into linear algebra, we first need to formalize them. We devise two types of operators. In one case, we have a single matrix M and wanted to get the interaction of it. We define the self-interaction of M as M ring. Therefore, the interaction of M is basically the concatenation of M and M ring. Here's an example. On the left, we have matrix M. On the right, we have the interaction of M which composes of M and M ring. In another case, we have multiple tables but still wanted to get the interactions across tables. Now, suppose we have two matrices, M1 and M2. We define the cross interaction of M1 and M2 as M1 circle product M2. Here's an example. We have M1 and M2. On the right, we have the cross interaction between them. The first column on the right comes from the modification across the first columns in M1 and M2. The second column in the cross interaction comes from the modification between the first column in M1 and the second column in M2 and so on and so forth. So putting it all together, suppose we still use a two-table join schema with table S and R1. The project equal join is still T but project equal join with interactions is not defined as the combination of T and T ring which is then equal to the complex equation on the right. In that complex equation, we have S ring and X1 ring come from the self-interaction of S and R1 correspondingly. And we also have the cross interaction between S and R1. Putting the P matrix on the far right, this is just a permutation matrix to change the order of official space if needed. So with feature interactions being defined, we now introduce our new abstraction, intact in normalized matrix. Our idea is simple. We wanted to augment the normalized matrix in Mophis with nonlinear feature interaction operators we define and rework the entire underlying hourly rewrite rules. Considering the same join schema, the INM is defined as a logic group of six elements where S hat, R1 hat and P are new elements in INM and K1 is still the same indicator matrix used in Mophis. For simplicity, we also define the cross interaction between S and K1 times R1 as R1 and P hat. So using this new abstraction, we overload hourly operators that arise in machine learning to automatically factorize both joins and interactions. To demonstrate how our abstraction works, we show how we rewrite left matrix multiplication operator, which is a common operator used in linear models. To factorize computations, we first cut W into chunks and multiply each chunk with a sub table. In our case, we have three sub products. For the first part, there is no redundancy, so there is no need to rewrite. For the second part, it has some join related redundancy. We could employ the technique in Mophis to address that, that is to multiply R1 hat with W1 hat first to create a much smaller product and then multiply K1 with it. But for the last part, the cross interaction between S and R1, it has both join and interaction redundancy. So this is the most challenging and normal part. I'm going to show you an example of, to let you know how we tackle this part. And to bring it up front, the way we tackle the cross interaction part is to manipulate the associativity between linear algebra and nonlinear operations. Here are the example matrices we will use in the illustration. To factorize the cross interaction part, the very first step is to cut W into chunks, each denoted as W1 and W2 correspondingly. To then multiply R1 with them and stick together the result into R1 prime. Next we multiply K1 and R1 prime to obtain M, which is pretty much like using the indicator matrix to expand R1 into a higher dimension. Next we perform a hardware product between M and S. Finally we take a result from the previous step to obtain the final result. And I know the illustration might be too fast and you're still confused. But in the interest of time, I hope you get our rough idea. And a formally expressed LMM with feature interactions can be factorized as follows. And thanks to our novel re-read rules, there are fewer flops used in computing the cross interaction part. I will also show how effective this is in the experiment session. In the paper, we have detailed re-read rules for other operators as well as some proofs for them. Please feel free to check them out. And lastly, I present our experiment result. We implement our interactive normalized matrix as a Python class by overloading non-piles and de-array. Meanwhile, we support supply sales bar matrix to exploit pre-existing optimization message. We also have a pattern retention that will rewrite both forward and backward propagation. For the dataset, we use seven re-read datasets with dark schema and all of them come from Mophice project and have at least two dimension tables. We pre-processed all datasets as presenter machine learning practice. We also precipitated all datasets into training and validation set randomly. Due to the time constraint, we only look at the result of BL dataset for today's talk. And with all those set up, we now check whether Mophice can provide any runtime improvement on real data in comparison with alternatives. So we look at two key metrics. The time approach takes to reach the convergence and its convergence behavior. For the optimization message, we use Adam and LBFGS. For the machine learning algorithms, we experiment with logistic regression and linear SVM. We compare the following approaches by training machine learning models until convergence with then look at their time to convergence and convergence behavior. For the first three pairs of approaches are our baseline and last one is our framework Mophice. And on the top are the software and hardware set up we use in our experiment. We now look at the result for Yelp dataset with logistic regression. Here's the plot. The X axis is the runtime in seconds. The Y axis is the validation error. As we are training machine learning models, we should see validation error going down over time. And for example, the orange line on the plot shows how LBFGS on materialized data converges. LBFGS on materialized data doesn't convert much until 20 seconds. Then it ramps up very quickly until 40 seconds it starts to slow down. Whereas Adam shows a much better convergence curve. At the very beginning, it learns at a very fast pace and then slows down around 20 seconds and smooths it up around 30 seconds. LBFGS with Mophice Pi shows a similar learning curve except it converges much faster than LBFGS on materialized data, but it's still slower than Adam. This is because Mophice Pi addresses the joint redundancy, but it's still burdened by the interaction redundancy. Lastly, the curve of our work Mophice Pi is most interesting. Though Adam converges earlier than both materialized and Mophice Pi with LBFGS, the first per epoch efficiency of Mophice Pi inverse the train for LBFGS and converges earlier than Adam. If we look at the table of average runtime to convergence, we can see LBFGS on materialized data used to be much slower than Adam. But Mophice Pi has changed the train. It makes the second out other message LBFGS converge even faster than the state of art, Adam. In the paper, there are more results on the real-world data set such as our LBFGS, we made LBFGS like achieve up to 36 X Bs of all Adam and other things like we started on the real-world data set, and that's how the sparsity impacts the usage of our framework. Please do check out those interesting results. And that's my talk day. All the paper, code, and data is available at this webpage. I'm best reachable at this email and Twitter account if you want to follow me for some photography. Thanks. Thank you.
 I might talk today's organizing three parts, motivation and background, the technical detail  about our new framework, as well as some experiment results.  And first of all, I'm going to talk about our motivation.  Machine learning is being rapidly adopted everywhere, such as data analytics and online  recognition systems.  For example, a data scientist at Netflix will leverage machine learning techniques to determine  whether to recommend a movie to users or not.  And she might get two tables.  One is a long-growing work history table with features such as user name and movie IDs.  Well, another is a movie catalog table.  Two tables are stored independently but connected by movie IDs.  And like what she got, many real-world data sets are also multi-table.  But most machine learning tools only expect a single table as input.  Therefore, the data scientist must put a former drawing to materialize a single table from  that it is after a single drawing table is obtained can she train machine learning models  with it.  Some problem arises from drawings.  The drawing table created often has many entries that are simply duplicates of other  roles.  Later in the process of ML training, those duplicated entries will still be treated as  the same ones leading to fewer effective flops in computations.  And in recent years, there's a long-out work centered on the previous problem about ML  overjoins, also known as factorized machine learning.  They focus on avoiding the materialization of the drawing table and, instead, do the  machine learning training directly on top of multi-table data.  In particular, one of the most updated projects in the office explores this idea by coupling  linear algebra with factorized ML.  Their work is based on observations that many popular machine learning algorithms such as  logistic regression are essentially made up of L.A. operations.  So the idea of their work is basically hookup normalized data in abstraction called normalized  matrix, which is similar to non-piles matrix class, but under the hood, Muffin has done  some logical rewrite optimized for normalized data on an operator level.  Then through it, L.A. rewrite rules and imports L.A. based machine learning algorithms and  outputs factorized machine learning execution automatically.  Because Muffin pushes machine learning through drawings, it provides better system efficiency  and at the same time, it provides users an intuitive way to factorize their machine learning  cause users only need to write their machine learning algorithms using L.A.  And to go a little deeper into that, to formally represent Muffin's, suppose we have factor table  S and dimension table R1, the project is equal to 0 for T. And the materialized wheel of  T is basically the concatenation of X, S and X1.  Whereas in Muffin's, the normalized matrix is a logic group of three elements, S, K1  and R1, where K1 is an indicator matrix encoding the primary key, primary key, foreign key  dependency.  So Muffin is so good, but though Muffin's is promising for performing L.A. based machine  learning anomalous data, it is restricted by its linearity over feature space.  For example, L.A. based generalized linear models offer unlawful data because they always  try to create linear happening on data, but data might entail some nonlinear relationships.  For this issue, we could employ a technique called feature interactions to answer if it's  nonlineality among features.  Here's an example.  On the left, we have a matrix.  After applying feature interactions, we get a much larger matrix on the right.  The third column on the right comes from the multiplication of the first column on the left  with itself.  The first column on the right comes from the second column on the left with itself.  And the last column comes from the multiplication across two columns on the left.  All of those new features are created nonlinearly associating feature vectors with each other.  And because of this nonlineality, feature interactions often boost model accuracy.  But at the same time, since we have much more data, it might impact the system efficiency.  And when applying feature interactions with L.A. based algorithms on normalized data,  things could become much more complex and messy.  Because a great portion of interaction features are actually created nonlinearly from the  joint redundant data, we have a new type of joint interaction, interplayed redundancy.  So how could we deal with that?  Existing factorized machine learning frameworks doesn't seem to be helpful here, as this new  redundancy is simply nonlinear.  So this leads to our work.  We wanted to have a factorized machine learning framework that can delineate double redundancy  created by feature interactions and joints.  To do a brief recap, most machine learning tools materialize both joints and interactions,  whereas Mophias can factorize joints but can't really help with feature interactions.  Our new framework, Mophias 5, can factorize both linear joint and nonlinear feature interactions.  So let's dive into Mophias 5 framework.  To integrate feature interactions into linear algebra, we first need to formalize them.  We devise two types of operators.  In one case, we have a single matrix M and wanted to get the interaction of it.  We define the self-interaction of M as M ring.  Therefore, the interaction of M is basically the concatenation of M and M ring.  Here's an example.  On the left, we have matrix M. On the right, we have the interaction of M which composes  of M and M ring.  In another case, we have multiple tables but still wanted to get the interactions across  tables.  Now, suppose we have two matrices, M1 and M2.  We define the cross interaction of M1 and M2 as M1 circle product M2.  Here's an example.  We have M1 and M2.  On the right, we have the cross interaction between them.  The first column on the right comes from the modification across the first columns in M1  and M2.  The second column in the cross interaction comes from the modification between the first  column in M1 and the second column in M2 and so on and so forth.  So putting it all together, suppose we still use a two-table join schema with table S  and R1.  The project equal join is still T but project equal join with interactions is not defined  as the combination of T and T ring which is then equal to the complex equation on the  right.  In that complex equation, we have S ring and X1 ring come from the self-interaction of  S and R1 correspondingly.  And we also have the cross interaction between S and R1.  Putting the P matrix on the far right, this is just a permutation matrix to change the  order of official space if needed.  So with feature interactions being defined, we now introduce our new abstraction, intact  in normalized matrix.  Our idea is simple.  We wanted to augment the normalized matrix in Mophis with nonlinear feature interaction  operators we define and rework the entire underlying hourly rewrite rules.  Considering the same join schema, the INM is defined as a logic group of six elements  where S hat, R1 hat and P are new elements in INM and K1 is still the same indicator  matrix used in Mophis.  For simplicity, we also define the cross interaction between S and K1 times R1 as R1  and P hat.  So using this new abstraction, we overload hourly operators that arise in machine learning  to automatically factorize both joins and interactions.  To demonstrate how our abstraction works, we show how we rewrite left matrix multiplication  operator, which is a common operator used in linear models.  To factorize computations, we first cut W into chunks and multiply each chunk with a  sub table.  In our case, we have three sub products.  For the first part, there is no redundancy, so there is no need to rewrite.  For the second part, it has some join related redundancy.  We could employ the technique in Mophis to address that, that is to multiply R1 hat with  W1 hat first to create a much smaller product and then multiply K1 with it.  But for the last part, the cross interaction between S and R1, it has both join and interaction  redundancy.  So this is the most challenging and normal part.  I'm going to show you an example of, to let you know how we tackle this part.  And to bring it up front, the way we tackle the cross interaction part is to manipulate  the associativity between linear algebra and nonlinear operations.  Here are the example matrices we will use in the illustration.  To factorize the cross interaction part, the very first step is to cut W into chunks,  each denoted as W1 and W2 correspondingly.  To then multiply R1 with them and stick together the result into R1 prime.  Next we multiply K1 and R1 prime to obtain M, which is pretty much like using the indicator  matrix to expand R1 into a higher dimension.  Next we perform a hardware product between M and S.  Finally we take a result from the previous step to obtain the final result.  And I know the illustration might be too fast and you're still confused.  But in the interest of time, I hope you get our rough idea.  And a formally expressed LMM with feature interactions can be factorized as follows.  And thanks to our novel re-read rules, there are fewer flops used in computing the cross  interaction part.  I will also show how effective this is in the experiment session.  In the paper, we have detailed re-read rules for other operators as well as some proofs  for them.  Please feel free to check them out.  And lastly, I present our experiment result.  We implement our interactive normalized matrix as a Python class by overloading non-piles  and de-array.  Meanwhile, we support supply sales bar matrix to exploit pre-existing optimization message.  We also have a pattern retention that will rewrite both forward and backward propagation.  For the dataset, we use seven re-read datasets with dark schema and all of them come from  Mophice project and have at least two dimension tables.  We pre-processed all datasets as presenter machine learning practice.  We also precipitated all datasets into training and validation set randomly.  Due to the time constraint, we only look at the result of BL dataset for today's talk.  And with all those set up, we now check whether Mophice can provide any runtime improvement  on real data in comparison with alternatives.  So we look at two key metrics.  The time approach takes to reach the convergence and its convergence behavior.  For the optimization message, we use Adam and LBFGS.  For the machine learning algorithms, we experiment with logistic regression and linear SVM.  We compare the following approaches by training machine learning models until convergence  with then look at their time to convergence and convergence behavior.  For the first three pairs of approaches are our baseline and last one is our framework  Mophice.  And on the top are the software and hardware set up we use in our experiment.  We now look at the result for Yelp dataset with logistic regression.  Here's the plot.  The X axis is the runtime in seconds.  The Y axis is the validation error.  As we are training machine learning models, we should see validation error going down  over time.  And for example, the orange line on the plot shows how LBFGS on materialized data converges.  LBFGS on materialized data doesn't convert much until 20 seconds.  Then it ramps up very quickly until 40 seconds it starts to slow down.  Whereas Adam shows a much better convergence curve.  At the very beginning, it learns at a very fast pace and then slows down around 20 seconds  and smooths it up around 30 seconds.  LBFGS with Mophice Pi shows a similar learning curve except it converges much faster than  LBFGS on materialized data, but it's still slower than Adam.  This is because Mophice Pi addresses the joint redundancy, but it's still burdened by the  interaction redundancy.  Lastly, the curve of our work Mophice Pi is most interesting.  Though Adam converges earlier than both materialized and Mophice Pi with LBFGS, the first per  epoch efficiency of Mophice Pi inverse the train for LBFGS and converges earlier than  Adam.  If we look at the table of average runtime to convergence, we can see LBFGS on materialized  data used to be much slower than Adam.  But Mophice Pi has changed the train.  It makes the second out other message LBFGS converge even faster than the state of art,  Adam.  In the paper, there are more results on the real-world data set such as our LBFGS, we  made LBFGS like achieve up to 36 X Bs of all Adam and other things like we started on the  real-world data set, and that's how the sparsity impacts the usage of our framework.  Please do check out those interesting results.  And that's my talk day.  All the paper, code, and data is available at this webpage.  I'm best reachable at this email and Twitter account if you want to follow me for some  photography.  Thanks.  Thank you.
Li_Chen_Kumar_0_143.png Li_Chen_Kumar_144_311.png Li_Chen_Kumar_312_431.png Li_Chen_Kumar_432_1271.png Li_Chen_Kumar_1272_1811.png Li_Chen_Kumar_1812_2315.png Li_Chen_Kumar_2316_2783.png Li_Chen_Kumar_2784_8327.png Li_Chen_Kumar_8328_9191.png Li_Chen_Kumar_9192_9311.png Li_Chen_Kumar_9312_12491.png Li_Chen_Kumar_12492_14015.png Li_Chen_Kumar_14016_16007.png Li_Chen_Kumar_16008_16511.png Li_Chen_Kumar_16512_17339.png Li_Chen_Kumar_17340_18023.png Li_Chen_Kumar_18024_18311.png Li_Chen_Kumar_18312_18419.png Li_Chen_Kumar_18420_18983.png Li_Chen_Kumar_18984_24011.png Li_Chen_Kumar_24012_24611.png Li_Chen_Kumar_24612_25043.png Li_Chen_Kumar_25044_25166.png