2
$\begingroup$

I have a set of tables $\mathcal{T} = \{T_1, ..., T_n\}$, where each $T_i$ is a collection of named columns $\{c_0 .. c_{j_{i}}\}$. In addition, I have a large sequence of observations $\mathcal{D}$ of the form $(T_i, c_k)$, indicating that given access to table $T_i$ a user decided to use column $c_k$ for a particular task (not relevant to the problem formulation). Given a new table $T_j \not\in \mathcal{T}$, I'd like to rank the columns of $T_j$ based on the likelihood that a user would pick that column for the same task.

My first intuition was to expand each observation $(T_i, c_k) \in D$ into $\{ (c_k, True) \} \cup \{ (c_j, False) | c_j \in T_i \land j \neq k \}$ and view this as a classification problem, and I can then use the probability of being in the positive class as my sorting metric. My issue with this is that it seems to me that this ignores that there is a relation between columns in a given table.

I also thought perhaps there is a reasonable approach to summarizing $T_i$, call this $\phi$ and then making the problem $(\phi(T_i), f(c_k))$, where $f$ is some function over the column.

I suspect this is a problem that people have tackled before, but I cannot seem to find good information. Any suggestions would be greatly appreciated.

[Update]

Here's an idea I've been tossing around and was hoping I could get input from more knowledgeable people. Let's assume users pick $c_j \in T_i$ as a function of how "interesting" this column is. We can estimate the distribution that generated $c_j$, called this $\hat{X}_j$. If we assume a normal distribution is "uninteresting", then define $\text{interest}(c_j) = \delta(\hat{X}_j, \text{Normal})$, where we can define $\delta$ to be some distance metric (e.g. https://en.wikipedia.org/wiki/Bhattacharyya_distance). The interest level of a table $\text{interest}(T_i) = \text{op}(\{\text{interest}(\hat{X}_j) | c_j \in T_i\})$, where $op$ is an aggregator (e.g. avg). Now I expand the original $(T_i, c_k) \in \mathcal{D}$ observations into triplets of $(\text{interest}(T_i), \text{interest}(c_j), c_j == c_k)$ and treat these as a classification problem. Thoughts?

$\endgroup$
4
  • $\begingroup$ A question immediately arising: why are you speaking of columns of tables, not just of elements of sets? Does that mean rows in tables have some bearing on the problem? what are they then, what are their number, what are the tables values? Also you did't pronounce it clear about the tasks: there are a number Q of different tasks and every person performs all the tasks? $\endgroup$ – ttnphns Aug 18 '17 at 8:27
  • $\begingroup$ @ttnphns I should have perhaps provided more context: these are actual database tables, so columns/rows are significant, and in this case the tasks are ad-hoc user queries. For each ad-hoc user query, the user chooses one (or multiple) table columns to select select c1, c2, .... from t. My goal is to rank c1...cn in order of likelihood of being selected for the query. Does that clarify this? $\endgroup$ – JPC Aug 19 '17 at 14:05
  • $\begingroup$ You say given a new table you wish to rank the columns. Does this imply new tables with new data are being generated continually? $\endgroup$ – Chris Aug 22 '17 at 12:09
  • $\begingroup$ The data I have has a set number of tables, which are static. I'd like to rank columns in new tables, unrelated to the set observed before. So you could think of each of these new tables as generated by a new process. I won't have access to observations (i.e I won't actually get to see paired tables with column selections) for these new tables though, so I cannot learn directly on them. $\endgroup$ – JPC Aug 22 '17 at 14:46
1
+50
$\begingroup$

This is an interesting problem. I would begin by generating some features that describe the columns. For example a column has a type, an average number of bytes used per row, etc. Continuing with your adopted notation we have a vector of $q$ features $\boldsymbol{\phi}_{k_{i}}$ describing column $k$ of table $i$.

Define a metric in $\mathbb{R}^q$ (obeying the triangle equality, etc.) $d(\boldsymbol{\phi}, \boldsymbol{\phi}^*)$ that measures the distance between feature vectors ($||\boldsymbol{\phi} - \boldsymbol{\phi}^*||$ is a good one).

When a new table $T_j$ is selected find:

$$T^*=\min\{f(d(\boldsymbol{\phi_{k_j}}, \boldsymbol{\phi}_{k_i}))\}, \forall i \neq j$$

Where $f$ is some function of $k$ that deals with the aggregate distance of the columns in a table in some meaningful way (this could simply be $\sum_k$ for example). We now have table $T^*$ from our training data which is "closest" to the table $T_j$ that has been selected.

Having identified a table most similar to the one selected you can use your training data to determine what columns of this new table most closely resemble the columns that are usually selected in $T^*$ as per a normal machine learning problem. This is a simple approach that can be built on but may be a good place to begin.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.