0
$\begingroup$

Given $n$ variables and a function $f$ such that $f(v) = N(v) + D(v)$, where $N$ and $D$ are the subfunctions of function $f$. Function $f$, can be considered as an oracle.

Query: let $v \in P$, approximate/find the minimum value that $f$ could take over all possible configurations of $v$. For e.g., if 4 variables are given $\{x_1,x_2,x_3,x_4\}$, then if we select $v$ of size 2, that means we select a set from the PowerSet of $\{x_1,x_2,x_3,x_4\}$ of size 2 it can be {x_1,x_2} or {x_2,x_3}. Characteristic of function F [Characteristic of function N[2] Characteristic of function D Max Value function $f$ can take is when $v = \phi$ (thus, size of v = 0 -> No variables selected)

Max Size of $\left | v \right | \leq \frac{3}{4} n$. Here, size represents the number of variables selected from the given $n$ variables.

Brute Force: Enumerate all possibles elements of $PowerSet \ P$, and compute $f(v)$. Note the minimum value of $f$.

Greedy approach: In this method, we increase the size of $v$ by 1 on each iteration.

 Greedy approach for computing minimum value of f      
    Input:      
        Given $n$ variables    
        Function $f$     
    Output:     
        Approximate minimum value that $f$ takes     
    Working:       
     $minVal = f(v) $ where $v = \phi$    
     FOR{each $i = 0 to \frac{3}{4}n $}       
        FOR{each $e \in {Remaining $n-i$ variables} $}
           $u = v + \{e\} $
           $Compute $f(u)$
        ENDFOR
        Let variable $e$ gives you the minimum value when added to set $
        $newVal = f(v+\{e\})$
        IF{newVal < minVal}
            minVal = newVal
            v = v + {e}
        ELSE
            break
        ENDIF
    ENDFOR

And I believe that its not differentiable (unsure as how differentiable is defined)! Its quite close to the best feature subset selection, as adding more features might improve classification. Question: 1)Is to come up with an approximate algorithm with a performance ratio value?
2) For the above given Greedy algorithm what would be worst possible performance? Or is it possible to come up with a approximate bound on it in comparison to the optimal solution?

$\endgroup$
  • $\begingroup$ 1. Can you proof-read your question? Something seems to be missing in the first sentence: the first sentence trails off (and ends with $$ for no apparent reason). 2. What's meant by the size of $v$? $v$ is a $n$-dimensional vector, right? 3. Do you know anything about the properties of $f$? Is it continuous, differentiable, smooth, etc.? 3. How is $f$ represented? How is it provided to the algorithm? as an oracle? $\endgroup$ – D.W. Dec 22 '15 at 20:21
  • $\begingroup$ @D.W.: I have updated the question.Do you mind to have a look ? $\endgroup$ – letsBeePolite Dec 22 '15 at 20:42
  • $\begingroup$ Well, I find the question confusing. You use $v$ both for a $n$-dimensional vector and for a subset of the $n$ variables. Anyway, if $f$ is a function of $n$ variables, what does it mean to minimize $f$ when "selecting" only a subset of the variables? The value of $f$ presumably depends on the values of all $n$ variables, so it's not clear how you plan to evaluate $f$. Perhaps $f$is a function from subsets of $\{1,\dots,n\}$ to $\mathbb{R}$? I think you need to go back to the drawing board to figure out how to formulate your problem mathematically, because right now it makes no sense. $\endgroup$ – D.W. Dec 22 '15 at 20:47
  • $\begingroup$ Anyway, the availability of algorithms is going to depend on the properties of $f$. In the general case (without using any properties of $f$), you can't do any better than brute force... but if $f$ is known to have some properties (monotone, or something like that) there are known techniques. So I recommend you look at your particular $f$ and see what properties or structure it might have, and use that to improve your question. $\endgroup$ – D.W. Dec 22 '15 at 20:53

Your Answer

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

Browse other questions tagged or ask your own question.