3
$\begingroup$

Local search algorithms are useful for solving pure optimization problems, in which the aim is to find the best state according to an objective function. My question is what is the objective function ? Hill Climbing

$\endgroup$
3
$\begingroup$

The "objective function" is the function that you want to minimise or maximise in your problem.

The expression "objective function" is used in several different contexts (e.g. machine learning or linear programming), but it always refers to the function to be maximised or minimised in the specific (optimisation) problem. Hence, this expression is used in the context of mathematical optimisation.

For example, in machine learning, you define a model, $\mathcal{M}$. To train $\mathcal{M}$, you usually define a loss function $\mathcal{L}$ (e.g., a mean squared error), which you want to minimise. $\mathcal{L}$ is the "objective function" of your problem (which in this case is to be minimised).

In the context of search algorithms, the objective function could represent e.g. the cost of the solution. For example, in the case of the travelling salesman problem (TSP), you define a function, call it $C$, which represents the "cost" of the tour or Hamiltonian cycle, that is, a function which sums up the weights of all edges in the tour. In this case, the "objective" of your problem is to minimise this function $C$, because, essentially, you want to find an inexpensive tour, which is associated with either a local (or global) minimum of $C$. This function $C$ is the "objective function".

It should now be easy to memorise the expression "objective function", as it contains the term "objective", and the "objective" (or goal) in your (optimisation) problem is to minimise (or maximise) the corresponding function.

$\endgroup$
  • 1
    $\begingroup$ For mathematical optimization the definition is right. The value of a given function gets minimized and techniques like linear programming are used in reality. In the context of Artificial Intelligence an objective function is defined differently, because the aim is to program thinking machines. Mathematics alone doesn't grasp the issue, but other subjects like linguistics, psychology and game-theory have to be included. $\endgroup$ – Manuel Rodriguez Nov 17 '18 at 8:32
  • $\begingroup$ @ManuelRodriguez How would you then define an "objective function" differently in AI? Give me some examples, because I am unaware of these different types of objective functions. AFAIK, objectives functions, at the end, boil down to the same concept, either if you include components from linguistics or game-theory, ecc., or not. $\endgroup$ – nbro Nov 17 '18 at 10:20
  • 1
    $\begingroup$ In linguistics, the objective function is defined as maximum mutal information which is a correlation between two systems which minimizes the conditional entropy. In Business Intelligence systems it is called algorithmic objective functions, to make clear that is much more advanced than what is known from mathematics. $\endgroup$ – Manuel Rodriguez Nov 17 '18 at 11:40
  • $\begingroup$ @ManuelRodriguez Can you cite some sources that support your claims? Because I've never heard of these. Also, what is business intelligence?! Don't those definitions boil down to the same concept, i.e., minimising or masimizing a function? In which sense it is "more advanced". $\endgroup$ – nbro Nov 17 '18 at 11:56
  • 1
    $\begingroup$ And i doesn't disagree with the statement that cosine similarity can be formulated as a mathematical equation. In the paper “Singh, Vipul. Application of Quantum Computing principles to Natural Language Processing. Diss. Indian Institute of Technology, Bombay” the application of qubits for building an objective function for NLP is described. $\endgroup$ – Manuel Rodriguez Nov 18 '18 at 17:47
1
$\begingroup$

In human-computer-interaction, the objective function directs to constraints from the outside. It is an in-between layer which communicates between the needs of the system itself and the operator who want's to do useful things with the system. For example, the operator want's to walk with the avatar to the right of the screen. The objective function is the machine readable demand of the human-operator. If the operator changes the goal, for example the avatar should jump, than the objective function is different. The objective function can be seen as a human-machine dialog.

Unfortunately, the interface can contain many possible modes, for example the human-operator can control the avatar by speech, by gesture, with a joystick or by numerical parameters. In each case, the objective function is different. That means, a command like “walk to the left” produces a another kind of goal than a joystick movement. In general, the objective function is given by the gui-interface, because the human-operator has pressed on the gui a button, and this command is the goal for the system which has to be reached.

Here are some examples for objective functions in a linguistic context. In both cases, the objective function is more complicated than only an equation, but it is dialogue-model in the first example:

quote: “The objective function is a weighted sum of costs representing different dimensions of the dialog quality: distance [...], efficiency [...], quantity [...], cost [...], effectiveness of presentation, etc. “ Levin, Esther, Roberto Pieraccini, and Wieland Eckert. "A stochastic model of human-machine interaction for learning dialog strategies." IEEE Transactions on speech and audio processing 8.1 (2000): 11-23.

... and a neural network in the second:

quote: “Below, we present practical strategies for neural generation models that use Maximum Mutual Information (MMI) as an objective function.” Li, Jiwei, et al. "A diversity-promoting objective function for neural conversation models." arXiv preprint arXiv:1510.03055 (2015).

$\endgroup$
  • $\begingroup$ You answered to a different question. The OP is clearly asking about the "objective function" in the context of optimisation problems. The picture he also posted should have made this super clear. I will not downvote this answer, because I will assume that you thought that the OP asked about a different type of "objective function". But I think you should delete this answer, as I am pretty sure it doesn't address the OP's concerns. $\endgroup$ – nbro Nov 16 '18 at 22:34
  • $\begingroup$ @nbro I haven't deleted the answer but added two references. Thanks for the advice to make the point more clear. $\endgroup$ – Manuel Rodriguez Nov 18 '18 at 16:44

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.