Your exhalations are a direct result of the chemical reaction that gives you energy: C + O2 -> CO2. C is your carbon-based food, O2 is your inhalation, and CO2 is your exhalation. When you burn more calories, you increase the speed of that reaction, and you breath out more CO2. That is why exercise makes you lose weight (and why it makes you heat up). They are inextricable. The mass has to go somewhere!